Huy có một dãy số gồm ~2n~ phần tử ~a_1, a_2, ..., a_{2n}~, trong đó mỗi số nguyên dương không lớn hơn ~n~ xuất hiện đúng hai lần. Huy định nghĩa khoảng cách của một vị trí ~i~ trong dãy số và một cặp phần tử cùng có giá trị ~j~ là ~D(i, j)~, được tính theo công thức:

$$D(i, j) = (|x_j - i| + 1) \times (|y_j - i| + 1)$$

trong đó ~x_j, y_j~ là hai vị trí của hai phần tử có giá trị ~j~.

Huy muốn tính xem với mỗi vị trí ~i~ thì khoảng cách gần nhất giữa ~i~ và một cặp phần tử bất kỳ là bao nhiêu, hay nói cách khác Huy muốn tìm giá trị ~D(i, j)~ nhỏ nhất với mọi ~j~. Tuy nhiên do số vị trí quá lớn nên Huy không thể tính nhanh được, các bạn hãy giúp Huy nhé.

Dữ liệu - Nhập từ tệp văn bản PAIR.inp:

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng tiếp theo gồm ~2n~ số nguyên dương ~a_1, a_2, ..., a_{2n}~ ~(1 \le a_i \le n)~.
• Dữ liệu đầu vào đảm bảo trong dãy ~a~ có đúng hai phần tử có giá trị ~i~ với mỗi ~i~ thỏa mãn ~1 \le i \le n~.

Kết quả - Ghi ra tệp văn bản PAIR.out:

• Một dòng duy nhất gồm ~2n~ số nguyên dương, số nguyên dương thứ ~i~ là khoảng cách ngắn nhất của một cặp số bất kỳ với vị trí ~i~.

Chấm điểm

Ví dụ

Dữ liệu (PAIR.inp)

2
1 2 2 1

Kết quả (PAIR.out)

4 2 2 4

Giải thích

• Cặp phần tử có giá trị ~1~ xuất hiện tại hai vị trí ~1~ và ~4~.
• Khoảng cách giữa vị trí ~1~ và cặp phần tử có giá trị ~1~ là: $$D(1, 1) = (|x_1 - 1| + 1) \times (|y_1 - 1| + 1) = (|1 - 1| + 1) \times (|4 - 1| + 1) = 4$$
• Cặp phần tử gần nhất với vị trí ~1~ và vị trí ~4~ là cặp phần tử có giá trị ~1~, với khoảng cách là ~4~.
• Cặp phần tử gần nhất với vị trí ~2~ và vị trí ~3~ là cặp phần tử có giá trị ~2~, với khoảng cách là ~2~.

Hôm nay, Dung muốn cho Huy một thử thách nho nhỏ về Toán học.

Dung có một dải băng dài được chia thành ~n~ ô vuông được đánh số thứ tự từ ~1~ đến ~n~ từ trái sang phải. Ban đầu, mỗi ô vuông trên băng đều ghi số ~1~. Huy có thể yêu cầu Dung thực hiện các thao tác sau:

• ~+\ i\ j\ k~: Cộng hai số ở vị trí ~i~ và ~j~, sau đó ghi kết quả vào ô ở vị trí ~k~.
• ~*\ i\ j\ k~: Nhân hai số ở vị trí ~i~ và ~j~, sau đó ghi kết quả vào ô ở vị trí ~k~.

Lưu ý, ~i, j, k~ có thể giống nhau.

Dung sẽ cho Huy một số nguyên dương ~n~. Gọi ~p_i~ là số nguyên tố thứ ~i~. Cô có 4 loại thử thách như sau:

• Loại 1: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi giá trị ~i~.
• Loại 2: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi giá trị ~p_i~.
• Loại 3: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi tổng các giá trị ~j^3~ với ~j~ là ước của ~i~. Ví dụ, ô ~4~ sẽ ghi giá trị ~1^3 + 2^3 + 4^3 = 73~.
• Loại 4: Với mọi ô từ ~2~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi lập phương tổng các giá trị ~p_j~ với ~j~ là ước nguyên tố của ~i~. Ví dụ, ô ~6~ sẽ ghi giá trị ~(p_2 + p_3)^3 = (3 + 5)^3 = 512~. Ô ~1~ cần ghi giá trị ~1~.

Để hoàn thành thử thách, Huy được phép yêu cầu Dung thực hiện thao tác biến đổi không quá ~50000~ lần.

Các bạn hãy viết chương trình giúp Huy hoàn thành thử thách nhé.

