Dữ liệu đảm bảo để bài luôn có kết quả!

Ngày hôm nay có ~n~ gian hàng bán đồ ăn tại lễ hội ở đền Hakurei. Yuyuko ham ăn muốn đi ăn ~q~ lượt, mỗi lượt từ gian hàng ~l~ đến gian hàng ~r~. Với mỗi gian hàng, hãy in ra số lần cô ghé thăm.

Input

• Dòng đầu gồm 2 số ~n, q~.
• ~q~ dòng tiếp theo mỗi dòng thứ ~i~ gồm 2 số ~l_i, r_i~ ~(1 \le l_i \le r_i \le 10^5)~ là lượt đi ăn thứ ~i~.

Output

• In ra ~n~ số ứng với ~n~ cửa hàng là số lần Yuyuko vào gian hàng.

Sample Test

Input:

4 3
1 3
2 4
1 2

Output:

2 3 2 1

Marisa tin rằng danmaku hình tam giác là sặc sỡ nhất. Cho 3 điểm tọa độ nguyên trên lưới tọa độ ~Oxy~, hãy xác định xem 3 điểm này có tạo thành hình tam giác được hay không?

Input

• 3 điểm có tọa độ nguyên.

Output

• YES và NO tương ứng với có hoặc không tạo được hình tam giác.

Sample Test

Input 1

0 0 0 1 1 0

Output 1

YES

Input 2

727 1 727 2 727 3

Output 2

NO

Giới hạn

• Tọa độ các điểm có giá trị tuyệt đối không vượt quá ~10^9~.

Yakumo Ran rất giỏi toán, nhưng với những số rất lớn cô sẽ gặp khó khăn nên cô nhờ các bạn giúp bài toán sau.

Cho hai số nguyên dương ~a,b~, hãy tính: ~\sum_{i=a}^b~ ~⌊\sqrt{i}⌋~.

Ở đây, ~⌊a⌋~ có nghĩa là số nguyên lớn nhất không lớn hơn ~a~.

Input

• Gồm một dòng chứa hai số nguyên dương ~a,b~.

Output

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

Sample Test

Input 1

3 10

Output 1

17

Giải thích

~⌊\sqrt{3}⌋+⌊\sqrt{4}⌋+⌊\sqrt{5}⌋+⌊\sqrt{6}⌋+⌊\sqrt{7}⌋+⌊\sqrt{8}⌋+⌊\sqrt{9}⌋+⌊\sqrt{10}⌋~ ~=1+2+2+2+2+2+3+3=17~

Input 2

14 29

Output 2

67

Giới hạn:

• Subtask 1 (60% số điểm): ~a,b \le 10^6~
• Subtask 2 (40% số điểm): ~a,b \le 10^{12}~

Năm ~404~ BC, vùng đất Westeros đang xôn xao vì một bài toán rất lạ được đưa ra từ một kẻ ẩn danh tới từ Essos. Khắp bảy phụ quốc, các lãnh chúa liên tục tìm người để giải quyết bài toán nhưng đều thất bại. Bài toán được lan truyền tới Oldtown và khiến các Maester ở Citadel cũng phải đau đầu. Hãy giúp các học sĩ giải quyết bài toán này nhé:

Số đẹp được định nghĩa là một số nguyên dương và chia hết cho một trong ba số: ~3~, ~5~, hoặc ~7~.

Ví dụ về dãy các số đẹp: ~3, 5, 6, 7, 9, 10, 12, 14, 15, 18,...~

Hãy tìm số đẹp thứ ~k~.

Input

• Gồm một dòng chứa số nguyên dương ~k~.

Output

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

Sample Test

Input 1

2

Output 1

5

Input 2

10

Output 2

18

Giới hạn:

• Subtask 1 (50% số điểm): ~k \le 10^6~
• Subtask 2 (50% số điểm): ~k \le 10^9~

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

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1,A_2,…,A_N~. In ra độ dài của dãy con liên tiếp đan dấu dài nhất. (Đan dấu là không có hai phần tử nào cạnh nhau mà có cùng dấu)

Input:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N≤10^5)~ là số lượng phần tử của dãy ~A~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1,A_2,…,A_N~ mô tả dãy ~A~ ~(0<|A_i|≤10^9)~.

Output:

Ghi ra một số nguyên duy nhất là độ dài của dãy con liên tiếp đan dấu dài nhất.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~N≤10^3~;
• ~40\%~ số test còn lại ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Sample Test 1

Input:

9
1 3 -1 3 -2 4 -5 -6 7

Output

6

Giải thích

Dãy đan dấu: 3 -1 3 -2 4 -5

Sample Test 2

Input:

9
1 3 -1 3 -2 4 -5 6 7

Output

7

Giải thích

Dãy đan dấu 3 -1 3 -2 4 -5 6

Cho một dãy số ~A~ gồm ~N~ phần tử ~A_1,A_2,…,A_N~. Một dãy con liên tiếp từ ~L~ đến ~R~ của dãy số ~A~ là các phần tử ~A_L,A_{L+1},…,A_{R-1},A_R~ ~(1≤L≤R≤N)~. Cho một số nguyên dương ~T~, hãy đếm xem có bao dãy con của ~A~ có tổng các phần tử không quá ~T~.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~T~ là số lượng phần tử của dãy số ~A~ và số ~T~ cho trước ~(N≤10^6; T≤10^9)~;
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_i~ mô tả các phần tử của dãy số ~A~ ~(1≤i≤N; A_i≤10^9)~.

Output:

