Chúng ta đã quá rõ việc một số nguyên tố (prime) là số nguyên dương lớn hơn ~1~ có duy nhất hai ước là ~1~ và chính nó. Để làm mới bài toán, hôm nay, ta sẽ định nghĩa một số TPrime là một số nguyên dương lớn hơn ~1~ gồm đúng ~3~ ước.

Cho ~n~ truy vấn, mỗi truy vấn là một số ~a~, hãy kiểm tra xem số này có phải là số TPrime hay không.

Input

• Dòng ~1~ ghi số nguyên dương ~n~ ~(1 \le n \le 3*10^5)~
• ~n~ dòng sau, mỗi dòng gồm một số nguyên dương ~a~ ~(1 \le a \le 10^{12})~ miêu tả truy vấn.

Output

• In ra ~n~ dòng, với mỗi truy vấn, nếu ~a~ là số TPrime thì in ra "YES", ngược lại in ra "NO".

Subtask

• Có ~20\%~ số test ứng với ~1 \le n \le 100, 1 \le a \le 10^4~
• Có ~30\%~ số test ứng với ~1 \le n,a \le 10^5~
• Có ~50\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

3
4
6
7

Sample Output 1

YES
NO
NO

Với hai số nguyên dương ~u,v~, khi viết số ~v~ sau số ~u~ ta được một số mới.

Ví dụ: ~u = 99, v = 123~, khi viết số ~v~ sau ~u~ ta thu được số mới là số ~99123~.

Cho ~n~ số nguyên dương ~a_1, a_2, a_3, ... a_n~ và ~m~ số nguyên dương ~b_1, b_2, b_3, ..., b_m~.

Yêu cầu:

• Với mỗi giá trị ~b_i~ ~(1 \le i \le m)~, bạn hãy cho biết có bao nhiêu số ~a_j~ (~1 \le j \le n~) sao cho sau khi viết ~a_j~ sau ~b_i~ ta được một số mới chia hết cho ~3~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,m~. (~1 \le n,m \le 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên dương miêu tả dãy ~a~. (~a_i \le 10^8, 1 \le i \le n~).
• Dòng tiếp theo chứa ~m~ số nguyên dương miêu tả dãy ~b~. (~b_i \le 10^8, 1 \le i \le m~).

Output

• Gồm ~m~ dòng, dòng thứ ~i~ ghi số lượng số ~a_j (1 \le j \le n)~ sao cho sau khi viết ~a_j~ sau ~b_i~ ta được một số mới chia hết cho ~3~.

Subtask

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

Sample Input 1

5  2
123  4  5  7  10
3  2

Sample Output 1

1
3

Explanation 1

~b_1 = 3~ chỉ có duy nhất một số ~a_1~ thỏa mãn. ~b_2 = 2~, có ba số ~a_2,a_4,a_5~ thỏa mãn.

~ABC~ là một thầy giáo dạy toán nổi tiếng, đối với thầy, chỉ có hai loại số duy nhất là số nguyên tố và hợp số. Lớp học của thầy gồm ~n~ học sinh được đánh thứ tự từ ~1~ tới ~n~. Học sinh thứ ~i~ có mã số là ~a_i~ ~(1≤a_i≤3×10^5)~. Chú ý rằng ở đây các bạn học sinh không nhất thiết là có mã số khác nhau.

Một ngày nọ, thầy đến lớp và mang theo vô số viên kẹo. Thầy sẽ có ~q~ lượt phát kẹo, ở mỗi lượt thầy sẽ chọn một số nguyên dương ~t~ ~(1≤t≤2)~ và ba số nguyên dương ~l,r,v (1≤l≤r≤n; 1≤ v≤10^9)~. Thầy sẽ đi phát cho tất cả các bạn học sinh có số thứ tự ~i~, sao cho ~i∈[l,r]~, đúng ~v~ viên kẹo mỗi bạn. Tuy nhiên, thầy bỗng thấy cách chia kẹo này không thú vị, và quyết định rằng nếu ~t=1~, thầy sẽ chỉ phát kẹo cho các bạn thỏa mãn điều kiện vừa rồi đồng thời mã số ~a_i~ của bạn ấy là số nguyên tố. Ngược lại, nếu ~t=2~, thầy sẽ chỉ đi phát kẹo cho các bạn với mã số ~a_i~ là hợp số.

Sau ~q~ lượt phát kẹo, thầy muốn biết mỗi bạn học sinh có số kẹo là bao nhiêu. Do thầy chỉ dạy toán chứ không phải tin, thầy muốn nhờ các bạn lập trình tính hộ số kẹo của từng bạn.

Lưu ý ở đây ta tạm coi ~1~ là hợp số.

Input

-Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1≤ n,q≤10^5)~; -Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,…,a_n~ miêu tả mã số học sinh từ ~1~ tới ~n~. -~q~ dòng sau, mỗi dòng gồm bốn số nguyên dương ~t,l,r,val (1 \le t \le 2; 1≤l \le r≤10^5; 1 \le val≤10^9)~.