Dữ liệu - Nhập từ tệp văn bản ARRAY.inp:

• Một dòng duy nhất gồm hai số nguyên dương ~n, \theta~, với ~\theta~ là loại thử thách của Dung. ~(1 \le n \le 20000, 1 \le \theta \le 4)~

Kết quả - Ghi ra tệp văn bản ARRAY.out:

• Dòng đầu tiên gồm một số nguyên dương ~k~ là số lần Dung cần thực hiện thao tác biến đổi. ~(0 \le k \le 50000)~
• ~k~ dòng tiếp theo, mỗi dòng thuộc một trong hai dạng sau:
  • ~+\ i\ j\ k~: mô tả thao tác cộng. ~(1 \le i, j, k \le n)~
  • ~*\ i\ j\ k~: mô tả thao tác nhân. ~(1 \le i, j, k \le n)~

Chấm điểm

Ví dụ

Dữ liệu (ARRAY.inp)

2 2

Kết quả (ARRAY.out)

2
+ 1 1 1
+ 1 2 2

Giải thích

• Đầu tiên, Huy lấy giá trị của ô đầu tiên cộng với chính nó và ghi vào ô đầu tiên. Kết quả là ~1 + 1 = 2~.
• Tiếp theo, Huy lấy giá trị của ô đầu tiên cộng với giá trị của ô thứ hai và ghi vào ô thứ hai. Kết quả là ~2 + 1 = 3~.

Các subtask 1, 2, 3, 4 của bài này sẽ có đôi chút khác biệt về yêu cầu đề và giới hạn của các biến. Các bạn lưu ý đọc kỹ đề. Với subtask 4, không có giới hạn gì thêm.

Quang đang chơi một trò chơi điện tử. Màn chơi hiện tại của Quang có ~n~ cứ điểm được xếp thành một đường thẳng. Nhân vật của Quang có hai chỉ số là thể lực, ký hiệu là ~p~, và máu, ký hiệu là ~h~. Anh ta sẽ thăm các cứ điểm theo thứ tự tăng dần (nghĩa là sau khi thăm cứ điểm thứ ~i~ anh ta sẽ di chuyển đến cứ điểm thứ ~i + 1~). Cứ điểm thứ ~i~ có thể thuộc một trong ba loại sau:

• Cứ điểm loại ~1~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ điểm thể lực.
• Cứ điểm loại ~2~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ máu.
• Cứ điểm loại ~3~: chứa một con quái vật. Nhân vật của Quang sẽ có hai lựa chọn:
  • Chiến đấu với quái vật và mất ~1~ điểm thể lực.
  • Chấp nhận để quái vật đánh một đòn, mất ~1~ máu và chạy trốn khỏi cứ điểm.

Nếu một trong hai chỉ số máu và thể lực của nhân vật về ~0~ tại một thời điểm nào đó, nhân vật của Quang sẽ chết và Quang sẽ thua trò chơi.

Quang có ~q~ kịch bản, trong đó kịch bản thứ ~i~ cho biết nhân vật của Quang đang chuẩn bị thăm cứ điểm ~l_i~, đang có ~p_i~ điểm thể lực và ~h_i~ máu. Bạn cần tính toán xem nhân vật của Quang có thể an toàn thoát khỏi cứ điểm ~r_i~ hay không. Nếu có, hãy cho biết số quái vật ít nhất mà nhân vật của Quang phải chiến đấu là bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương, ~n, q~ ~(1 \le n, q \le 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 3)~ - loại của cứ điểm thứ ~i~.
• ~q~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên dương ~l_i, r_i, p_i, h_i~ ~(1 \le l_i \le r_i \le n, 1 \le p_i, h_i \le 10^5)~.
• Với subtask 4, không có giới hạn gì thêm.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.
  • Nếu nhân vật của Quang không thể đi từ ~l_i~ đến ~r_i~, in ra ~-1~.
  • Ngược lại, in ra số quái vật nhỏ nhất mà nhân vật của Quang phải chiến đấu.

Ví dụ

Ví dụ 1

Dữ liệu vào

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

Dữ liệu ra

0
-1
1

Giải thích

