Sin-ga-lore là đất nước giáo dục lý tưởng cho nhiều học sinh đội tuyển. Ở Sing, anh Quân nổi tiếng là một học sinh giỏi đã học ~N~ môn học. Mỗi môn thứ ~i~ anh Quân được ~A_i~ điểm. Tại đây, điểm số là một số nguyên từ ~1~ đến ~5~. Điểm trung bình của mỗi học sinh là tổng điểm các môn chia cho số môn đã học (i.e. ~\frac{\sum_{i=1}^{n} A_i}{N}~) và làm tròn đến số nguyên gần nhất (Ví dụ: ~4.4~ sẽ làm tròn xuống ~4.0~, ~4.5~ sẽ làm tròn lên ~5.0~, hay ~3.49~ sẽ làm tròn xuống ~3.0~). Vì có nhiều đệ của anh Quân sang NUS học nên trường đã tặng cho anh Quân một món quà. Trường sẽ cho phép anh Quân sửa đổi tùy ý một vài điểm số bất kì. Tất nhiên là điểm đó phải hợp lệ (tức là một số nguyên từ ~1~ đến ~5~). Hỏi anh Quân sẽ phải sửa điểm của ít nhất bao nhiêu môn học để có điểm trung bình là ~5.0~

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(1 \le N \le 10^5)~.
• Dòng thứ hai gồm ~N~ số nguyên dương miêu tả dãy ~A~, dữ liệu đảm bảo rằng đây đều là các số nguyên dương từ ~1~ đến ~5~.

Output:

• In ra một số nguyên không âm là kết quả của bài toán.

Subtask:

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

Sample Input 1

4
3 2 5 4

Sample Output 1

2

Cho mảng ~A~ gồm ~N~ phần tử, mảng ~B~ gồm ~M~ phần tử. Bạn sẽ thực hiện ~N - M + 1~ thao tác, trong đó thao tác thứ ~i~ diễn ra như sau:

Xét các phần tử ~A_i, A_{i+1}, \ldots, A_{i + M - 1}~ và tăng chúng lần lượt lên ~B_1, B_2, \ldots, B_M~ (Hay nói cách khác, ~A_{i + j - 1}~ sẽ được tăng lên ~B_j~).

Bạn cần in ra dãy ~A~ sau khi thực hiện hết các thao tác.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~M~ ~(1 \le M \le N \le 10^5)~.
• Dòng thứ hai gồm ~N~ số nguyên dương miêu tả dãy ~A~ ~(A_i \le 10^9)~.
• Dòng thứ ba gồm ~B~ số nguyên dương miêu tả dãy ~B~ ~(B_i \le 10^9)~.

Output:

• In ra dãy ~A~ sau khi thực hiện các thao tác.

Subtask:

• Subtask ~1~ (~30\%~ số điểm): ~N,M \le 1000~
• Subtask ~3~ (~30\%~ số điểm): ~B_i = 1~
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm

Sample Input 1

3 2
5 1 3
1 2

Sample Output 1

6 4 5

Chặt nhị phân là một kĩ thuật tìm kiếm quen thuộc đối với tất cả các lập trình viên. Một dãy số ~a~ là một dãy có thể chặt nhị phân được nếu như nó là một dãy số đồng biến. Cụ thể hơn, dãy đồng biến là dãy thoả mãn tính chất: ~(a_i - a_j) \cdot (a_j - a_k) \ge 0 \ \ \forall 1 \le i < j < k \le n~. Chú ý rằng theo định nghĩa này, mọi dãy số có không, một hoặc hai phần tử đều là dãy đồng biến.

Cho dãy số ~a_1, a_2, \ldots, a_n~, hãy đếm xem có bao nhiêu dãy con khác nhau của dãy này là dãy đồng biến.

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

Một dãy ~b~ được gọi là dãy con của dãy ~a~ nếu như ta có thể bỏ bớt một vài phần tử của ~a~ và giữ nguyên thứ tự của các phần tử còn lại để thu được dãy ~b~.

Hai dãy con được gọi là khác nhau nếu tồn tại một vị trí ~i~ sao cho phần tử thứ ~i~ của dãy ~a~ được bỏ đi để tạo ra dãy con thứ nhất, nhưng không được bỏ đi để tạo ra dãy con thứ hai.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~ ~(0 \le a_i \le 10^5)~.

