Cho hai số tự nhiên ~A~ và ~N~. Hãy tìm số tự nhiên ~B~ sao cho ~A \times B = N~.

Input

• Dòng đầu tiên gồm một số tự nhiên ~A~ (~0 \le A \le 100~).
• Dòng thứ hai gồm một số tự nhiên ~N~ (~0 \le N \le 100~).

Output

In ra số tự nhiên ~B~ thỏa mãn. Nếu không có số tự nhiên thỏa mãn, in ra NA.

Ví dụ

Input 1

2
6

Output 1

3

Input 2

7
10

Output 2

0

Cho một số tự nhiên ~N~. Hỏi có thể tách ~N~ thành tổng hai số lẻ khác nhau được không?

Input

Gồm một số tự nhiên ~N~ (~0 < N \le 10^9~).

Output

In ra YES khi có thể tách được ~N~ thỏa mãn yêu cầu đề bài, ngược lại in ra NO.

Ví dụ

Input 1

6

Output 1

YES

Input 2

7

Output 2

NO

Giải thích

Ở ví dụ 1, ~6 = 5 + 1~.

Cho dãy số ~A~ có quy luật như sau: ~1, 2, 4, 5, 7, 8, \ldots~

Cho hai số tự nhiên ~L~ và ~R~, hãy tính tổng các số trong dãy số ~A~ mà lớn hơn ~L~ và nhỏ hơn ~R~.

Input

• Dòng đầu tiên gồm một số tự nhiên ~L~ (~0 < L \le 10^9~).
• Dòng thứ hai gồm một số tự nhiên ~R~ (~L < R \le 10^9~).

Output

In ra một số tự nhiên là chữ số cuối cùng của kết quả tìm được.

Scoring