• Trong kịch bản đầu tiên, sau khi được tăng thêm ~2~ thể ở cứ điểm thứ ~1~ và ~2~, nhân vật của Quang chỉ cần tránh hai quái vật ở nhà ~3~ và ~5~ rồi thoát khỏi cứ điểm ~5~ mà không cần phải chiến đấu với một con quái vật nào.
• Trong kịch bàn thứ hai, cho dù Quang chọn chiến đấu hay chạy trốn thì máu hoặc thể lực của nhân vật đều về ~0~ và Quang thua trò chơi.
• Trong kịch bản cuối cùng, Quang nhận ~1~ điểm thể lực ở cứ điểm ~4~ và chiến đấu với quái vật ở cứ điểm ~5~. Do đó nhân vật của Quang phải đối đầu với ~1~ quái vật.

Để trang trí cho buổi lễ bế mạc của kỳ thi Olympic truyền thống 30 tháng 4, bạn Hạnh Giang dự định thiết kế một mạng lưới gồm các bóng đèn và dây đèn treo trên trần nhà. Mỗi dây đèn kết nối chính xác hai bóng đèn, và giữa mỗi cặp bóng đèn bất kỳ có không quá một dây đèn. Hiện tại, Hà đã chuẩn bị sẵn ~n~ bóng đèn màu với các màu sắc khác nhau, các bóng đèn này được đánh số từ ~1~ đến ~n~.

Sau khi tính toán các yếu tố về ánh sáng và màu sắc, Hạnh Giang muốn khoảng cách giữa bóng đèn màu thứ ~i~ và bóng đèn màu thứ ~j~ chính xác bằng ~a_{ij}~, với khoảng cách giữa hai bóng đèn là số lượng dây đèn ít nhất kết nối chúng. Hà có thể mua thêm một số bóng đèn trắng để hoàn thiện vào mạng lưới của mình, tuy nhiên do ngân sách cho buổi lễ này có hạn nên bạn phải tìm cách mua thêm ít bóng đèn trắng nhất có thể (tuy nhiên không có giới hạn về số lượng dây đèn được mua thêm). Bạn hãy giúp Hạnh Giang tìm ra một phương án hợp lệ sử dụng ít bóng đèn trắng nhất nhé.

Dữ liệu:

• Dòng đầu tiên gồm một số nguyên dương n là số bóng đèn màu ~(2≤n≤20)~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~n~ số nguyên không âm ~a_{i1}, a_{i2}, …, a_{in}~ là khoảng cách giữa các cặp bóng đèn màu ~(a_{ii}=0, 1≤a_{ij}=a_{ji}≤10 ∀i≠j)~.

Kết quả:

• Nếu không tồn tại phương án thỏa mãn, in ra hai số ~-1~ trên một dòng.
• Ngược lại, in ra kết quả theo định dạng sau:
• Dòng đầu tiên gồm hai số nguyên dương ~k,m~ lần lượt là số lượng bóng đèn trắng và dây đèn mà Hạnh Giang phải mua thêm.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~i,j~ mô tả một dây đèn kết nối bóng đèn thứ ~i~ và bóng đèn thứ ~j~ ~(1 ≤ i < j ≤ n+k)~. Các bóng đèn trắng mà Hạnh Giang mua thêm được đánh số từ ~n+1~ đến ~n+k~.

Chấm điểm

Gọi ~k_p~ là số bóng đèn trắng cần thêm vào trong phương án của bạn, ~k_j~ là số bóng đèn trắng cần thêm vào trong phương án của giám khảo. Nếu điểm tối đa của test là ~1~, điểm của bạn được tính như sau:

• Nếu ~k_p \le k_j~, bạn được ~1~ điểm cho test đó.
• Nếu ~k_p > k_j + 400~, bạn được ~0~ điểm cho test đó.
• Nếu ~k_j < k_p \le k_j + 400~, điểm của bạn (~S~) sẽ được tính theo công thức:

$$S = 1 - (\frac{k_p - k_j - 0.75}{400})^{0.25}$$

Nộp bài

Các bạn có thể nộp bài bằng một trong hai cách sau:

• Nộp code: Bạn có thể nộp code như một bài bình thường, nhập dữ liệu từ stdin, in kết quả ra stdout, giới hạn thời gian để đoạn code của bạn đưa ra kết quả là ~40~ giây.
• Nộp bài theo từng test: Sử dụng ngôn ngữ TEXT. Sao chép output của bạn cho một test vào khung code. Tuy nhiên cách nộp bài này chỉ nộp được 1 test một lần.

Testcase

Bộ test bài gồm ~6~ testcase, mỗi testcase có giá trị ~1~ điểm.

Test 1 ~(k_j = 15)~

5
0 10 7 7 8
10 0 7 9 6
7 7 0 6 4
7 9 6 0 5
8 6 4 5 0