Output

• In ra một dòng ~n~ số nguyên dương là số kẹo của từng bạn học sinh.

Subtask

• Có ~20\%~ số test tương ứng với số điểm có ~n,q \le 100~
• Có ~30\%~ số test khác tương ứng với số điểm có ~n,q \le 10^4~
• Có ~30\%~ số test còn lại tương ứng với số điểm có: ~a_i~ đều là số nguyên tố.
• Có ~20\%~ số test còn lại tương ứng với số điểm không có giới hạn gì thêm.

Ví dụ

Input 1

6 3
1 2 4 3 7 10
1 2 5 2
2 1 6 1
2 5 5 4

Output 1

1 2 1 2 2 1

Giải thích 1

Ở lượt đầu tiên, ta chỉ phát kẹo cho các học sinh trong đoạn ~[2,5]~ với mã số là số nguyên tố, đó là ba bạn thứ ~2,4,5~.

Ở lượt thứ hai, ta phát kẹo cho các bạn trong đoạn ~[1,6]~ với mã số là hợp số, đó là các vị trí ~1,3,6~.

Ở lượt thứ ba, ta không thể phát kẹo cho bạn thứ ~5~ vì mã số của bạn là ~7~, đó không phải hợp số.

Mít có các que tính có nhiều độ dài và màu sắc. Hôm nay học về hình tam giác nhọn, Mít đã nghĩ ra một bài toán rất độc đáo có liên quan tới tam giác nhọn và các que tính của mình. Mít chia các que tính thành ~N~ bộ, các que tính trong cùng một bộ thì có độ dài bằng nhau nhưng có màu khác nhau. Độ dài của các que tính trong hai bộ bất kì là khác nhau. Mít đố các bạn đếm xem có bao nhiêu tam giác nhọn khác nhau có thể được tạo ra từ ~N~ bộ que tính đó. Chú ý: mỗi cạnh của tam giác được chọn từ một bộ que tính khác nhau tức là sẽ không có tam giác cân và hai tam giác nhọn được gọi là giống nhau khi các cặp cạnh tương ứng bằng nhau và cùng màu, ngược lại là khác nhau.

Yêu cầu: Cho độ dài và số lượng các que tính của ~N~ bộ que tính, hãy lập trình đếm số lượng tam giác nhọn khác nhau có thể tạo ra.

Dữ liệu vào từ tệp văn bản TRIACU.INP:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 2000)~ là số bộ que tính;
• ~N~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~L, C~ mô tả độ dài và số lượng que tính của bộ thứ ~i~ ~(1 ≤ i ≤ N~; ~\ L ≤ 10^6~; ~\ C ≤ 10^3)~.

Kết quả ghi ra tệp văn bản TRIACU.OUT:

Một số nguyên duy nhất là số lượng tam giác nhọn khác nhau.

Ràng buộc

• Có ~50\%~ số test ứng với ~N ≤ 200~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

4
3 3
4 1
5 2
6 2

Output

4

Giải thích

Có ~4~ tam giác nhọn có thể tạo ra từ bộ que tính thứ ~2, 3, 4~.

Cho dãy số gồm ~n~ số nguyên ~a_1, a_2, …, a_n~ và ~2~ số nguyên không âm ~L, R (L ≤ R)~.

Yêu cầu: Đếm số cặp ~(i, j)~ thỏa mãn điều kiện: ~i ≤ j~ và ~L ≤ |a_i+…+a_j| ≤ R~.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~n, L, R~ ~(n ≤ 3*10^5 ; 0 ≤ L ≤ R ≤ 10^9)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2,…, a_n (|a_i|≤ 10^9)~

Output

• Một số nguyên duy nhất là số lượng cặp ~(i, j)~ đếm được.

Subtask

• Subtask 1 (~30\%~ số điểm): ~n \le 10^3~.
• Subtask 2 (~50\%~ số điểm): ~n \le 10^5~ và ~a_i \ge 0~.
• Subtask 3 (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Test

Input

3 0 1
1 -1 2

Output

4

Có ~n~ người xếp hàng mua vé một trận bóng theo thứ tự ~1~ đến ~n~. Mỗi người cần mua một vé, nhưng người bán vé lại có thể bán cho mỗi người tối đa hai vé. Do đó, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ~t_i~ là thời gian cần thiết để người thứ ~i~ mua vé cho mình. Nếu người thứ ~i+1~ rời hàng và nhờ người ~i~ mua hộ vé thì mất ~r_i~ thời gian để mua cho cả hai.

Hãy xác định thời gian mua vé nhỏ nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 6 \times 10^4)~
• Dòng thứ hai chứa ~n~ số nguyên dương miêu tả dãy ~t_1, t_2, ..., t_n~ ~(t_i \le 30000)~
• Dòng thứ ba chứa ~n-1~ số nguyên dương miêu tả dãy ~r_1, r_2, ..., r_{n-1}~ ~(r_i \le 30000)~

