Xét tất cả các số nguyên được tạo bởi một dãy liên tiếp các chữ số của C. Với mỗi số, An kiểm tra xem số đó có phải là số nguyên tố hay không và tự hỏi trong tất cả các số nguyên được xét, có bao nhiêu số nguyên tố?

Là một lập trình viên tài ba, bạn hãy giúp An nhé!

Input

Số nguyên C, thỏa mãn:

• ~0 \le C \le 2 \times 10^9~.

Output

• Ghi ra số lượng các số nguyên tố tìm được.
• Nếu không có thì in ra thông báo: NO PRIMES

Sample Input

2319
908

Sample Output

6
NO PRIMES

Cho một mảng số nguyên a gồm n phần tử và một số nguyên k.

Hãy tìm một đoạn con liên tiếp có độ dài đúng bằng k sao cho giá trị trung bình của các phần tử trong đoạn là lớn nhất. In ra giá trị trung bình lớn nhất tìm được.

Một đáp án được chấp nhận nếu sai số tuyệt đối nhỏ hơn ~10^{-5}~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n,k~ ~(1 \le k \le n \le 10^5)~.
• Dòng thứ hai chứa n số nguyên ~a_1,a_2,\ldots,a_n~ ~(-10^4 \le a_i \le 10^4)~.

Output

In ra giá trị trung bình lớn nhất của một đoạn con liên tiếp có độ dài đúng bằng k.

Ví dụ

Do số lượng sinh viên của Đại học Quốc gia Berland tăng lên, trường quyết định trang bị một phòng máy tính mới. Bạn được giao nhiệm vụ mua chuột máy tính với tổng chi phí thấp nhất có thể.

Các máy tính trong phòng không giống nhau. Một số chỉ có cổng USB, một số chỉ có cổng PS/2, và một số hỗ trợ cả hai loại cổng.

Cửa hàng cung cấp bảng giá gồm ~m~ con chuột. Với mỗi con chuột, biết giá bán và loại cổng mà nó hỗ trợ (USB hoặc PS/2). Mỗi con chuột chỉ có thể được mua nhiều nhất một lần.

Hãy chọn mua một số chuột sao cho số lượng máy tính được trang bị chuột là lớn nhất có thể. Nếu có nhiều cách đạt được cùng số lượng máy tính được trang bị, hãy chọn cách có tổng chi phí nhỏ nhất.

Input

• Dòng đầu tiên chứa ba số nguyên ~a,b,c~ lần lượt là số máy tính chỉ có cổng USB, số máy tính chỉ có cổng PS/2 và số máy tính hỗ trợ cả hai loại cổng. ~(0 \le a,b,c \le 10^5)~.
• Dòng thứ hai chứa số nguyên ~m~ là số lượng chuột trong bảng giá. ~(0 \le m \le 3 \times 10^5)~.

• ~m~ dòng tiếp theo, mỗi dòng mô tả một con chuột gồm:

  • Một số nguyên ~val_i~ là giá của chuột. ~(1 \le val_i \le 10^9)~.
  • Một xâu ký tự là loại cổng của chuột, có giá trị "USB" hoặc "PS/2".

Output

In ra hai số nguyên cách nhau bởi một dấu cách:

• Số lượng máy tính được trang bị chuột.
• Tổng chi phí để mua các chuột đó.

Ví dụ

Sample Input

2 1 1
4
5 USB
6 PS/2
3 PS/2
7 PS/2

Sample Output

3 14

Cho mảng số nguyên có ~n~ phần tử và hai số nguyên dương ~k~, ~t~.

Hãy kiểm tra xem có tồn tại cửa sổ kích thước ~k~ nào của mảng ban đầu sao cho hai phần tử thuộc cửa sổ đó có độ lệch không vượt quá ~t~.

Nói cách khác, cần tìm hai chỉ số ~i~, ~j~ thuộc cùng một cửa sổ kích thước ~k~ sao cho:

~|a_i - a_j| \le t~

Ví dụ:

Mảng [1, 5, 8, 1, 5, 9], ~k = 3~, ~t = 3~ thì tồn tại cửa sổ [1, 5, 8] vì:

~|5 - 8| \le 3~

Input

• Dòng đầu tiên là số lượng test case ~T~. ~(1 \le T \le 100)~.

• Mỗi test case gồm 2 dòng:

  • Dòng thứ nhất chứa ba số nguyên ~n~, ~k~, ~t~ ~(1 \le k \le n \le 10^5,\ 1 \le t \le 2 \cdot 10^9)~.

  • Dòng thứ hai chứa ~n~ số nguyên của mảng ~( -10^9 \le a_i \le 10^9 )~.

Output

Với mỗi test case:

• In ra YES nếu tồn tại cửa sổ thỏa mãn điều kiện.
• Ngược lại in ra NO.

Ví dụ

Sample Input

1
6 3 3 
1 5 8 1 5 9

Sample Output

YES

Trên cánh đồng, bác John đặt ~n~ bố cỏ ở các vị trí khau nhau dọc trên con đường thẳng từ đầu đến cuối của cánh đồng. Để ước lượng sự phân bố số cỏ trên cánh đồng, bác hỏi Bessi ~m~ câu hỏi dạng:

Cho hai số A và B, Bessi cần trả lời cho bác biết có bao nhiêu bó cỏ nằm từ vị trí A đến vị trí B?

Input

• Dòng đầu tiên gồm hai số ~n, m (n, m \le 10^5)~ là số bó cở và số câu hỏi của bác John.
• Dòng tiếp theo chứa ~n~ số ~a_1, a_2, ..a_n~ là vị trí của ~n~ bó cỏ (~0 \le a_i \le 10^9)~
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số A, B ~(0 \le A, B \le 10^9)~là một câu hỏi của bác John.

Output

~m~ số tương ứng là câu trả lời của ~m~ câu hỏi của bác John

Ví dụ

Sample Input

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10

Sample Output

2
2
3
4
1
0

Cho một ma trận nhị phân có N hàng và M cột, một con chuột bắt đầu từ ô có tọa độ [s, t] và tìm đường đi tới ô [u, v], biết rằng ở mỗi bước con chuột có thể di chuyển từ ô hiện tại sang các ô chung cạnh với ô hiện tại và số ở ô chung cạnh là số 1.

Bạn chỉ được đi qua 1 ô đúng 1 lần hãy kiểm tra xem con chuột có thể tìm được đường đi tới ô [u, v] hay không ? Dữ liệu đảm bảo 2 ô [s, t] và ô [u, v] đều bằng 1.

Gợi ý : Loang từ ô (u, v) xem ô (s, t) có bị đi qua không, nếu có là sẽ tìm được đường đi

Ví dụ con chuột có thể đi từ ô (1, 1) tới ô (3, 6) theo đường đi được tô màu xanh

Đầu vào

Dòng đầu tiên N và M.

Dòng thứ 2 là 4 số s, t, u, v

N dòng tiếp theo mỗi dòng gồm M phân tử.

Giới hạn

~1 ≤ N, M ≤ 100~

~1 ≤ s, u ≤ N~

~1 ≤ t, v ≤ M~

Đầu ra

In ra YES nếu con chuột có thể tìm được đường đi, ngược lại in ra NO