Cho một kí tự ~c~. Liệu ~c~ có phải một chữ cái thuộc bảng chữ cái tiếng Anh hay không? Hãy kiểm tra xem!

Input

Gồm một ký tự ~c~ duy nhất.

Output

In ra YES nếu ~c~ thuộc bảng chữ cái tiếng Anh, ngược lại in ra NO.

Sample Test 1

Input:

a

Output:

YES

Sample Test 2

Input:

@

Output:

NO

Cho số nguyên dương ~n~. Hãy đưa ra số lượng chữ số của ~n~ và tổng các chữ số trong biểu diễn thập phân của ~n~.

Input

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

Output

Gồm hai dòng, dòng thứ nhất chứa số chữ số và dòng thứ hai chứa tổng chữ số của ~n~.

Sample Test

Input:

69

Output:

2
15

Cho số nguyên dương ~n~, hãy kiểm tra xem ~n~ có phải là số nguyên tố hay không.

Input

Gồm một số nguyên ~n~ duy nhất (~n \leq 10^9~)

Output

In ra YES nếu ~n~ là số nguyên tố, ngược lại thì in ra NO.

Subtasks

Subtask ~1~ (~40\%~): ~n \leq 10^3~.

Subtask ~2~ (~60\%~): Không có điều kiện gì thêm.

Sample Test

Input:

3

Output:

YES

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 một số nguyên dương ~N~. Đếm xem có bao nhiêu số nguyên không âm nhỏ hơn ~N~ và có tận cùng là chữ số ~K~.

Input:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N≤10^9)~.
• Dòng thứ hai chứa số nguyên ~K~ ~(0≤K≤9)~.

Output:

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

Ràng buộc

• Có ~70\%~ số test ứng với ~70\%~ số điểm của bài thoả mãn: ~N≤10^6~;
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Sample Test

Input:

68
3

Output

7

Giải thích

Các số thoả mãn là: ~3,13,23,33,43,53,63~.

Cho dãy số gồm ~n~ ~(n \le 10^5)~ phần tử nguyên dương ~a_1, a_2, ... , a_n~ ~(a_i \le 10^6)~ và một số nguyên dương ~k~ cho trước ~(k \le 10^9)~

Tìm dãy con liên tiếp dài nhất có tổng đúng bằng ~k~

Input

• Dòng đầu nhập số nguyên dương ~n~ và ~k~.
• Dòng thứ ~2~ nhập ~n~ số nguyên ~a_1, a_2, ... , a_n~.

Output

• In ra kết quả là độ dài dãy con thỏa mãn yêu cầu

Sample test

Input

7 7 
4 3 2 1 1 1 6

Output

4

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\}~

Cho một dãy số ~A~ nguyên không âm gồm ~n~ phần tử và một số ~k~ bất kì ~(k<=n)~. Ta định nghĩa ý nghĩa của dãy số này chính bằng trung bình cộng lớn nhất của một đoạn con liên tiếp bất kì trong dãy với độ dài lớn hơn hoặc bằng ~k~. Nói cách khác, ý nghĩa của dãy chính bằng ~max(f(l,r))~, với ~f(l,r)~ là trung bình cộng của đoạn con ~[l,r]~ và ~(1 \le l \le r \le n, r-l+1 \ge k)~. Hãy lập trình để đi tìm ý nghĩa của dãy.

Input:

• Dòng đầu gồm 3 số ~n,k,h~.
• Dòng sau là ~n~ phần tử của dãy ~A~. (~1 \le k \le n \le 10^5, 0 \le h \le 1~), (~A_i \le 10^5 ~ với mọi ~1 \le i \le n~).

Output:

Nếu ~h = 0~, in ra phần nguyên của kết quả tìm được. Ngược lại nếu ~h = 1~, in ra kết quả lấy 3 chữ số thập phân sau dấu phẩy.

Sample Test 1

Input:

4 2 0 
17 0 14 1

Output:

10

Sample Test 2

Input:

4 2 1
17 0 14 1

Output:

10.333

Giải thích:

• Ở test 1, đoạn con thỏa mãn là ~[1,3]~ có giá trị trung bình là 10.(333). Tuy nhiên do ~h = 0~ nên ta chỉ lấy phần nguyên của kết quả là 10.
• Ở test 2, tương tự test 1, nhưng do ~h = 1~ nên ta lấy kết quả = 10.333

Ràng buộc

• Subtask 1: ~n \le 1000~. (50%)
• Subtask 2: ~n \le 10^5, h = 0~. (30%)
• Subtask 3: ~n \le 10^5~. (20%)

Cho dãy số nguyên dương ~A~ gồm ~N~ phần tử. Tìm đoạn con liên tiếp có nhiều phần tử nhất thoả mãn:

• Đoạn con từ ~L~ đến ~R~;
• Tồn tại một vị trí ~i~ ~(L \le i \le R)~ sao mọi số từ vị trí ~L~ đến vị trí ~R~ đều chia hết cho ~A_i~;
• ~R - L~ lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^6)~;
• Dòng thứ hai ~N~ số nguyên mô tả dãy số ~A~ có giá trị không quá ~10^6~.

Output

• Dòng đầu tiên in ra số ~K~ là số các cặp ~(L, R)~ thỏa mãn điều kiện và giá trị ~(R - L)~ lớn nhất cách nhau bởi một dấu cách.
• Dòng thứ hai in ra ~K~ số là các giá trị ~L~ của các cặp số được sắp xếp từ nhỏ đến lớn.

Giới hạn

• Có ~70\%~ số test có ~N \le 10^3~;
• ~30\%~ số test còn lại không có điều kiện gì thêm.

Sample Test

Input

5
4 6 9 3 6

Output

1 3
2