Output

• In ra thời gian ít nhất để mua vé cho ~n~ người.

Sample Test

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Trên dãy số nguyên ~a_1,a_2,...,a_n~ và với hai số nguyên ~w_1,w_2~, ta định nghĩa một bộ năm chỉ số ~1 \le i_1 < i_2 < ... < i_5 \le n~ được gọi là bộ năm và có trọng số được tính bằng: ~(w_1 \times a_{i_1}) + (w_2 \times a_{i_2}) + a_3 + (w_2 \times a_{i_4}) + (w_1 \times a_{i_5})~.

Ví dụ, trên dãy gồm ~7~ số nguyên ~2,8,1,9,1,-1,8~ và ~w_1 = 1~, ~w_2 = -1~ thì bộ năm chỉ số ~2,3,4,6,7~ là một bộ năm có trọng số bằng ~(1 \times 8) + (-1 \times 1) + 9 + (-1 \times (-1)) + (1 \times 8) =25~, đây cũng là bộ năm có trọng số lớn nhất trong tất cả các bộ năm.

Yêu cầu: Cho dãy số ~a_1,a_2,...,a_n~ và hai số nguyên ~w_1~ và ~w_2~. Hãy tìm bộ năm có trọng số lớn nhất.

Input

• Dòng đầu chứa ba số nguyên ~n,w_1,w_2~ ~(5 \le n \le 10^5; |w_1|, |w_2| \le 100)~
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(|a_i| \le 10^9)~.

Output

• Gồm một số nguyên là trọng số của bộ năm lớn nhất tìm được.

Subtask

• Có ~20\%~ số test ứng với ~1 \le n \le 100~
• Có ~20\%~ số test ứng với ~w_1 = w_2 = 0~
• Có ~20\%~ số test ứng với ~n \le 5000, w_1 = 0~
• Có ~20\%~ số test ứng với ~w_1 = 0~
• Có ~20\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

7 1 -1
2 8 1 9 1 -1 8

Sample Output 1

25

Sample Input 2

7 0 0
2 8 1 9 1 -1 8

Sample Output 2

9

Sau khi chơi với ngọc chán chê, Tí sắp ~n~ viên ngọc ra một đường thẳng và bắt đầu nhìn ngắm chúng. Tí nhận thấy rằng có không quá ~k~ màu ngọc khác nhau trên bàn và viên ngọc thứ ~i~ từ trái sang thì có màu ~a_i~. Tí muốn chia dãy ngọc thành các đoạn liên tiếp sao cho mỗi đoạn đều có đủ ~k~ màu. Hỏi Tí có bao nhiêu cách chia thỏa mãn như vậy?

Yêu cầu: In số cách chia thỏa mãn sau khi ~\mod 10^9+7~

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,k~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~.

Output

• Ghi ra một số nguyên là kết quả bài toán.

Constraints

• ~1\leq k\leq n\leq 10^6~
• ~1\leq a_i\leq k~

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~k = 1~.
• Subtask ~2~ (~20\%~ số điểm): ~n\leq 5000~.
• Subtask ~3~ (~20\%~ số điểm): ~n\leq 10^5, k\leq 100~.
• Subtask ~4~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Example

Sample Input ~1~

5 2
1 2 2 1 2 

Sample Ouput ~1~

3

Explanation

Có ~3~ cách chia như sau: ~(1\ 2) | (2\ 1\ 2), (1\ 2\ 2) | (1\ 2)~, hoặc ~(1\ 2\ 2\ 1\ 2)~.

Đất nước ~ABC~ gồm ~n~ thành phố, có ~m~ con đường hai chiều với độ dài là ~1~ nối giữa một cặp thành phố. Có ~k~ khách du lịch, vị khách thứ ~i~ đang ở thành phố ~a_i~. Hiện đang có một sự kiện xảy ra ở thành phố ~b~, với mỗi khách du lịch, hãy in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện này.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n,m,k~.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u~ và ~v~ miêu tả con đường ~(u,v)~.
• Dòng tiếp theo gồm ~k~ số nguyên dương miêu tả thành phố mà vị khách thứ ~i~ đang ở.
• Dòng cuối cùng chứa số nguyên dương ~b~ - thành phố nơi diễn ra sự kiện.

