Bạn được cho một số nguyên dương ~P~. Nhiệm vụ của bạn là dựng một hình chữ nhật có các cạnh mang độ dài nguyên dương và có chu vi đúng bằng ~P~ sao cho diện tích của nó là lớn nhất có thể.

Input:

• Gồm một dòng duy nhất chứa số nguyên dương ~P~ ~(3 \le P \le 10^9)~là chu vi của hình chữ nhật cần tìm.

Output:

• Nếu có thể dựng được hình chữ nhật thỏa mãn, hãy in ra diện tích lớn nhất có thể của hình chữ nhật đó, ngược lại nếu không thể dựng được hình chữ nhật, hãy in ra ~-1~.

Sample Input 1

8

Sample Output 1

4

Explanation 1

Dựng hình chữ nhật với chiều dài và chiều rộng đều bằng ~2~, khi đó diện tích bằng ~4~. Đây là diện tích lớn nhất có thể thu được.

Sample Input 2

3

Sample Output 2

-1

Explanation 2

Do bài toán yêu cầu cạnh có độ dài dương, không có cách nào để dựng lên một hình chữ nhật có chu vi bằng ~3~.

Bạn được cho một xâu ~S~ có độ dài ~n~ gồm các chữ cái từ a đến z. Nhiệm vụ của bạn là đếm số xâu con liên tiếp mà mỗi cặp kí tự đặc biệt trong xâu con đó có khoảng cách không nhỏ hơn ~k~ (~k \le n~).

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n~, ~m~ và ~k~ ~(1 \le k \le n \le 10^5; 1 \le m \le 10)~ lần lượt là độ dài của xâu ~S~, số lượng kí tự đặc biệt và khoảng cách yêu cầu giữa hai kí tự đặc biệt bất kì.
• Dòng thứ hai chứa xâu ~S~ gồm các chữ cái từ a đến z.
• Dòng cuối cùng gồm ~m~ kí tự là các kí tự đặc biệt, dữ liệu đảm bảo ~k~ kí tự này phân biệt

Output

• Gồm một dòng duy nhất là số lượng xâu con liên tiếp thỏa mãn đề bài

Substask

• ~30\%~ số test: ~1 \le k \le n \le 10^3~.
• ~20\%~ số test: ~1 \le k \le n \le 10^5~, trong xâu chỉ có đúng ~2~ vị trí có kí tự đặc biệt.
• ~50\%~ số test: ~1 \le k \le n \le 10^5~.

Sample Input 1

6 2 2
acbabc
a b

Sample Output 1

10

Explanation 1

Các xâu con thỏa mãn là: a, c, b, a, b, c, ac, acb, cb, bc.

Trong tiết học về số thập phân, các bạn học sinh đều thích các số thập phân hữu hạn vì chúng có thể viết ra được (dù phần thập phân có thể có ~10^{10^{18}}~ số, nhưng ít ra còn đỡ hơn vô hạn). Nhưng trái lại, vốn là một người luôn có ý tưởng đột phá, Hiếu lại thích các số thập phân vô hạn. Chính sự đột phá này đã giúp cậu thành công trong nhiều cuộc thi khi mà giúp cậu đưa ra được những ý tưởng táo bạo và độc đáo. Hiểu được cậu, Kh0i cũng ra một bài toán để thử thách Hiếu:

• Cho số nguyên dương ~n~, đếm số cặp ~(a, b)~ ~(1 \le a, b \le n)~ thỏa mãn ~s = \dfrac{a}{b}~ là số thập phân vô hạn.

Vì hiểu rằng Hiếu tuy vậy nhưng rất lười nên Kh0i chỉ bắt cậu tìm đáp án chia lấy dư cho ~10^9 + 7~, nhưng cậu phải trả lời câu hỏi này ~t~ lần. Các bạn hãy giúp Hiếu nhé!

Input

• Dòng đầu tiên gồm số nguyên dương ~t~ là số lượng câu hỏi.
• ~t~ dòng sau, dòng thứ ~i~ gồm duy nhất một số nguyên dương ~n~ là câu hỏi của anh Huy trong lần thứ ~i~.

Output

• In ra ~t~ dòng, dòng thứ ~i~ chứa duy nhất một số nguyên là đáp án cho câu hỏi thứ ~i~, chia lấy dư cho ~10^9 + 7~.

Subtask

• Trong tất cả các test, ~1 \le t \le 10~.
• Subtask 1 ~(40\%)~: Trong tất cả các câu hỏi, ~1 \le n \le 1000~.
• Subtask 2 ~(30\%)~: Trong tất cả các câu hỏi, ~1 \le n \le 10^6~.
• Subtask 3 ~(30\%)~: Trong tất cả các câu hỏi, ~1 \le n \le 10^{12}~.

Sample Input

3
4
6
20

Sample Output

3
8
204

Explanation

• Các cặp số thỏa mãn với ~n = 4~ là: ~(1, 3)~, ~(2, 3)~, ~(4, 3)~.
• Các cặp số thỏa mãn với ~n = 6~ là: ~(1, 3)~, ~(2, 3)~, ~(4, 3)~, ~(5, 3)~, ~(1, 6)~, ~(2, 6)~, ~(4, 6)~, ~(5, 6)~.

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~