Test 2 ~(k_j = 43)~

10
0 3 8 7 6 7 7 6 9 6
3 0 7 6 6 5 7 7 9 6
8 7 0 7 6 6 7 7 3 8
7 6 7 0 10 6 7 9 8 5
6 6 6 10 0 8 9 4 5 8
7 5 6 6 8 0 5 5 5 3
7 7 7 7 9 5 0 7 6 7
6 7 7 9 4 5 7 0 7 5
9 9 3 8 5 5 6 7 0 6
6 6 8 5 8 3 7 5 6 0

Test 3 ~(k_j = 32)~

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

Test 4 ~(k_j = 69)~

20
0 3 2 8 6 8 4 8 4 5 4 5 3 5 6 8 4 4 7 6
3 0 4 7 4 6 4 7 3 5 4 4 4 4 4 6 5 3 5 4
2 4 0 7 5 7 4 7 4 4 3 4 4 5 5 8 4 4 7 5
8 7 7 0 9 9 8 6 8 8 9 8 8 6 6 5 9 7 8 7
6 4 5 9 0 8 7 9 5 2 7 6 6 6 6 8 8 5 7 7
8 6 7 9 8 0 5 7 7 8 7 5 7 7 7 8 8 5 7 3
4 4 4 8 7 5 0 5 5 6 3 5 6 6 7 6 6 5 6 5
8 7 7 6 9 7 5 0 7 8 7 6 8 5 6 2 9 5 3 5
4 3 4 8 5 7 5 7 0 4 5 4 4 4 5 7 6 3 6 6
5 5 4 8 2 8 6 8 4 0 6 5 5 7 6 8 7 4 8 6
4 4 3 9 7 7 3 7 5 6 0 4 4 6 7 8 6 5 6 5
5 4 4 8 6 5 5 6 4 5 4 0 4 5 6 7 4 4 6 4
3 4 4 8 6 7 6 8 4 5 4 4 0 5 6 8 5 4 6 5
5 4 5 6 6 7 6 5 4 7 6 5 5 0 6 6 6 4 5 6
6 4 5 6 6 7 7 6 5 6 7 6 6 6 0 5 8 3 5 5
8 6 8 5 8 8 6 2 7 8 8 7 8 6 5 0 10 6 4 6
4 5 4 9 8 8 6 9 6 7 6 4 5 6 8 10 0 6 8 6
4 3 4 7 5 5 5 5 3 4 5 4 4 4 3 6 6 0 5 5
7 5 7 8 7 7 6 3 6 8 6 6 6 5 5 4 8 5 0 5
6 4 5 7 7 3 5 5 6 6 5 4 5 6 5 6 6 5 5 0

Test 5 ~(k_j = 51)~

20
0 7 5 5 7 4 6 7 5 5 7 3 5 3 5 3 6 5 5 5
7 0 10 7 6 7 9 9 3 8 7 5 10 9 7 9 9 10 9 7
5 10 0 6 5 8 9 7 8 3 5 7 7 4 7 3 8 5 5 5
5 7 6 0 5 5 7 4 5 4 4 3 6 7 5 6 5 6 4 2
7 6 5 5 0 7 6 4 4 3 2 5 6 6 3 5 5 5 5 4
4 7 8 5 7 0 3 5 5 7 7 3 5 6 5 6 6 8 7 5
6 9 9 7 6 3 0 7 7 7 7 5 3 8 4 8 4 7 9 7
7 9 7 4 4 5 7 0 7 5 3 5 7 8 6 7 6 7 5 3
5 3 8 5 4 5 7 7 0 6 5 3 8 7 5 7 7 8 7 5
5 8 3 4 3 7 7 5 6 0 3 5 5 4 5 3 6 3 5 3
7 7 5 4 2 7 7 3 5 3 0 5 7 6 4 5 6 5 4 3
3 5 7 3 5 3 5 5 3 5 5 0 6 5 3 5 5 7 5 3
5 10 7 6 6 5 3 7 8 5 7 6 0 7 4 7 2 5 7 5
3 9 4 7 6 6 8 8 7 4 6 5 7 0 7 2 8 6 4 6
5 7 7 5 3 5 4 6 5 5 4 3 4 7 0 7 3 7 7 5
3 9 3 6 5 6 8 7 7 3 5 5 7 2 7 0 8 5 3 5
6 9 8 5 5 6 4 6 7 6 6 5 2 8 3 8 0 6 6 4
5 10 5 6 5 8 7 7 8 3 5 7 5 6 7 5 6 0 7 5
5 9 5 4 5 7 9 5 7 5 4 5 7 4 7 3 6 7 0 3
5 7 5 2 4 5 7 3 5 3 3 3 5 6 5 5 4 5 3 0

