Cho ~a, b~ là độ dài 2 cạnh đáy và ~h~ là chiều cao của một hình thang. Tính diện tích hình thang đó.

Input

• Gồm một dòng chứa ~3~ số thực ~a, b, h~ (~a, b, h \leq 1000~).

Output

• In ra diện tích hình thang. Kết quả được tính đến chữ số thập phân thứ 3.

Sample Test

Input

5 3 2 

Output

8

Cho bốn số nguyên dương ~a, b, c, d~. Hãy so sánh ~\frac {a} {b}~ với ~\frac {c} {d}~.

Input

• Gồm một dòng chứa bốn số nguyên dương ~a, b, c, d~ (~a, b, c, d \leq 10^9~).

Output

• In ra > nếu ~\frac {a} {b} > \frac {c} {d}~.
• In ra < nếu ~\frac {a} {b} < \frac {c} {d}~.
• In ra = nếu ~\frac {a} {b} = \frac {c} {d}~.

Sample Test

Input

1 2 3 4

Output

<

Note

• ~\frac {1} {2} < \frac {3} {4}~.

TDZ quan niệm rằng, một số không may mắn là số chia hết cho ~5~ hoặc chia cho ~5~ dư ~3~.

Vi dụ các số may mắn: ~1, 2, 4, 6, 7, 9, 11, 12, 14~.

Biết rằng TDZ chỉ sử dụng tất cả các số may mắn nhỏ hơn ~N~ đánh số thứ tự các bạn học sinh để gửi lời chúc kiểm tra thật tốt. Hãy tính tổng các số may mắn đã được sử dụng.

Input

• Gồm một số nguyên dương ~N~ duy nhất. (~N \leq 10^8~)

Output

• In ra tổng các số may mắn nhỏ hơn ~N~.

Sample Test

Input

15

Output

66

Note

• Các số may mắn nhỏ hơn ~N~ là ~1, 2, 4, 6, 7, 9, 11, 12, 14~ và tổng của chúng bằng ~66~.

Trên một màn hình LED lớn, người ta lần lượt cho hiện ra các số tự nhiên từ ~0~ đến ~9~ và cứ lặp đi lặp lại như thế (tức là sau số ~9~ là số ~0~).

Ban đầu, giây thứ ~0~, màn hình xuất hiện số ~K~ ~(0 ≤ K ≤ 9)~, sau ~1~ giây sẽ chuyển số tiếp theo.

Hỏi sau ~N~ giây, màn hình đang hiển thị số mấy?

Yêu cầu: Nhập vào ~N, K~. In ra số đang hiển thị ở giây thứ ~N~.

Input

• Gồm hai số nguyên ~N, K~ ~(K \le 9; N \le 10^9)~.

Output

• In ra một số nguyên duy nhất là kết quả của bài toán.

Sample Test

Input

5
0

Output

5

Cho số nguyên dương ~N~. Đếm xem trong các chữ số của ~N~ có bao nhiêu số nguyên tố.

Input

• Gồm một số nguyên dương ~N~ duy nhất.
  
  

Output

• In ra số lượng chữ số là số nguyên tố trong ~N~.
  
  

Subtasks

• Subtask 1 (~50\%~ số điểm): ~N \leq 10^4~.
• Subtask 2 (~20\%~ số điểm): ~N \leq 10^8~.
• Subtask 3 (~30\%~ số điểm): ~N \leq 10^{100}~.
  
  

Sample Test

Input

23452345

Output

6

Note

• Có ~6~ chữ số nguyên tố trong ~N~ là ~2, 3, 5, 2, 3, 5~.