Output

• In ra một số nguyên không âm là kết quả của bài toán.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \le 20~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~2~ (~20\%~ số điểm): ~n \le 80~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~3~ (~20\%~ số điểm): ~n \le 300~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~4~ (~20\%~ số điểm): ~n \le 5000~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~5~ (~10\%~ số điểm): Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~6~ (~10\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

5
4 2 1 5 3

Sample output 1

17

Explaination

Các dãy con đồng biến là:

• []
• [4], [2], [1], [5], [3]
• [4, 2], [4, 1], [4, 5], [4, 3], [2, 1], [2, 5], [2, 3], [1, 5], [1, 3], [5, 3]
• [4, 2, 1]

Công ty Chim có ~n~ thành viên được phân nhiều quyền hạn khác nhau, trong đó người thứ ~1~ là sếp tổng. Mỗi thành viên trừ sếp tổng đều có chính xác một người ~p_i~ là sếp trực tiếp của họ. Người ~u~ được gọi là nằm dưới quyền hạn của người ~v~ nếu như người ~v~ là sếp trực tiếp của người ~u~, hoặc sếp trực tiếp của người ~u~ nằm dưới quyền hạn của người ~v~. Hay nói cách khác, cách phân quyền hạn của công ty Chim có cấu trúc như một đồ thị dạng cây.

Công ty đang có ~m~ phương án tăng lương cho các thành viên. Ở phương án thứ ~i~, công ty sẽ tăng lương cho người thứ ~u_i~ và tất cả các thành viên nằm dưới quyền hạn của người thứ ~u_i~ lên ~w_i~ đồng. Để đánh giá được độ thích hợp của những phương án này, công ty đặt ra ~q~ khảo sát. Ở khảo sát thứ ~i~, công ty muốn kiểm tra rằng nếu như chỉ có những phương án thứ ~t~ ~\forall t \in [L_i, R_i]~ được thực thi, người thứ ~u_i~ được tăng lương tổng cộng bao nhiêu đồng. Bạn hãy giúp công ty tìm ra câu trả lời cho ~q~ khảo sát này nhé.

Input

• Dòng đầu chứa ba số nguyên dương ~n, m, q~ ~(1 \le n, m, q \le 10^5)~.
• Dòng thứ hai chứa ~n - 1~ số nguyên dương ~p_2, p_3, \ldots, p_n~ ~(1 \le p_i \le n)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u_i, w_i~ ~(1 \le u_i \le n, \ 1 \le w_i \le 10^9)~.
• ~q~ dòng cuối cùng, dòng thứ ~i~ chứa ba số nguyên dương ~L_i, R_i, u_i~ ~(1 \le L_i \le R_i \le m, \ 1 \le u_i \le n)~.

Dữ liệu bảo đảm cấu trúc phân quyền của công ty là một đồ thị dạng cây.

Output

• In ra ~q~ dòng, dòng thứ ~i~ chứa câu trả lời cho khảo sát thứ ~i~.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n, m, q \le 500~
• Subtask ~2~ (~20\%~ số điểm): ~L_i = 1, R_i = m \ \forall i \in [1, q]~
• Subtask ~3~ (~20\%~ số điểm): ~n, m, q \le 5000~
• Subtask ~4~ (~20\%~ số điểm): ~p_i = i - 1 \ \forall i \in [2, n]~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

6 6 4
1 5 5 2 5 
6 9
4 10
1 6
5 5
5 6
6 5
2 5 5
1 1 1
2 3 2
1 4 1

Sample output 1

17
0
6
6

Bài đồ thị siêu cơ bản nên đề bài vô cùng ngắn gọn:

Quân có một đồ thị đầy đủ, vô hướng, có trọng số gồm ~n~ đỉnh. Trọng số của đỉnh thứ ~i~ là ~a_i~. Trọng số của cạnh nối giữa đỉnh ~u~ và đỉnh ~v~ là ~\frac{a_u + a_v}{gcd(a_u, a_v)}~. Cảm giác bài chưa đủ khó nên Quân vẽ thêm ~m~ cạnh nối nữa. Cạnh thứ ~i~ nối giữa hai đỉnh ~u_i~ và ~v_i~, và có trọng số là ~w_i~.

Hãy tính độ dài đường đi ngắn nhất từ đỉnh ~1~ tới mỗi đỉnh còn lại.

Input

• Dòng đầu chứa hai số nguyên không âm ~n, m~ ~(1 \le n \le 10^5, 0 \le m \le 10^4)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^5)~.
• ~m~ dòng cuối cùng, dòng thứ ~i~ chứa ba số nguyên dương ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10^5)~.