Test 6 ~(k_j = 86)~

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

Huy có một dãy số ~a_1, a_2, ..., a_n~. Huy có thể thực hiện ~k~ lần biến đổi, mỗi lần Huy có thể thay đổi một chữ số trong dãy. Huy muốn tổng các số chia hết cho ~9~ trong dãy là lớn nhất có thể. Bạn hãy tìm cách để Huy có thể biến đổi dãy số thỏa mãn yêu cầu. Lưu ý rằng sau khi biến đổi có thể có một hoặc nhiều số bắt đầu bằng chữ số ~0~.

Dữ liệu - Nhập từ tệp văn bản DIV.inp:

• Dòng đầu tiên gồm hai số nguyên dương ~n, k~ ~(1 \le n \le 2000, 0 \le k \le 10000)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.

Kết quả - Ghi ra tệp văn bản DIV.out:

• Một dòng duy nhất gồm tổng các số chia hết cho ~9~ trong dãy sau khi biến đổi.

Chấm điểm

Ví dụ

Dữ liệu (DIV.inp)

4 2
28 4 20 7

Kết quả (DIV.out)

117

Giải thích

Huy có thể thay đổi chữ số cuối cùng của phần tử đầu tiên thành chữ số ~7~, sau đó thay đổi chữ số đầu tiên của phần từ thứ ba thành chữ số ~9~ để được tổng ~27 + 90 = 117~. Có thể thấy đây là tổng lớn nhất có thể tạo được.

Cho dãy số nguyên dương ~n~ phần tử ~a_1, a_2, ..., a_n~. Nhiệm vụ của bạn là đếm số lượng đoạn con liên tiếp ~a[l...r]~ sao cho ~1 \le l \le r \le n~ và số lần xuất hiện của các phần tử trong dãy phải nhiều hơn ~1~.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~.
• Dòng thứ hai chữa dãy số nguyên ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le n)~.

Kết quả

• In ra số dãy con liên tiếp thoả mãn yêu cầu đề bài.

Chấm điểm

Ví dụ 1

Dữ liệu

4
1 2 2 1

Kết quả

2

Giải thích

• Có 2 đoạn con thoả mãn, gồm: ~[2, 3]~, ~[1, 4]~

Ví dụ 2

Dữ liệu

5
3 6 3 3 3

Kết quả

3

Đếm số lượng dãy số nguyên ~a_1, a_2, ..., a_N~ thỏa mãn:

• ~a_1 < a_2 < ... < a_N~
• ~L_i \le a_i \le R_i~ với mọi ~i~.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(1 \le N \le 200)~.
• ~N~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~L_i, R_i~ ~(1 \le L_i \le R_i \le 10^9)~.

Kết quả

• Một dòng duy nhất là số lượng dãy số tìm được. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho ~10^9 + 7~.

Chấm điểm

Ví dụ

Dữ liệu

3
1 4
3 3
2 5

Kết quả

4

Giải thích

• Có 4 dãy thỏa mãn là: ~(1, 3, 4), (2, 3, 4), (1, 3, 5), (2, 3, 5)~.

Cho một cây có ~n~ đỉnh, ~n - 1~ cạnh. Mỗi cạnh nối hai đỉnh ~u_i, v_i~ và có trọng số là ~w_i~. Khoảng cách giữa hai đỉnh trên cây là tổng trọng số các cạnh của đường đi đơn giữa hai đỉnh. Ban đầu có ~k~ đỉnh đặc biệt ~x_1, x_2, ..., x_k~. Bạn cần tính tổng khoảng cách nhỏ nhất từ mỗi đỉnh trên cây đến một trong các đỉnh đặc biệt đó. Có ~q~ truy vấn thay đổi các đỉnh đặc biệt, mỗi truy vấn sẽ xóa ~a~ đỉnh ~y_1, y_2, ..., y_a~ khỏi tập đỉnh, sau đó thêm ~b~ đỉnh ~z_1, z_2, ..., z_b~ vào tập đỉnh. Sau mỗi truy vấn, tính tổng khoảng cách nhỏ nhất từ mỗi đỉnh trên cây đến một trong các đỉnh đặc biệt như trên.

Dữ liệu