Cho một dãy gồm ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ và một số nguyên ~x~. Tìm số lớn nhất trong dãy sao cho số đó nhỏ hơn số ~X~.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~ (~N \leq 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ... a_N~. (~a_i \leq 10^6~)
• Dòng thứ ba chứa số nguyên ~X~. (~|X| \leq 10^6~)

Output

• In ra số lớn nhất nhỏ hơn ~X~ trong dãy. Nếu không tồn tại số nào thì in ra -1.

Sample Test 1

Input

5
1 2 6 4 5
4

Output

2

Sample Test 2

Input

4
1 2 3 4
0

Output

-1

Cho một dãy gồm ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~. Biết rằng các số trong dãy đều xuất hiện hai lần, trừ một số. Hãy tìm số đó.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ... a_N~. (~a_i \leq 10^6~)
• Các số đều xuất hiện hai lần trừ một số.

Output

• In ra số chỉ xuất hiện một lần trong dãy.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~N = 3~.
• Subtask 2 (~30\%~ số điểm): ~N \leq 10^3~.
• Subtask 3 (~50\%~ số điểm): ~N \leq 10^6~.

Sample Test 1

Input

5
4 1 2 1 2

Output

4

Cho một dãy gồm ~N~ số nguyên ~a_1, a_2, a_3, ..., a_N~. Hãy tìm đoạn con liên tiếp và dài nhất mà các phần tử liên tiếp cách đều nhau.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, a_3, ... a_N~. (~|a_i| \leq 10^9~)

Output

• In ra độ dài của đoạn con dài nhất thoả mãn đề bài.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~N = 3~.
• Subtask 2 (~30\%~ số điểm): ~N \leq 10^3~.
• Subtask 3 (~50\%~ số điểm): ~N \leq 10^6~.

Sample Test 1

Input

3
1 2 1

Output

3

• Dãy đã cho có các số liên tiếp cách nhau ~1~ đơn vị nên đây là dãy con dài nhất thoả mãn.

Sample Test 2

Input

6
1 2 3 5 7 9

Output

4

Note

• Dãy con liên tiếp dài nhất và cách đều nhau là ~3, 5, 7, 9~. (khoảng cách giữa các số liên tiếp đều là ~2~)

Sample Test 3

Input

6
1 4 7 4 7 1

Output

5

Note

• Dãy con liên tiếp dài nhất và cách đều nhau là ~1, 4, 7, 4, 7~. (khoảng cách giữa các số liên tiếp đều là ~3~)

Cho dãy số có quy luật như sau: ~1,2,2,3,3,3,4,4,4,4,5,5,…~ Cho một số tự nhiên ~N~, hãy tìm số thứ ~N~ của dãy số trên (các số được đánh thứ tự từ ~1~).

Input

• Gồm một số nguyên dương ~N~ ~(N ≤ 10^{15})~.

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1 (~60\%~ số điểm): ~N ≤ 10^{6}~;
• Subtask 2 (~20\%~ số điểm): ~N ≤ 10^{10}~;
• Subtask 3 (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test

Input

5

Output

3

Cho một dãy gồm ~N~ số nguyên ~a_1, a_2, a_3, ..., a_N~. Hãy tìm một đoạn con liên tiếp trong dãy sao cho chúng có tổng lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, a_3, ... a_N~. (~|a_i| \leq 10^9~)

Output

• In ra tổng lớn nhất tìm được.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~N = 3~.
• Subtask 2 (~20\%~ số điểm): ~N \leq 100~.
• Subtask 3 (~30\%~ số điểm): ~N \leq 10^3~.
• Subtask 4 (~30\%~ số điểm): ~N \leq 10^6~.

Sample Test

Input

7
-2 -3 4 -1 -2 1 5

Output

7

Note

• Đoạn con có tổng lớn nhất là ~4, -1, -2, 1, 5~.

Cho một xâu ~S~ gồm các kí tự số. Hãy đếm xem có bao nhiêu xâu con chia hết cho ~4~ (xâu con có thể bắt đầu bằng ~0~).

Một xâu con của ~S~ là xâu được tạo thành từ các ký tự liên tiếp trong ~S~.

Input

• Gồm một xâu ~S~ có độ dài không quá ~10^6~.

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1 (~60\%~ số điểm): Xâu ~S~ có độ dài không quá ~100~.
• Subtask 2 (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test 1

Input

08

Output

3

Note

• Các xâu con thoã mãn là ~0, 8, 08~.

Sample Test 2

Input

13085

Output

5

Viết liền các số nguyên dương liên tiếp, từ nhỏ đến lớn, bắt đầu từ ~1~, ta sẽ được một dãy dài vô hạn gồm các chữ số: ~123456789101112131415161718192021222324252627282930313233343536\ldots~

Bạn được cho số nguyên dương ~k~, nhiệm vụ của bạn là tìm chữ số thứ ~k~ của dãy trên.

Input

• Dòng thứ nhất chứa số nguyên dương ~T~ - số bộ dữ liệu. (~T \leq 10^3~)
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~k~.

Output

• In ra ~T~ dòng, mỗi dòng chứa một chữ số cho bộ dữ liệu tương ứng.

Subtasks

• Subtask 1 (~20\%~ số điểm): Mọi số ~k \leq 50~.
• Subtask 2 (~30\%~ số điểm): Mọi số ~k \leq 10^6~.
• Subtask 3 (~50\%~ số điểm): Mọi số ~k \leq 10^{18}~.

Sample Test

Input

5
8
18
16
14
19

Output

8
1
1
1
4

Cho số nguyên dương ~N~. Hãy đếm số cách xoá đi một đoạn chữ số liên tiếp của ~N~ (không được xoá hết) để nhận được số mới chia hết cho ~3~, biết rằng số mới nhận được có thể có thừa chữ số ~0~ ở đầu.

Hai cách xoá được coi là khác nhau nếu có một vị trí được xoá trong cách này nhưng không được xoá trong cách kia.

Input

• Gồm một dòng duy nhất chứa một số nguyên ~N~ (~1 \le N \le 10^{100000}~).

Output

• In ra một số nguyên là số cách xoá tìm được.

Subtasks

• Subtask 1 (~50\%~ số điểm): ~N \le 10^{300}~.
• Subtask 2 (~25\%~ số điểm): ~N \le 10^{10000}~.
• Subtask 3 (~25\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test 1

Input

1005

Output

4

Sample Test 2

Input

2009

Output

3