Output

• In ra ~n~ số nguyên không âm, số thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~i~.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \le 1000~
• Subtask ~2~ (~20\%~ số điểm): Dãy ~a~ đôi một giống nhau
• Subtask ~3~ (~20\%~ số điểm): ~m = 0; \ a_i \le 50 \ \forall i \in [1, n]~
• Subtask ~4~ (~20\%~ số điểm): ~m = 0~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

3 1
1 2 3
2 3 1

Sample output 1

0 3 4

Huy và Châu trong công cuộc tìm lại cảm hứng đã quyết định đào sâu về toán học, đặc biệt là phần số học. Để tìm kiếm tài liệu, hai cậu quyết định đi tới tuyển Tin Ams, và vô tình thấy được một bài toán khó như sau được viết trên bảng:

Cho mảng ~a~ gồm ~n~ phần tử nguyên dương và một số nguyên dương ~k~.

Ta đều biết các số nguyên dương đều có thể phân tích dưới dạng thừa số nguyên tố, vậy nên đỡ mất thời gian phân tích gây tổn hại máy chấm, bạn sẽ nhận được số nguyên dương ~k~ dưới dạng phân tích thừa số nguyên tố của nó. Nói cách khác, bạn sẽ nhận được hai dãy nguyên dương ~p~ và ~x~ gồm ~m~ phần tử, thỏa mãn ~p~ gồm các số nguyên tố phân biệt. Lúc này ~k = p_1^{x_1} \times p_2^{x_2} \times p_3^{x_3} \times ... \times p_m^{x_m}~.

Giả sử ~S~ là một dãy con của dãy ~a~ (bao gồm cả dãy rỗng), ta có định nghĩa sau:

• Gọi ~LCM(S)~ là bội chung nhỏ nhất của mọi phần tử thuộc ~S~. Đối với ~S = \emptyset~, giá trị này được coi là ~1~.
• Gọi ~G(S)~ là trọng số của dãy con ~S~, giá trị ~G(S) = x~ với ~x~ là số nguyên dương nhỏ nhất thỏa mãn: ~k | LCM(S) \times x~, hay ~LCM(S) \times x~ chia hết cho ~k~.

Hãy tính tổng trọng số của các dãy con ~S~ thoả mãn ~G(S) = 1~, hay nói cách khác đếm số dãy con sao cho bội chung nhỏ nhất của nó chia hết cho ~k~.

Sau khi đọc xong, hai cậu mới biết rằng hóa ra đây là một đề bài được dự định sẽ cho vào ~AMSOI~ ~Round~ ~4~. Vốn đều là những người có ước mơ được thi ~VMO~ cháy bỏng, hai cậu đã nhanh chóng tìm ra lời giải của bài toán, thậm chí còn có thể giải một yêu cầu tổng quát hơn như sau:

Thay vì chỉ tính các dãy con ~S~ có ~G(S) = 1~, nhiệm vụ của bạn là hãy tính tổng trọng số của toàn bộ dãy con trong ~S~.

Tuy nhiên, Huy lại muốn đưa nó vào đề bài chính thức, Châu lại bảo như vậy là quá khó với các bạn học sinh. Vậy nên, hai cậu quyết định thuyết phục thầy ... đưa cả hai dạng yêu cầu này vào bài. Và đó là lý do tại sao bạn lại đọc được đề của nó vào ngày hôm nay.

Để hiện thực hóa thỉnh cầu của học trò, ~mrtee~ sẽ cho bạn một tham số ~t~.

Với ~t = 1~, bạn hãy in ra kết quả của yêu cầu thứ nhất:

Hãy tính tổng trọng số của các dãy con ~S~ thoả mãn ~G(S) = 1~, hay nói cách khác đếm số dãy con sao cho bội chung nhỏ nhất của nó chia hết cho ~k~.