Một số nguyên duy nhất là số lượng dãy con thoả mãn yêu cầu đề bài.

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm có ~N≤100~;
• Có 30% số test khác tương ứng với 30% số điểm có ~N≤5000~;
• 20% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.

Sample Test 1

Input:

6 8
8 3 2 1 6 9

Output

9

Giải thích

Các dãy con thoả mãn: ~\{8\},\{3\},\{2\},\{1\},\{6\},\{3,2\},\{2,1\},\{1,6\},\{3,2,1\}~

Chuẩn bị Gala mừng năm mới Tết Tân Sửu 2021 của công ty HiTech, ban giám đốc quyết định có giải thưởng đặc biệt cho thành viên của công ty. Sau khi đưa ra các tiêu chí đánh giá, việc bầu chọn sẽ được thực hiện bằng cách tất cả các thành viên sẽ được bỏ phiếu cho nhau.

Hình thức bỏ phiếu được thực hiện thông qua phiếu bầu chọn online. Danh sách các thành viên của công ty được niêm yết và quy định là số thứ tự từ ~1~ đến ~N~ ~(1≤N≤5000),~ tương ứng với ~N~ ô trên phiếu bầu chọn. Sau khi thực hiện, ban tổ chức thu được các danh sách phiếu tương ứng của các thành viên công ty. Trong mỗi phiếu bầu chọn, giá trị ô ở vị trí tương ứng ghi ~'X'~ là bầu chọn cho người đó, ô ghi ~'0'~ là không bầu chọn (coi các trường hợp bầu chọn không hợp lệ là không bầu chọn).

Yêu cầu: Em hãy giúp ban tổ chức đưa ra danh sách các nhân viên có phiếu bầu chọn cao nhất.

Dữ liệu nhập vào từ file văn bản VOTE.INP:

• Dòng đầu tiên gồm số một số nguyên dương ~N~ ~(1≤N≤5000)~ là số lượng phiếu bầu chọn.
• ~N~ dòng tiếp theo mỗi dòng tương ứng là ~N~ giá trị của các phiếu đã bầu chọn.

Các kí tự cách nhau một dấu cách.

Kết quả ghi ra file văn bản VOTE.OUT:

• Dòng đầu tiên ghi số lượng người được nhiều phiếu nhất và số lượng phiếu.
• Dòng thứ hai ghi thứ tự tương ứng của những người được cao phiếu nhất đó theo thứ tự tăng dần.

Ví dụ

Input

5
X 0 X 0 X
X 0 0 X X
0 0 X 0 0
0 X 0 X 0
0 0 X X 0

Output

2 3
3 4

Giải thích:

• Người số ~1~ được ~2~ phiếu bầu chọn.
• Người số ~2~ được ~1~ phiếu bầu chọn.
• Người số ~3~ được ~3~ phiếu bầu chọn.
• Người số ~4~ được ~3~ phiếu bầu chọn.
• Người số ~5~ được ~2~ phiếu bầu chọn.
• Người số ~3~ và số ~4~ cùng được số phiếu bầu chọn lớn nhất.

Giới hạn

• Có ~70\%~ số test tương ứng với số điểm có ~N \le 1000;~
• ~30\%~ số test còn lại tương ứng với số điểm có ~N \le 5000.~

Nông dân John (FJ) có ~N~ con bò đang đứng trên một hàng, mỗi con đứng ở một vị trí khác nhau trên trục số. Chúng đang luyện tập ném trái bóng chày vòng vòng để chuẩn bị cho một trận thi đấu quan trọng với những con bò láng giềng. Khi FJ theo dõi, ông ta nhận ra một nhóm có ba con bò ~(X,Y,Z)~ hoàn thành hai cú ném. Con bò ~X~ ném trái bóng cho con bò ~Y~ ở bên phải cô ta, và con bò ~Y~ ném trái bóng cho con bò ~Z~ ở bên phải cô ta. FJ để ý rằng lần ném thứ hai có độ dài không quá hai lần so với lần ném đầu tiên. Hãy giúp FJ đếm xem có bao nhiêu bộ ba các con bò ~(X,Y,Z)~ mà FJ có thể theo dõi.

Input

• Dòng ~1~: Số lượng các con bò là ~N~ ~(3 <= N <=1000)~.
• Dòng ~2..1+N~: Mỗi dòng chứ một số tự nhiên là vị trí của một con bò (các số tự nhiên nằm trong khoảng ~0..10^8~).

Output

In ra Số lượng bộ ba con bò ~(X,Y,Z)~, trong đó con bò ~Y~ nằm bên phải con bò ~X~, con bò ~Z~ nằm bên phải con bò ~Y~, và khoảng cách giữa ~Y~ và ~Z~ nằm giữa ~XY~ và ~2XY~ (bao gồm cả giá trị này), trong đó ~XY~ là khoảng cách của ~X~ đến ~Y~.

Sample Test

Input:

5 
3 
1 
10 
7 
4 

Output

4

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

Số trùng là một số tự nhiên mà chữ số đầu tiên trùng với chữ số cuối cùng. Ví dụ: ~8, 66, 686, 8398,...~

Nhập vào một số tự nhiên ~N~ là số trùng. Hãy đếm xem có bao nhiêu số trùng nhỏ hơn ~N~ mà có chữ số đầu và chữ số cuối giống như ~N~.

Ví dụ: ~N = 131~, có các số thoả mãn: ~121, 111, 101, 11, 1~. Vậy có ~5~ số thoả mãn.

Input

Số tự nhiên ~N~ ~(N \le 10^9)~.

Output

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

Sample Test

Input

131

Output

5