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*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

Đã là sản phẩm thì phải có mã vạch ở trên nên Nitori quyết định in mã vạch cho sản phẩm dưa chuột của mình. Cô muốn mã vạch có kích thước ~n \times m~, kí tự # thể hiện màu đen còn . thể hiện màu trắng. Các cột của mã vạch phải cùng màu, số lượng cột cùng màu nhau ở cạnh nhau ít nhất là ~x~ và nhiều nhất là ~y~.

Do máy in bị trục trặc nên mã vạch đã bị in sai hết cả. Nitori muốn tiết kiệm chi phí nên hãy đếm số lượng ít nhất kí tự phải sửa để được mã vạch thỏa mãn yêu cầu nhé!

Input

• Dòng đầu tiên gồm các số nguyên dương ~1 \le n, m, x, y \le 1000~.
• ~n~ dòng tiếp theo gồm ~m~ kí tự thuộc # hoặc ..

Output

• Số lượng kí tự ít nhất phải sửa.

Sample Test

Input:

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

Output:

11

Cho ba số nguyên dương ~c~, ~d~, ~x~. Bạn cần phải tìm số cặp ~(a,b)~ thỏa mãn ~c*lcm(a,b) - d*gcd(a,b) = x~. Ở đây, ~lcm(a,b)~ là bội chung nhỏ nhất của ~(a,b)~, ~gcd(a,b)~ là ước chung lớn nhất của ~(a,b)~.

Input

• Dòng đầu gồm số nguyên dương ~t~ ~(t \le 10^4)~ là số lượng test case.
• ~t~ dòng sau, mỗi dòng gồm ba số nguyên dương ~c~, ~d~, ~x~ miêu tả test case. ~(1 \le c,d,x \le 10^7)~

Output

• Với mỗi test case, in ra số lượng cặp ~(a,b)~ thỏa mãn.

Sample Test

Input

4
1 1 3
4 2 6
3 3 7
2 7 25

Output

4
3
0
8

Giải thích: Ở test case thứ nhất, có ~4~ cặp thỏa mãn là ~(1,4), (4,1), (3,6), (6,3)~

Cho một cây vô hướng ~n~ đỉnh với gốc là ~1~, mỗi đỉnh ~u~ có một giá trị là ~c[u]~. Cho ~q~ truy vấn có dạng như sau:

• Truy vấn có dạng "~1~ ~v~". Với truy vấn này, tạm gọi dãy ~u_1, u_2, ..., u_k~ là dãy đỉnh trong đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~v~, (~u_k = v~). Bạn cần tìm một đỉnh ~u_i~ nào đó thỏa mãn ~gcd(c[u_i], c[v]) > 1~ với ~1 \le i < k~. Nếu có nhiều giá trị ~u_i~ thỏa mãn, hãy chọn đỉnh có ~i~ lớn nhất, ngược lại, in ra ~-1~ nếu không có đỉnh nào như vậy.
• Truy vấn có dạng "~2~ ~v~ ~w~". Với truy vấn này, bạn hãy đổi giá trị ~c[v] = w~. Có tối đa ~50~ truy vấn dạng này.

Hãy giải quyết bài toán trên.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~q~ ~(1 \le n,q \le 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~c_1, c_2, ..., c_n~. ~(c_i \le 2*10^6)~
• ~n-1~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~u v~ miêu tả cạnh nối giữa hai đỉnh này.
• ~q~ dòng tiếp theo, mỗi dòng miêu tả một truy vấn. Lưu ý rằng, với mọi truy vấn, ~v \le n~, ~w \le 2*10^6~

Output

• In ra kết quả của các truy vấn dạng ~1~ thành từng dòng.

Sample Test

Input

4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4

Output

-1
1
2
-1
1

Số may mắn là số mà biểu diễn thập phân của nó chỉ chứa chữ số 4 và 7, ví dụ: 4, 7, 444, 747,...

Cho mảng ~a~ có ~n~ phần tử nguyên dương. Đếm số lượng dãy con (không nhất thiết liên tiếp) có độ dài ~k~ mà không số may mắn nào xuất hiện quá 1 lần.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~1 \le k \le n \le 10^5~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le a_i \le 10^9~ là các phần tử của mảng ~a~.

Output

• Số lượng dãy con thỏa mãn modulo ~10^9+7~.

Sample Test

Input:

4 2
4 4 7 7

Output:

4