~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ố.

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

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

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)~.

Hè đã tới, ~mrtee~ muốn cho các học sinh của mình vận động một chút. Thầy đã lập ra một cuộc thi nhảy xa, tuy nhiên điều luật của nó thì rất lạ.

Nếu chiếu trên trục ~OX~, đường nhảy sẽ bắt đầu từ điểm ~1~ và kết thúc tại điểm ~n~. Bạn sẽ xuất phát từ điểm ~0~ và được nhảy bao nhiêu lượt tùy thích, miễn là không ra khỏi phạm vi ~[1,n]~. Tuy nhiên, mỗi lượt bạn phải nhảy một quãng đường nguyên dương và ở lần nhảy thứ ~i~, bạn phải nhảy một quãng đường có độ chia hết cho ~k+i-1~. Tất nhiên, bạn sẽ được cung cấp trước ~2~ giá trị ~n~ và ~k~.

Là một ~coder~ yêu thích toán học, bạn không quan tâm tới việc thắng thua trong cuộc thi này lắm, mà chỉ hứng thú với việc đếm xem với mỗi vị trí ~i~ thuộc đoạn ~[1,n]~, có bao nhiêu cách nhảy khác nhau từ điểm xuất phát tới đó.

Hãy thử lập trình và giải đáp câu hỏi ấy!

Input

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

Output

• In ra ~n~ số nguyên, số thứ ~i~ là số cách để nhảy từ điểm ~0~ tới điểm ~i~, vì kết quả có thể rất lớn nên hãy lấy phần dư với modulo ~10^9+7~.
  
  

Constraints

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

Subtasks

• ~35\%~ số điểm: ~n \le 300~.
• ~40\%~ số điểm: ~n \le 4000~.
• ~25\%~ số điểm: ~n \le 2*10^5~.
  
  

Sample Test 1

Input:

12 1

Output:

1 1 2 2 3 4 5 6 8 10 12 15

Sample Test 2

Input:

15 3

Output:

0 0 1 0 0 1 1 0 1 1 1 2 1 1 3

Giải thích

• Ở ví dụ ~1~, các cách để đến điểm ~6~ là ~[0,6],[0,4,6],[0,2,6],[0,1,3,6]~.
• Ở ví dụ ~2~, các cách để đến điểm ~15~ là ~[0,15],[0,3,12],[0,6,10,15]~

Có ~n~ điểm từ ~1~ tới ~n~ trên trục tọa độ ~OX~. Điểm thứ ~i~ có màu ~c_i~.

Tại điểm ~i~, bạn có thể:

• Đi tới điểm ~i+1~ (nếu ~i \neq n~), tốn ~R~ giây.
• Đi tới điểm ~i-1~ (nếu ~i \neq 1~), tốn ~L~ giây.
• Tốc biến tới điểm ~j~ (nếu ~c_i = c_j~), tốn ~C~ giây.

Cho ~2~ điểm ~st~ và ~en~, hãy tính thời gian ngắn nhất để đi từ ~st~ đến ~en~.

Input

• Dòng thứ nhất chứa ~4~ số nguyên dương ~n,L,R,C~.
• Dòng thứ hai gồm ~2~ số nguyên dương ~st~ và ~en~. ~(1 \le st \le en \le n)~
• Dòng thứ ba chứa ~N~ số nguyên dương ~c_1, c_2, ..., c_n~ là màu của từng điểm.

Output

• In ra thời gian ngắn nhất để đi từ ~st~ đến ~en~.

Constraints

• ~1 \le n \le 10^5~.
• ~1 \le L,R,C \le 10^9~.
• ~1 \le c_i \le 10^5~.

Sample Input 1:

5 1 2 3
1 5
1 2 1 1 2

Sample Output 1:

5

Sample Input 1:

5 1 4 3
3 5
1 2 1 1 2

Sample Output 1:

4

Subtasks

• Subtask ~1~: ~n \le 1000~ ~(50\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(50\%)~

Ở một vương quốc nọ có ~n~ thành phố, được đánh số từ ~1~ đến ~n~. Mạng lưới giao thông của vương quốc gồm ~m~ con đường, con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với độ dài đúng bằng ~1~ ki-lô-mét.

Có ~k~ dự án nhà máy điện đang được triển khai, dự án thứ ~j~ sẽ xây một nhà máy điện đặt tại thành phố ~p_j~, cung cấp điện cho tất cả các thành phố nằm trong bán kính ~r_j~ ki-lô-mét (giả sử rằng quãng đường di chuyển trong nội thành là bằng ~0~). Nhà vua đang băn khoăn, những thành phố nào đã được cấp điện, và những thành phố nào chưa được cấp điện? Hãy giúp nhà vua giải quyết bài toán này nhé.

Input

Dòng đầu chứa ba số nguyên ~n~, ~m~, ~k~ (~2 \le n, m \le 2 \times 10^5~; ~0 \le k \le 5 \times 10^5~).

~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i~, ~v_i~ (~1 \le u_i, v_i \le n~; ~u_i \ne v_i~) mô tả con đường thứ ~i~.

~k~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~p_j~, ~r_j~ (~1 \le p_j \le n~; ~0 \le r_j \le 10^9~) mô tả dự án thứ ~j~.

Output

Gồm một dòng duy nhất chứa một xâu nhị phân gồm ~n~ kí tự, kí tự thứ ~i~ bằng "1" nếu thành phố thứ ~i~ đã được cấp điện, ngược lại kí tự thứ ~i~ bằng "0" nếu thành phố thứ ~i~ chưa được cấp điện.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~n, m \le 1000~.
• Subtask ~2~ (~30\%~ số điểm): ~r_1 = r_2 = \dots = r_{k - 1} = r_k~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input 1

4 3 1
1 2
1 3
2 4
2 1

Output 1

1101

Input 2

6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
6 0
3 1

Output 2

101111