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

Alyona có con số yêu thích là ~k~ và vì cô còn nhỏ, ~k~ không vượt quá ~10~. Giờ đây, cô muốn chọn ~k~ chuỗi con không rỗng của chuỗi ~s~ sao cho các chuỗi này xuất hiện dưới dạng chuỗi con không giao nhau của chuỗi ~t~ và theo đúng thứ tự như trong chuỗi ~s~. Cô cũng quan tâm đến việc độ dài của chúng là lớn nhất có thể trong tất cả các biến thể.

Bạn cần tìm ~k~ chuỗi con không giao nhau và có thể rỗng trên dãy ~s~ (các chuỗi con cần liên tiếp nhau), sao cho cũng tồn tại ~k~ chuỗi con không giao nhau và có thể rỗng trên dãy ~t~ có giá trị tương tự. Bạn cần chọn ra ~k~ dãy con sao cho tổng độ dài của chúng là lớn nhất.

Note: Bạn toán này quy về đơn giản là bài toán LCS, nhưng thay vì mỗi phần tử ta lấy một kí tự, thì là lấy một đoạn con.

Input:

• Dòng đầu tiên chứa ba số nguyên dương ~n~, ~m~, ~k~ ~(1 \leq n, m \leq 1000, 1 \leq k \leq 10)~, lần lượt là độ dài của chuỗi ~s~, độ dài của chuỗi ~t~, và số yêu thích của Alyona.
• Dòng thứ hai chứa chuỗi ~s~, bao gồm các chữ cái tiếng Anh viết thường.

• Dòng thứ ba chứa chuỗi ~t~, bao gồm các chữ cái tiếng Anh viết thường.

  Output:

• In ra một số nguyên không âm duy nhất — tổng độ dài của các chuỗi trong dãy mong muốn.

Ví dụ

Input 1

5 5 1
abcde
bcdea

Output 1

4

Trên lưới ô vuông gồm ~𝑚~ dòng và ~𝑛~ cột. Các dòng được đánh số từ 1 đến ~𝑚~ từ trên xuống dưới, các cột được đánh số từ 1 đến ~𝑛~ từ trái sang phải. Ô nằm giao giữa dòng ~𝑖~ và cột ~𝑗~ gọi là ô (~𝑖,𝑗~). Ban đầu, tại thời điểm 0, máy tính sẽ đặt ~𝑘~ robot trên lưới, robot thứ ~𝑟~ (~𝑟 =1,2, … , 𝑘~) được đặt ở ô (~𝑥_𝑟, 𝑦_𝑟~), các ô khác của lưới có thể đặt vật cản hoặc không. Mỗi đơn vị thời gian, người chơi phải điều khiển di chuyển một số con robot trong ~𝑘~ robot (có thể không điều khiển con nào). Robot chỉ thực hiện di chuyển sang một trong các ô kề cạnh hoặc kề đỉnh với ô robot đang đứng và ô đó không có vật cản, việc di chuyển này mất đúng một đơn vị thời gian.

Nhiệm vụ của người chơi là di chuyển để ~𝑘~ robot gặp nhau là sớm nhất, ~𝑘~ robot được gọi là gặp nhau nếu chúng cùng đứng trong một ô. Để trò chơi thêm thú vị, nếu ô (~𝑖,𝑗~) có vật cản thì ở thời điểm ~𝑑_{𝑖𝑗}~ vật cản sẽ biến mất và robot có thể đi vào ô (~𝑖,𝑗~) tính từ thời điểm ~𝑑_{𝑖j}~

Input

• Dòng đầu tiên chứa 3 số ~𝑚, 𝑛, 𝑘~ (~𝑚 \times 𝑛 \leq 5000~);
• Dòng thứ ~𝑖~ trong ~𝑚~ dòng tiếp theo chứa ~𝑛~ số nguyên, số thứ ~𝑗~ trong dòng nhận giá trị 0 mô tả ô (~𝑖,𝑗~) không có vật cản, hoặc -1 mô tả ô (~𝑖,𝑗~) có đặt robot, hoặc một số nguyên dương ~𝑑_{𝑖𝑗}~ mô tả ô (~𝑖,𝑗~) có vật cản và ~𝑑_{𝑖𝑗}~ là thời điểm vật cản ở ô đó biến mất (~𝑑_{𝑖𝑗} \leq 10^9~).

Output

• Gồm một dòng chứa một số nguyên là thời điểm sớm nhất mà ~𝑘~ robot gặp nhau, nếu không tồn tại cách di chuyển ghi -1.

Scoring

• Subtask ~1~ (~25\%~ số điểm): ~𝑘 = 2~ và không có ô nào đặt vật cản;
• Subtask ~2~ (~25\%~ số điểm): ~𝑘 \leq 5~ và không có ô nào đặt vật cản;
• Subtask ~3~ (~25\%~ số điểm):~𝑘 = 2~;
• Subtask ~4~ (~25\%~ số điểm): ~𝑘 \leq 5~.

Sample Input 1

3 4 2
-1 0 3 0
19 9 9 0
0 0 0 -1 

Sample Output 1

3

Cho một dãy ~N~ số nguyên dương ~A_1,A_2,…,A_N~. Một thao tác thay đổi là việc chọn một phần tử ~a_i (1\leq i \leq N)~ và thay thế ~A_i=A_i+1~.