• Subtask 1 (60% số điểm): ~R \le 10^3~.
• Subtask 2 (40% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

1
10

Output

6

Giải thích

~2 + 4 + 5 + 7 + 8 = 26~.

Số trùng là số tự nhiên được tạo bởi chỉ đúng một chữ số, ví dụ: ~1, 3333, 5, 888888, \ldots~

Cho một số tự nhiên ~N~, hỏi có bao nhiêu số trùng nhỏ hơn ~N~.

Input

Gồm một số tự nhiên ~N~ (~0 \le N \le 10^9~).

Output

In ra một số tự nhiên là kết quả của bài toán.

Scoring

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

Ví dụ

Input

25

Output

12

Giải thích

Các số thỏa mãn là: ~0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22~.

Bạn được cho một số nguyên dương ~P~. Nhiệm vụ của bạn là dựng một hình chữ nhật có các cạnh mang độ dài nguyên dương và có chu vi đúng bằng ~P~ sao cho diện tích của nó là lớn nhất có thể.

Input

Gồm một dòng duy nhất chứa số nguyên dương ~P~ (~3 \le P \le 10^9~) là chu vi của hình chữ nhật cần tìm.

Output

Nếu có thể dựng được hình chữ nhật thỏa mãn, hãy in ra diện tích lớn nhất có thể của hình chữ nhật đó. Ngược lại, nếu không thể dựng được hình chữ nhật, hãy in ra ~-1~.

Ví dụ

Input 1

8

Output 1

4

Input 2

3

Output 2

-1

Giải thích

Ở ví dụ 1, dựng hình chữ nhật với chiều dài và chiều rộng đều bằng ~2~, khi đó diện tích bằng ~4~. Đây là diện tích lớn nhất có thể thu được.

Ở ví dụ 2, do bài toán yêu cầu cạnh có độ dài dương, không có cách nào để dựng lên một hình chữ nhật có chu vi bằng ~3~.

Từ dãy số tự nhiên ~1, 2, 3, \ldots, N~, người ta sắp xếp lại dãy số này theo số dư trong phép chia các số hạng của dãy số cho một số tự nhiên ~K~ là ước của ~N~ như sau:

• Đoạn thứ nhất gồm tất cả các số chia hết cho ~K~.
• Đoạn thứ hai gồm tất cả các số chia ~K~ dư ~1~.
• Đoạn thứ ba gồm tất cả các số chia ~K~ dư ~2~.
• ...
• Đoạn cuối cùng gồm tất cả các số chia ~K~ dư ~K - 1~.

Các số hạng trong mỗi đoạn cũng được sắp xếp theo chiều tăng dần.

Ví dụ: Với ~N = 12~ và ~K = 4~, sau khi sắp xếp ta có dãy số:

~4, 8, 12, 1, 5, 9, 2, 6, 10, 3, 7, 11~.

Cho trước ba số nguyên dương ~N, K, M~ với ~K~ là ước của ~N~ và ~M < N~. Hãy tìm số hạng thứ ~M~ của dãy đã sắp xếp.

Input

Gồm ba số nguyên dương ~N, K, M~ (~N \le 10^{16}; K \le 10^9; K~ là ước của ~N; M < N~) trên cùng một dòng, mỗi số cách nhau một dấu cách.

Output

Ghi ra số hạng thứ ~M~ của dãy số theo yêu cầu.

Scoring

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

Ví dụ

Input

12 4 2

Output

8

Bạn được cho một xâu ~S~ có độ dài ~n~ gồm các chữ cái từ a đến z. Nhiệm vụ của bạn là đếm số xâu con liên tiếp mà mỗi cặp kí tự đặc biệt trong xâu con đó có khoảng cách không nhỏ hơn ~k~ (~k \le n~).

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, m, k~ (~1 \le k \le n \le 10^5; 1 \le m \le 10~), lần lượt là độ dài của xâu ~S~, số lượng kí tự đặc biệt và khoảng cách yêu cầu giữa hai kí tự đặc biệt bất kì.
• Dòng thứ hai chứa xâu ~S~ gồm các chữ cái từ a đến z.
• Dòng cuối cùng gồm ~m~ kí tự là các kí tự đặc biệt, dữ liệu đảm bảo các kí tự này phân biệt.

Output

Gồm một dòng duy nhất là số lượng xâu con liên tiếp thỏa mãn đề bài.

Scoring

• Subtask 1 (30% số điểm): ~1 \le k \le n \le 10^3~.
• Subtask 2 (20% số điểm): ~1 \le k \le n \le 10^5~, trong xâu chỉ có đúng ~2~ vị trí có kí tự đặc biệt.
• Subtask 3 (50% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

6 2 2
acbabc
a b

Output

10

Giải thích

Các xâu con thỏa mãn là: a, c, b, a, b, c, ac, acb, cb, bc.

Cho xâu nhị phân ~s~ độ dài ~n~. Bạn được thực hiện các thao tác sau bao nhiêu lần tùy ý:

• Xóa ~x~ số 0 kề nhau.
• Xóa ~y~ số 1 kề nhau.
• Đổi vị trí ~2~ số 0 và 1 liền kề.

Đếm xem sau một số hữu hạn các thao tác (có thể không thực hiện bất cứ thao tác nào), có bao nhiêu xâu nhị phân độ dài ~m~ khác nhau có thể được tạo ra. Hai xâu nhị phân khác nhau khi chúng có một vị trí mà ở xâu này là 0 nhưng xâu còn lại là 1.

Input

• Dòng đầu tiên chứa bốn số nguyên ~n, m, x, y~ (~1 \le m \le n \le 2 \times 10^5; 0 \le x, y \le n~).
• Dòng thứ hai chứa xâu nhị phân ~s~.

Output

In ra một số nguyên duy nhất là kết quả của bài toán chia lấy dư cho ~10^9 + 7~.

Scoring

• Subtask 1 (25% số điểm): ~n = m~.
• Subtask 2 (25% số điểm): ~n \le 20~.
• Subtask 3 (25% số điểm): ~n \le 2000~.
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

5 3 1 2
00011

Output

4

Cho dãy ~z~ gồm ~n~ phần tử, được đánh số từ ~1~ đến ~n~. Hãy đếm xem có bao nhiêu bộ bốn số ~(a, b, c, d)~ thỏa mãn ~1 \le a \le b < c \le d \le n~ và không có số nào xuất hiện trong cả hai đoạn ~(z_a, z_{a+1}, \ldots, z_b)~ và ~(z_c, z_{c+1}, \ldots, z_d)~.

Input

Dòng đầu tiên chứa số nguyên ~t~ là số lượng bộ dữ liệu (~1 \le t \le 50~). Mỗi bộ dữ liệu được miêu tả như sau:

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 1000~).
• Dòng tiếp theo chứa ~n~ số nguyên ~z_1, z_2, \ldots, z_n~ (~1 \le z_i \le 10^9~).

Output

Với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa số lượng bộ bốn số ~(a, b, c, d)~ thỏa mãn điều kiện đề bài.

Scoring

• Subtask 1 (20% số điểm): ~t = 1, 1 \le n \le 20~.
• Subtask 2 (20% số điểm): ~t \le 5, 1 \le n \le 300~.
• Subtask 3 (30% số điểm): ~t \le 5~.
• Subtask 4 (30% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

2
3
1 2 5
4
2 3 2 3

Output

5
4

Giải thích

• Với bộ dữ liệu đầu tiên, tất cả các bộ số đều thỏa mãn.
• Với bộ dữ liệu thứ hai, các bộ số thỏa mãn là ~(1,1,2,2), (1,1,4,4), (2,2,3,3), (3,3,4,4)~.

Cơ quan an ninh Trái Đất cần phải tiêu diệt tàu vũ trụ của người ngoài hành tinh để bảo vệ hòa bình cho Trái Đất. Tàu vũ trụ hiện đang hạ cánh trên sa mạc Sahara để thực hiện việc cướp nhiên liệu. May thay, đây là một trận địa đã được chuẩn bị trước đó của người Trái Đất.

Tàu vũ trụ được xây dựng từ các khối lập phương đơn vị kích thước ~1 \times 1 \times 1~ xếp chồng lên nhau, và lớp dưới cùng có dạng hình chữ nhật ~m \times n~.

Trận địa được bao phủ bởi rất nhiều máy bắn tia laser để phá hủy con tàu. Súng laser được lắp đặt ở bốn phía của tàu vũ trụ, và chúng định kì bắn tia laser vào một số khối của con tàu. Mỗi tia luôn vuông góc với các mặt của tàu vũ trụ và phá hủy ~r~ khối đầu tiên trên đường đi của nó. Nếu có một hoặc nhiều khối trên đỉnh của khối bị phá hủy, chúng sẽ di chuyển xuống.

Sau khi bắn ~k~ phát, cơ quan an ninh quyết định thực hiện một cuộc không kích diện rộng. Họ chọn khu vực có kích thước ~p \times p~ trên con tàu sao cho số lượng khối lập phương đơn vị bị phá hủy là nhiều nhất có thể. Cuộc không kích sẽ phá hủy tất cả các khối trong khu vực này.

Hãy tìm số lượng khối tối đa bị phá hủy bởi cuộc không kích phạm vi ~p \times p~ sau ~k~ phát bắn laser.

Input

• Dòng thứ nhất chứa năm số nguyên ~m, n, r, k, p~ (~1 \le m \times n \le 10^6; 1 \le r \le 10; 1 \le k \le 3 \times 10^5; 1 \le p \le \min(m, n, 10)~).
• ~m~ dòng tiếp theo, mỗi dòng chứa ~n~ số; số ở dòng thứ ~i~, cột thứ ~j~ là ~a_{i,j}~, số khối lập phương đơn vị được xếp chồng lên nhau ở vị trí ~(i, j)~ (~1 \le a_{i,j} \le 10^6~).
• ~k~ dòng tiếp theo mô tả các phát bắn laser, có dạng dir i h:
  • dir là một trong bốn chữ cái: W - hướng Tây, E - hướng Đông, S - hướng Nam, N - hướng Bắc.
  • ~i~ là một số nguyên dương; nếu hướng bắn là hướng Đông hoặc hướng Tây thì đây là chỉ số dòng, nếu hướng bắn là hướng Nam hoặc hướng Bắc thì đây là chỉ số cột bị bắn.
  • ~h~ là độ cao của phát bắn.

Output

Một dòng chứa một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask 1 (30% số điểm): ~n, Q \le 100~
• Subtask 2 (70% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

4 8 2 6 2
1 1 1 1 1 1 1 1
1 2 3 1 1 1 3 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
N 2 2
W 2 2
W 2 3
E 2 1
S 4 1
S 7 1

Output

6