Đất nước HNAms có ~m~ nguyên tố hóa học, được đánh số từ ~1~ tới ~m~.

Mỗi một hợp chất được tạo nên bởi một dãy các nguyên tố, độ tinh khiết của nguyên tố ~e~ ~(1 \le e \le m)~ trong hợp chất là số lần xuất hiện của ~e~ trong dãy.

Độ tinh khiết của hợp chất là số các nguyên tố hóa học ~e~ phân biệt ~(1 \le e \le m)~ thỏa mãn nồng độ của ~e~ trong hợp chất nằm trong đoạn ~[x_e,y_e]~.

Sau khi xem xong series Phá Vỡ Tệ, Duck tỏ ra đặc biệt đam mê với Hóa. Một hôm sau khi trốn học tuyển như thường lệ, cậu đã đến phòng thí nghiệm Hóa Học và đánh cắp được một dãy các nguyên tố ~a_1,a_2,...,a_n~.

Với ước muốn trở thành thầy Bạch, cậu đã tự tạo ra ~q~ thí nghiệm giả tưởng cho mình:

• Mỗi thí nghiệm có dạng ~(l,r)~, cậu thắc mắc rằng độ tinh khiết của hợp chất được tạo thành từ các nguyên tố trong đoạn ~a_l,a_{l+1},...,a_r~ là bao nhiêu.
• Nên nhớ đây chỉ là thí nghiệm giả tưởng vì cậu không có gan pha chế, vậy nên với mỗi thí nghiệm ta luôn xét đoạn ~[l,r]~ của dãy hợp chất ban đầu.

Tuy nhiên Duck không giỏi cả Hóa lẫn Tin, vậy nên hãy giúp cậu tính toán nhé.

Input:

• Dòng đầu tiên gồm ba số nguyên dương ~n,m,q~ ~(1 \le n,m,q \le 5 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(1 \le a_i \le m)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le m)~ gồm hai số nguyên dương ~x_i, y_i~ ~(1 \le x_i \le y_i \le n)~.
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~l,r~ ~(1 \le l \le r \le n)~ tương ứng với một truy vấn.

Output:

• Với mỗi truy vấn ~(l,r)~, in ra trên một dòng một số nguyên không âm là độ tinh khiết của hợp chất tạo thành bởi đoạn con ~a_l,a_{l+1},...,a_r~.

Subtask:

• Subtask ~1~ (~20\%~ số điểm): ~n,q \le 6000~.
• Subtask ~2~ (~25\%~ số điểm): ~n,q \le 10^5~.
• Subtask ~3~ (~25\%~ số điểm): ~x_i = 1, y_i = n~, ~\forall i \in [1,m]~.
• Subtask ~4~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

2
3
1
1

Explanation 1

Đoạn ~[1,3]~ có độ tinh khiết bằng ~2~ với hai nguyên tố ~1~ và ~2~.

Đoạn ~[1,7]~ có độ tinh khiết bằng ~3~ với ba nguyên tố ~1~, ~2~ và ~5~.

Đoạn ~[2,5]~ có độ tinh khiết bằng ~1~ với nguyên tố ~2~.

Đoạn ~[3,7]~ có độ tinh khiết bằng ~1~ với nguyên tố ~5~.

Khu rừng ma thuật có ~n~ địa điểm và được kết nối bởi ~n-1~ đường đi, hay nói cách khác, khu rừng chính là một cây!

Địa điểm ~i~ trong khu rừng mọc lên ~a_i~ cây nấm. Marisa muốn hái chúng, nhưng hôm nay cô đang hơi lười nên sẽ sử dụng chiếc máy hái nấm mới mua của Nitori.

Chiếc máy có phạm vi hoạt động là ~r~. Khi sử dụng chiếc máy ở địa điểm ~i~, nó sẽ hái toàn bộ nấm ở các đỉnh ~j~ sao cho đường đi ngắn nhất giữa ~i~ và ~j~ không quá ~r~. Chiếc máy có thể được sử dụng ~k~ lần trước khi hết pin. Hãy tìm cách hái được nhiều nấm nhất giúp Marisa nhé!

Input

• Dòng đầu tiên là ~T~, số lượng bộ dữ liệu.
• ~T~ nhóm dòng sau:
  • Dòng đầu tiên gồm ba số nguyên ~n,k,r~.
  • Dòng thứ hai gồm ~n~ số nguyên ~a_i~.
  • ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u,v~, thể hiện có đường đi giữa địa điểm ~u~ và ~v~.

Output

• Với mỗi bộ dữ liệu, in ra một số nguyên là số nấm nhiều nhất có thể hái được.

Subtask

• Trong toàn bộ các test: ~1 \le k \le n \le 1000~, ~1 \le r \le 1000~, ~1 \le a_i \le 10^6~, ~1 \le u,v \le n~, ~1 \le T \le 5~.
• Subtask ~1~ (~10\%~ số điểm): ~1 \le k \le n \le 20~.
• Subtask ~2~ (~10\%~ số điểm): Cây là đường thẳng.
• Subtask ~3~ (~40\%~ số điểm): ~1 \le k \le n \le 50~, ~0 \le r, a_i \le 50~.
• Subtask ~4~ (~20\%~ số điểm): ~k \le 2, n,r \le1000~.
• Subtask ~5~ (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

46