Output

• Với mỗi vị khách, in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện. Nếu không có đường đi thì in ra -1.

Điều kiện

• ~ 1 \le n,m,k \le 2*10^5~.

Subtask

• ~50\%~ số điểm: ~n,m,k \le 1000~.
• ~50\%~ số điểm: Không giới hạn gì thêm.

Ví dụ

Input 1:

4 3 3
1 2 
2 3
3 4
1 2 3
4

Output 1:

3 2 1

Input 2:

5 4 3
1 2
2 3
3 1
4 5
1 2 5
3

Output 2:

1 1 -1

Cho một cây vô hướng gồm ~n~ đỉnh ~(1 \le n \le 1e5)~ và ~m~ đỉnh đặc biệt ~(1 \le m \le n)~, kèm một số ~k~ nguyên dương bất kì ~(1 \le k \le n)~. Một đỉnh ~u~ được gọi là tốt nếu như với mọi đỉnh ~v~ thuộc tập ~m~ đỉnh đặc biệt, ta luôn có ~dist(u,v) \le k~. Ở đây, ~dist(u,v)~ là khoảng cách của đỉnh ~u~ và ~v~ trên cây, hay bằng số cạnh trên đường đi ngắn nhất từ đỉnh ~u~ tới đỉnh ~v~. Hãy đếm xem có bao nhiêu đỉnh được coi là "tốt".

Input:

• Dòng đầu gồm 3 số ~n,m,k. (1 \le m \le n \le 10^5, 1 \le k \le 10^5).~
• ~n-1~ dòng sau mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ là cạnh nối từ đỉnh ~u~ tới ~v~.
• Dòng cuối gồm ~m~ số miêu tả các đỉnh đặc biệt.

Output:

• Số đỉnh tốt.

Sample Test

Input:

6 2 3 
1 5 
2 3 
3 4 
4 5 
5 6
1 2

Output:

3

Giải thích:

• 3 đỉnh tốt là đỉnh 3,4,5.

Ràng buộc

• Subtask 1: ~n <= 500.~ (50%)
• Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
• Subtask 3: Không giới hạn gì thêm. (20%).

Cho một đồ thị vô hướng có dạng cây, tức là đồ thị gồm ~n~ đỉnh và ~n-1~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~n~, đỉnh thứ ~i~ có trọng số là ~w_i~.

Chắc hẳn các bạn đều biết khái niệm về cây con, giả sử ta có một cây có gốc là ~1~ như sau:

• Cây con có gốc là ~2~ sẽ bao gồm các đỉnh : ~\{2,6,5,4\}~.
• Cây con có gốc là ~3~ sẽ bao gồm các đỉnh : ~\{3\}~.

Ta định nghĩa ~S(root,a)~ là tổng trọng số các đỉnh trong cây con gốc ~a~ khi gốc của cây là ~root~. Hay ~S(root,a) = \sum_u^{u \in subtree(a)} w[u]~ khi gốc của cây là ~root~.

Bạn cần trả lời ~q~ câu hỏi, mỗi câu hỏi có dạng như sau:

• ~a~ ~b~ : Hãy in ra ~S(a,b)~.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~ ~(n,q \le 2 \times 10^5)~ miêu tả số đỉnh và số truy vấn.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~w~ ~(1 \le w_i \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~u_i~ và ~v_i~ miêu tả cạnh ~(u_i,v_i)~ của cây ~(1 \le u_i,v_i \le n)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~a_i,b_i~ ~(1 \le a_i,b_i \le n)~ miêu tả truy vấn tương ứng.

Output:

• Với mỗi truy vấn, in ra đáp án tương ứng.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~n,q \le 2000~
• Subtask ~2~ (~25\%~ số điểm): ~a_i = 1~ với mọi truy vấn.
• Subtask ~3~ (~25\%~ số điểm): ~b_i = 1~ với mọi truy vấn.
• Subtask ~4~ (~25\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

6 4
1 3 2 1 4 2
1 3
2 4
1 2
2 6
6 5
1 2
1 6
4 2
2 1

Sample Output 1

10
6
12
3

Explanation 1

Đối với hai truy vấn đầu tiên, gốc của cây bằng ~1~.

• ~S(1,2) = w[2] + w[6] + w[5] + w[4] = 10~
• ~S(1,6) = w[6] + w[5] = 6~

Đối với truy vấn thứ ba, gốc của cây bằng ~4~:

• ~S(4,2) = w[2] + w[6] + w[5] + w[1] + w[3] = 12~

Đối với truy vấn thứ tư, gốc của cây bằng ~2~

• ~S(2,1) = w[1] + w[3] = 3~