Công ty điện lực thành phố cần xây dựng hệ thống đèn chiếu sáng một sân chơi hình chữ nhật kích thước ~n \times m~ (meters) bằng các bóng đèn. Mỗi bóng đèn có thể chiếu sáng một hình vuông kích thước ~k \times k~ (meters) có các cạnh song song với biên của cái sân.

Yêu cầu: Hãy tìm số lượng bóng đèn ít nhất để có thể chiếu sáng toàn bộ sân chơi.

Input

Một dòng chứa ba số nguyên dương ~n, m, k~ (~1 \le n, m, k \le 10^9~), các số cách nhau dấu cách.

Output

Một dòng ghi một số là số bóng đèn ít nhất tìm được.

Sample Input 1

4 8 2

Sample Output 1

8

Sample Input 2

10 9 3

Sample Output 2

12

Để luyện tập bé An viết và nhớ các chữ số thập phân, mẹ ghi ra giấy cho bé một xâu ~S~ chỉ gồm ba ký tự (+, -, =) và hướng dẫn bé chơi trò chơi sau: đầu tiên bé chọn một chữ số thập phân khác chữ số 0 và tạo ra một số ~N~ có nhiều chữ số dựa vào xâu ký tự ~S~. Sau khi đã chọn chữ số đầu tiên, mỗi chữ số tiếp theo sẽ dựa trên chữ số kế trước đó và tùy thuộc các ký tự liên tiếp trong xâu ~S~.

Nếu dấu "+" thì chữ số tiếp theo sẽ lớn hơn chữ số kế trước đó 1 đơn vị, nếu là dấu "-" thì chữ số tiếp theo sẽ nhỏ hơn chữ số kế trước đó 1 đơn vị, và nếu là dấu "=" thì chữ số tiếp theo sẽ là bằng chữ số kế trước đó.

Để luyện tập bé An đã chọn tất cả các chữ số khác chữ số 0 để bắt đầu và đã viết ra rất nhiều số có nhiều chữ số.

Yêu cầu: Hãy tìm xem trong tất cả các số ~N~ mà bé An đã viết ra thì số có giá trị nhỏ nhất là số nào.

Input

Một dòng chứa xâu ~S~ chỉ gồm 3 ký tự ('+', '-', '=') có độ dài không quá 100 ký tự.

Output

Một dòng ghi số nguyên theo yêu cầu, các chữ số viết liền nhau và chữ số đầu tiên phải khác chữ số 0. Trong trường hợp không thể tạo được số ~N~ thì ghi ra 0.

Sample Input 1

+--+=+

Sample Output 1

1210112

Ví dụ 1: Chữ số đầu tiên được chọn là 1, chữ số tiếp theo thứ hai là 2 bởi dấu đầu tiên trong xâu ~S~ là '+', dấu tiếp theo là dấu '-' nên chữ số thứ ba sẽ là 1, ...

Sample Input 2

+++++++++

Sample Output 2

0

Ví dụ 2: Không thể tạo được số theo yêu cầu bởi xâu ~S~ có 9 dấu '+' mà không thể bắt đầu bằng chữ số 0 (nếu bắt đầu bằng 1 thì chữ số cuối cùng sẽ vượt quá 9).

An có hai cuốn albums sưu tầm các con tem. Cuốn thứ nhất có ~n~ con tem, cuốn thứ hai có ~m~ con tem. Trong cùng một cuốn các con tem đều khác nhau, nhưng trong cả hai cuốn thì có một số con tem trùng nhau. An muốn tìm các con tem trùng để có thể đổi các con tem khác. An nhớ chắc chắn rằng khi sưu tầm An đã cẩn thận đánh số các con tem, hai con tem khác nhau thì được đánh bằng hai số hiệu khác nhau và các con tem giống nhau đã được đánh cùng một số hiệu.

Yêu cầu: Hãy giúp An tìm số lượng các con tem trùng nhau trong hai cuốn albums.

Input

• Dòng đầu chứa hai số nguyên dương ~n, m~ (~1 \le n, m \le 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~) là số hiệu của các con tem trong album thứ nhất.
• Dòng thứ ba chứa ~m~ số nguyên dương ~b_1, b_2, ..., b_m~ (~1 \le b_i \le 10^9~) là số hiệu của các con tem trong album thứ hai.

Output

• Dòng đầu tiên ghi số nguyên dương ~k~ là số lượng các con tem trùng nhau.
• Dòng thứ hai ghi ~k~ số nguyên là số hiệu của các con tem trùng nhau theo thứ tự tăng.
• Trong trường hợp không có hai con tem nào trùng nhau thì chỉ ghi ra số 0.

Sample Input 1

5 6
2 10 5 13 4
6 2 13 3 10 1

Sample Output 1

3
2 10 13

Sample Input 2

3 3
10 15 20
1 2 3

Sample Output 2

0

Subtasks

• 50% số tests tương ứng với 50% số điểm của bài có ~n, m \le 7500~.
• 50% số tests tương ứng với 50% số điểm của bài có ~7500 \le n, m \le 10^5~.

Cho một dãy gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Độ giống nhau của hai số là số chữ số tương ứng giống nhau của hai số tính tương ứng theo hàng đơn vị, hàng chục, hàng trăm, ...

• Ví dụ: Hai số 204 và 24 có độ giống nhau là 1 bởi chúng chỉ có chữ số hàng đơn vị giống nhau.
• Hai số 24 và 25 có độ giống nhau là 1 bởi chúng có chữ số hàng chục giống nhau.
• Hai số 2024 và 24 có độ giống nhau là 2.

Yêu cầu: Hãy tính tổng độ giống nhau của tất cả các cặp số hạng trong dãy. Hai số hạng ~a_i, a_j~ của dãy là một cặp nếu ~i \neq j~.

Input

• Dòng đầu chứa số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~0 < a_i < 10^9~), các số cách nhau dấu cách.

Output

Một dòng ghi một số là tổng độ giống nhau của các cặp số tìm được.

Sample Input 1

4
12 13 22 7

Sample Output 1

6

Sample Input 2

5
13 23 22 211 212

Sample Output 2

18

Subtasks

• 20% số tests tương ứng với 20% số điểm của bài có ~1 \le n \le 1000~.
• 30% số tests tương ứng với 30% số điểm của bài có ~0 < a_i < 1000~.
• 50% số tests tương ứng với 50% số điểm của bài không có ràng buộc gì thêm.