• Dòng đầu tiên gồm ba số nguyên ~n, k, q~ ~(1 \le k \le n \le 10^5, 0 \le q \le 400)~.
• Dòng tiếp theo gồm ~k~ số nguyên ~x_1, x_2, ..., x_k~ ~(1 \le x_i \le n)~. Dữ liệu đầu vào đảm bảo các giá trị ~x_i~ đôi một phân biệt.
• ~n - 1~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10000)~.
• Tiếp theo là ~q~ cặp dòng mô tả các truy vấn, mỗi cặp dòng có định dạng như sau:
  • Dòng đầu tiên gồm số nguyên dương ~a~, sau đó là ~a~ số nguyên dương ~y_1, y_2, ..., y_a~ ~(0 \le a \le 200, 1 \le y_i \le n)~. Dữ liệu đầu vào đảm bảo các giá trị ~y_i~ đôi một phân biệt và có trong tập các đỉnh đặc biệt hiện tại.
  • Dòng tiếp theo gồm số nguyên dương ~b~, sau đó là ~b~ số nguyên dương ~z_1, z_2, ..., z_b~ ~(0 \le b \le 200, 1 \le z_i \le n)~. Dữ liệu đầu vào đảm bảo các giá trị ~z_i~ đôi một phân biệt và không có trong tập các đỉnh đặc biệt hiện tại.
• Dữ liệu đầu vào đảm bảo sau mỗi truy vấn thay đổi cây có ít nhất ~1~ đỉnh đặc biệt.

Kết quả

• Dòng đầu tiên gồm một số nguyên là tổng khoảng cách với tập đỉnh đặc biệt ban đầu.
• Tiếp theo là ~q~ dòng, dòng thứ ~i~ là tổng khoảng cách sau truy vấn thay đổi thứ ~i~.

Subtask

Ví dụ

Ví dụ 1

Dữ liệu

5 1 1
1
1 2 3
1 3 4
2 4 3
2 5 1
0
1 2

Kết quả

17
8

Giải thích

Hình minh họa cây ban đầu.

• Có duy nhất đỉnh ~1~ là đỉnh đặc biệt.
• Khoảng cách từ các đỉnh ~1, 2, 3, 4, 5~ đến đỉnh ~1~ lần lượt là ~0, 3, 4, 6, 4~, tổng là ~17~.

Hình minh họa cây sau truy vấn thay đổi.

• Có đỉnh ~1~ và ~2~ là đỉnh đặc biệt.
• Khoảng cách từ các đỉnh ~1, 3~ đến đỉnh ~1~ lần lượt là ~0, 4~.
• Khoảng cách từ các đỉnh ~2, 4, 5~ đến đỉnh ~2~ lần lượt là ~0, 3, 1~.
• Tổng khoảng cách là ~8~.

Trên một con đường có hai hàng cột đèn chiếu sáng. Hàng bên trái gồm ~n~ cột đèn, hàng bên phải gồm ~m~ cột đèn. Các cột đèn ở bên trái được đặt thẳng hàng với nhau, các cột đèn ở bên phải được đặt thẳng hàng với nhau. Tất cả các cột đèn đều có cùng chiều cao. Một hôm, Huy đi qua con đường này và chợt nghĩ ra một bài toán rất thú vị: Có bao nhiêu cách nối các đường dây điện cho các cột đèn này, sao cho:

• Sử dụng chính xác ~n+m-1~ đường dây điện.
• Mỗi đường dây điện nối chính xác 2 cột đèn.
• Với mọi cặp cột đèn bất kỳ, luôn tồn tại một đường đi giữa hai cột đèn này (trực tiếp qua một đường dây điện hoặc gián tiếp thông qua các dây điện và cột đèn trung gian).
• Khi tất cả các dây điện đều được căng ra, hai dây điện bất kỳ không được có điểm chung nào trừ cột đèn là đầu mút chung của chúng (nếu có).

Huy suy nghĩ rất lâu vẫn chưa thể tìm ra cách giải bài toán. Bạn hãy thử giải bài toán này cùng Huy nhé.

Dữ liệu - Nhập từ tệp văn bản CONNECT.inp:

• Một dòng duy nhất gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 5000)~.

Kết quả - Ghi ra tệp văn bản CONNECT.out:

• Một dòng duy nhất gồm phần dư của kết quả tìm được khi chia cho ~10^9 + 7~.

Chấm điểm

Ví dụ

Dữ liệu (CONNECT.inp)

2 2

Kết quả (CONNECT.out)

12

Giải thích

Có tổng cộng 12 cách nối dây như liệt kê ở hình trên.