Yêu cầu: Bạn cần trả lời ~q~ truy vấn. Mỗi truy vấn cho bạn một dãy con liên tiếp trong đoạn từ ~l\rightarrow r~ và yêu cầu tính xem số lượng thao tác thay đổi tối thiểu để cho dãy con đã cho thành dãy không giảm.

Input

• Dòng đầu chứa hai số nguyên dương ~N,q~ ~(1\leq N,q \leq 2 \times 10^5)~;
• Dòng tiếp theo gồm ~N~ số nguyên dương ~A_1,A_2,…,A_n~ ~(A_i\leq 10^9)~.
• ~q~ dòng cuối cùng, mỗi dòng gồm 2 số nguyên dương ~l, r~ ~(1\leq l \leq r \leq n)~ biểu thị cho dãy con từ ~l~ đến ~r

Output

• In ra ~q~ dòng, mỗi dòng chứa một số nguyên không âm là kết quả bài toán của truy vấn tương ứng.

Sample Input 1

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

Sample Output 1

2
0
14

Explanation 1

• Truy vấn đầu tiên, bạn có thể sử dụng ~2~ thao tác để chuyển dãy con đã cho từ ~[4,2,5]~ thành ~[4,4,5]~.
• Truy vấn thứ ~2~, dãy con đã cho là dãy không giảm nên không cần thực hiện thao tác thay đổi nào.
• Trong truy vấn thứ ~3~, bạn có thể sử dụng ~14~ thao để chuyển dãy con thành ~[2,10,10,10]~.

Cho một cây gồm ~N~ đỉnh. Cạnh thứ ~i~ trên cây có trọng số ~w_i~. Độ dài đường đi giữa hai đỉnh ~u~ và ~v~ được định nghĩa là tổng các cạnh nằm trên đường đi phải qua ít cạnh nhất từ ~u~ tới ~v~. Chọn ~K~ đỉnh lá sao cho tổng độ dài đường đi giữa mọi cặp đỉnh trong ~K~ đỉnh đã chọn là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ ~(1≤K≤N)~.
• ~N-1~ dòng tiếp theo, mỗi dòng chứa thông tin về một cạnh của cây từ nút ~u_i~ đến ~v_i~ với trọng số ~w_i~ ~(1≤w_i≤10^5)~.

Output

• Gồm một số nguyên duy nhất là tổng khoảng cách nhỏ nhất trong cách chọn K nút lá tốt nhất.

Scoring

• Sub1: ~1 ≤ N ≤ 20~;
• Sub2: ~1 ≤ N ≤10^5, K=2~;
• Sub3: ~1 ≤ N ≤2000, K=3~;
• Sub4: ~1 ≤ N ≤10^5, K≤100~.

Example

Input

4 2
1 2 2
1 3 3
1 4 4

Output

5

Input

4 3
1 2 2
1 3 3
1 4 4

Output

18

Mrtee đang nghiên cứu về tổ kiển, mô hình đó được mổ phong trên một lưới ô vuông ~n×m~ bao gồm ~k~ ô ~(x_i,y_i)~. Các ô này có cấu trúc giống dạng cây, với hai ô kề cạnh bất kì có thể di chuyển tới nhau, và hai ô bất kì cũng có thể đi tới nhau theo một đường đi duy nhất. Mrtee đang quan tâm đến việc xét một hình chữ nhật ~(x_1,y_1,x_2,y_2)~ và nếu ta chỉ xét các ô thuộc tổ kiến nằm bên trong hình chữ nhật này thì sẽ có bao nhiêu thành phần liên thông.

Sẽ có ~q~ truy vấn có dạng như vậy.

Yêu cầu: cho dữ liệu về tổ kiến và ~q~ truy vấn, mỗi truy vấn là một hình chữ nhật, hãy đếm số thành phần liên thông trong hình chữ nhật đó.

Input

• Dòng đầu chứa hai số nguyên ~n,m~ (~1≤n,m≤2⋅10^5~ )
• Dòng thứ hai chứa số nguyên ~k,q~ (~2≤k≤2⋅10^5,1≤q≤2⋅10^5~).
• ~k-1~ dòng tiếp theo, mỗi dòng chứa ~f_i,x_i,y_i~ mô tả ô (~x_i,y_i~) thuộc tổ kiến kết nối với ô (~x_i+1,y_i~ ) nếu ~f_i= h~, hoặc kết nối với ô ~(x_i,y_i+1)~ nếu ~f_i=v~ (~1≤x_i≤n,1≤y_i≤m~). Dữ liệu đảm bảo các ô này tạo thành một cây.
• ~q~ dòng tiếp theo mỗi dòng chứa bốn số ~x_1,y_1,x_2,y_2~ (~1≤x_1≤x_2≤n,1≤y_1≤y_2≤m~). Các ô (~x,y~) được coi là nằm trong hình chữ nhật thỏa mãn ~x_1≤x≤x_2,y_1≤y≤y_2~.

Output

• Ghi ra ~q~ dòng là kết quả của mỗi truy vấn.

Subtask

• 20% số test có ~n,m,k,q≤100~
• 20% số test có ~n,m,k,q≤3000~
• 30% số test có ~n,m≤3000,k,q≤10^5~
• 30% số test còn lại không có ràng buộc gì thêm.

Example

Input 1

4 3
8 5
h 1 1
v 2 1
v 1 1
h 3 1
v 2 2
h 2 1
h 1 3
3 3 4 4
3 2 4 3
1 2 3 3
1 1 4 4
1 1 4 3

Output 1

0
0
2
1
1