Với ~t = 2~, bạn hãy in ra kết quả của yêu cầu thứ hai:

Thay vì chỉ tính các dãy con ~S~ có ~G(S) = 1~, nhiệm vụ của bạn là hãy tính tổng trọng số của toàn bộ dãy con trong ~S~.

Với cả hai yêu cầu, tổng bạn cần tính đều có giá trị rất lớn, vậy nên hãy in nó ra sau khi lấy phần dư cho ~10^9+7~.

Một dãy ~b~ được gọi là dãy con của dãy ~a~ nếu như ta có thể bỏ bớt một vài phần tử của ~a~ và giữ nguyên thứ tự của các phần tử còn lại để thu được dãy ~b~.

Hai dãy con được gọi là khác nhau nếu tồn tại một vị trí ~i~ sao cho phần tử thứ ~i~ của dãy ~a~ được bỏ đi để tạo ra dãy con thứ nhất, nhưng không được bỏ đi để tạo ra dãy con thứ hai.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n,m,t~ (~1 \le n \le 10^5; 1 \le m \le 16; 1 \le t \le 2~).
• Dòng thứ hai gồm ~m~ số nguyên dương miêu tả dãy ~p~, dữ liệu đảm bảo rằng đây đều là các số nguyên tố và chúng đôi một khác nhau (~2 \le p_i \le 10^6~).
• Dòng thứ hai gồm ~m~ số nguyên dương miêu tả dãy ~x~ ~(1 \le \sum_{i=1}^{m} x_i \le 20)~.
• Dòng cuối cùng gồm ~n~ số nguyên dương miêu tả dãy nguyên dương ~a~ (~1 \le a_i \le 10^{9}~).

Output:

• Với ~t = 1~, hãy in ra kết quả của yêu cầu thứ nhất, ngược lại với ~t = 2~ in ra kết quả của yêu cầu thứ hai. Vì kết quả có thể rất lớn nên hãy in nó ra sau khi lấy phần dư với ~10^9+7~.

Subtask:

• Subtask ~1~ (~10\%~ số điểm): ~t = 1; n \le 20; a_i \le 15; k \le 10^9~.
• Subtask ~2~ (~15\%~ số điểm): ~t = 1; n \le 50; a_i \le 15; k \le 10^9~.
• Subtask ~3~ (~20\%~ số điểm): ~t = 2; m \le 6; x_i = 1 \forall i \in [1,m]~.
• Subtask ~4~ (~25\%~ số điểm): ~t = 2; x_i = 1 \forall i \in [1,m]~.
• Subtask ~5~ (~15\%~ số điểm): ~t = 1~.
• Subtask ~6~ (~15\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

3 2 1
2 3
1 1
4 9 5

Sample Output 1

2

Sample Input 2

5 2 1
3 2
2 1
4 24 17 18 3

Sample Output 2

16

Sample Input 3

3 2 2
2 3
1 1
4 9 5

Sample Output 3

24

Sample Input 4

7 2 2
3 2
2 2
4 24 17 18 3 9 6

Sample Output 4

332

Explanation

Trong ví dụ thứ nhất, có hai dãy con ~S~ có ~G(S) = 1~ là dãy ~\{1;2\}~ và dãy ~\{1;2;3\}~.

Trong ví dụ thứ hai, có ~16~ dãy thỏa mãn chia hết cho ~k = 18~.

Ở ví dụ thứ ba với ~t = 2~ ta cần trả lời câu hỏi dạng thứ hai. Do ~k = 6~, ta sẽ xét các dãy con sau:

• ~\{\emptyset\}~: Dãy rỗng có ~LCM(\emptyset) = 1~, như vậy ~G(S) = 6~
• Ba dãy con độ dài ~1~: ~\{1\}~; ~\{2\}~; ~\{3\}~ lần lượt có ~G(S)~ là ~3;2;6~.
• Ba dãy con có độ dài ~2~: ~\{1;2\}~; ~\{2;3\}~; ~\{1;3\}~ lần lượt có ~G(S)~ là ~1;2;6~.
• Dãy con ~\{1;2;3\}~ có ~G(S) = 1~.
• Tổng lại ta thu được đáp án cho toàn bộ dãy con là ~24~.