Sau một chuyến du lịch liên hành tinh, thầy Nam trở về từ hành tinh An Bình. Điểm đặc biệt của hành tinh này là một ngày có đúng ~M~ giờ. Thầy Nam mua ~N~ chiếc đồng hồ chưa được chỉnh giờ ở An Bình. Mỗi đồng hồ có một màn hình hiển thị giờ hiện tại bằng một số từ ~0~ đến ~M-1~.

Các đồng hồ này không hoạt động mãi mãi: đồng hồ thứ ~i~ hoạt động đúng ~a_i~ giờ rồi dừng hẳn và không hiển thị gì nữa. Tại thời điểm mua, đồng hồ thứ ~i~ đang bắt đầu hiển thị giờ ~b_i~. Ví dụ, nếu ~M=7~ và một đồng hồ đang bắt đầu hiển thị giờ ~b_i=5~ lúc mua, đồng thời còn hoạt động trong ~a_i=4~ giờ, thì đồng hồ đó lần lượt hiển thị các giờ ~5, 6, 0, 1~, sau đó dừng hoạt động.

Thầy Nam muốn trả lời ~Q~ truy vấn. Mỗi truy vấn được cho bởi một số ~t_i~; với truy vấn này, cần tính tổng ~s_1 + \dots + s_N~, trong đó ~s_j~ là số lần màn hình của đồng hồ thứ ~j~ hiển thị giờ ~t_i~ trước khi đồng hồ đó dừng hoạt động.

Hãy giúp thầy Nam trả lời tất cả các truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(1 \le N \le 2 \cdot 10^5, 1 \le M \le 10^9)~: số đồng hồ và số giờ trong một ngày ở hành tinh An Bình.

• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~ và ~b_i~ ~(1 \le a_i \le 10^{12}, 0 \le b_i < M)~: số giờ đồng hồ thứ ~i~ còn hoạt động và giờ mà đồng hồ đó hiển thị tại thời điểm mua.

• Dòng tiếp theo chứa một số nguyên ~Q~ ~(1 \le Q \le 2 \cdot 10^5)~: số truy vấn.

• Trong ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên ~t_i~ ~(0 \le t_i < M)~.

Output

Ghi ra ~Q~ dòng, dòng thứ ~i~ là câu trả lời cho truy vấn thứ ~i~.

Scoring

Sample Input 1

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

Sample Output 1

6
4
4
5
5
6
7
8

Notes

• Đồng hồ thứ nhất lần lượt hiển thị các giờ ~6, 7, 0, 1, 2, 3, 4, 5, 6, 7~.

• Đồng hồ thứ ba hoạt động đúng ~16~ giờ, tức là đi qua trọn vẹn hai ngày ở An Bình, nên đóng góp ~2~ lần cho mỗi giờ từ ~0~ đến ~7~.

• Khi cộng đóng góp của tất cả đồng hồ, số lần xuất hiện của các giờ ~0, 1, 2, 3, 4, 5, 6, 7~ lần lượt là ~6, 4, 4, 5, 5, 6, 7, 8~.

• Vì các truy vấn trong ví dụ lần lượt hỏi các giờ từ ~0~ đến ~7~, kết quả chính là các số trên theo đúng thứ tự.

An dự định bay tới Đà Lạt, nhưng vì nhầm chuyến nên lại đáp xuống sân bay ở Sa Pa. Cậu nhanh chóng đặt một phòng khách sạn trong thị trấn và phải đi bộ tới đó trong đêm lạnh. Khách sạn của An nằm ở cuối một con đường dài ~N~ mét. Trên con đường này có ~N-1~ cửa hàng quần áo; cửa hàng thứ ~i~ nằm cách sân bay đúng ~i~ mét.

An chỉ đi theo hướng từ sân bay tới khách sạn. Khi đi ngang qua cửa hàng thứ ~i~, cậu có thể chọn một trong ba cách:

• tiếp tục đi mà không vào cửa hàng;

• vào cửa hàng để sưởi ấm, trả ~1~ đồng và không mua gì;

• vào cửa hàng, trả ~1~ đồng và mua thêm một lớp áo với giá ~A_i~ đồng.

An muốn tránh bị lạnh, nên trong suốt hành trình, cậu không được đi liên tiếp số mét nhiều hơn số lớp áo đang mặc mà không vào một cửa hàng nào. Ban đầu, khi vừa tới sân bay, An đang mặc đúng một lớp áo.

Hãy tính số tiền ít nhất An cần trả để tới được khách sạn.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 10^5)~: độ dài con đường.

• Dòng thứ hai chứa ~N-1~ số nguyên ~A_1, A_2, \dots, A_{N-1}~ ~(1 \le A_i \le 10^9)~: giá mua thêm một lớp áo ở từng cửa hàng.

Output

Ghi ra một số nguyên duy nhất là số tiền ít nhất An cần trả.

Scoring

Sample Input 1

8
5 1 9 1 9 9 9

Sample Output 1

5

Sample Input 2

10
6 4 2 7 1 8 3 9 5

Sample Output 2

8

Notes

Trong ví dụ thứ nhất, An có thể vào cửa hàng thứ nhất để sưởi ấm, mua thêm một lớp áo ở cửa hàng thứ hai, rồi vào cửa hàng thứ tư và thứ sáu để sưởi ấm. Tổng chi phí là ~1 + (1+1) + 1 + 1 = 5~.

Trong ví dụ thứ hai, An có thể vào cửa hàng thứ nhất và thứ hai để sưởi ấm, mua thêm áo ở cửa hàng thứ ba và thứ năm, rồi vào cửa hàng thứ bảy để sưởi ấm. Tổng chi phí là ~1 + 1 + (1+2) + (1+1) + 1 = 8~.

Ở thị trấn Lạc Sơn có ~N~ căn nhà được đánh số từ ~1~ đến ~N~ và ~M~ người dân được đánh số từ ~1~ đến ~M~. Mỗi người sống trong đúng một căn nhà, và mỗi căn nhà có nhiều nhất một người ở. Các căn nhà nằm trên sườn núi. Với mỗi nhà ~i~, có một đường trượt một chiều từ nhà ~i~ tới nhà ~r_i~. Có đúng một nhà ~s~ thỏa mãn ~r_s=s~; đây là nhà ở chân núi. Nếu xem mỗi đường trượt là một cạnh hướng về chân núi, các cạnh này tạo thành một cây gốc tại ~s~. Vì vậy từ một căn nhà bất kỳ, đi theo các đường trượt sẽ dẫn tới chân núi.

Những người dân quen biết nhau theo một vòng tròn: người ~i~ quen người ~i-1~ và ~i+1~; riêng người ~1~ quen người ~2~ và ~M~, người ~M~ quen người ~M-1~ và ~1~.

Có ~Q~ sự kiện, thuộc một trong hai loại:

• Loại ~1~: cho hai nhà ~a, b~. Nếu cả hai nhà đều có người, hai người đang sống ở hai nhà này đổi chỗ cho nhau. Nếu một trong hai nhà trống thì người ở nhà còn lại chuyển sang nhà trống đó; nếu cả hai nhà đều trống thì không có gì thay đổi.

• Loại ~2~: cho một người ~p~ và một số ~R~. Người ~p~ muốn tổ chức một bữa tiệc. Cậu ta được chọn một trong hai hướng quanh vòng tròn bạn bè, rồi mời một đoạn liên tiếp bắt đầu từ ~p~ theo hướng đó. Nói cách khác, nếu mời ~K~ người thì người ~p~ là một trong hai đầu của đoạn gồm ~K~ người liên tiếp trên vòng tròn. Một nhóm khách mời hợp lệ nếu tồn tại một căn nhà làm địa điểm tổ chức sao cho mọi người trong nhóm có thể đi từ nhà hiện tại của mình tới địa điểm đó bằng không quá ~R~ đường trượt.

Với mỗi sự kiện loại ~2~, hãy tìm số người lớn nhất có thể được mời.

Input

• Dòng đầu tiên chứa ba số nguyên ~N, M, Q~ ~(1 \le M \le N \le 10^5, 1 \le Q \le 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên ~r_1, r_2, \dots, r_N~ ~(1 \le r_i \le N)~. Có đúng một chỉ số ~s~ sao cho ~r_s=s~, và các đường trượt tạo thành một cây gốc tại ~s~.

• Dòng thứ ba chứa ~M~ số nguyên ~h_1, h_2, \dots, h_M~ ~(1 \le h_i \le N)~, trong đó ~h_i~ là nhà ban đầu của người ~i~. Các giá trị ~h_i~ đôi một khác nhau.

• Trong ~Q~ dòng tiếp theo, mỗi dòng mô tả một sự kiện:

  • ~1\ a\ b~ ~(1 \le a,b \le N, a \ne b)~: đổi cư dân của hai nhà ~a~ và ~b~.

  • ~2\ p\ R~ ~(1 \le p \le M, 1 \le R < N)~: truy vấn bữa tiệc do người ~p~ tổ chức với giới hạn ~R~ đường trượt.

Output

Với mỗi sự kiện loại ~2~, in ra một dòng chứa số người lớn nhất có thể được mời.

Scoring

Sample Input 1

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

Sample Output 1

1
2
1
2
2
2

Notes

• Ở truy vấn đầu tiên, người ~1~ đang ở nhà ~4~. Với ~R=1~, nếu mời thêm người kề bên nào trên vòng tròn thì địa điểm chung gần nhất đều quá xa, nên chỉ mời được một người.

• Ở truy vấn thứ hai, người ~2~ đang ở nhà ~7~ và ~R=2~. Có thể mời thêm người ~3~ ở nhà ~5~ rồi chọn nhà ~1~ làm địa điểm tổ chức, nhưng không thể mời ba người cùng lúc.

• Sau sự kiện ~1\ 7\ 6~, người ~2~ chuyển từ nhà ~7~ sang nhà ~6~. Vì vậy ở truy vấn tiếp theo với ~R=1~, người ~2~ không thể mời thêm người nào. Sau sự kiện ~1\ 4\ 8~, người ~1~ và người ~4~ đổi chỗ; khi người ~4~ làm chủ tiệc với ~R=1~, có thể mời thêm người ~3~ và chọn nhà ~2~ làm địa điểm tổ chức.

Mình đang khảo sát ~N~ vùng biển, được đánh số từ ~1~ đến ~N~. Vùng biển thứ ~i~ có ~c_i~ hòn đảo, diện tích của các đảo lần lượt là ~s_{i,1}, s_{i,2}, \dots, s_{i,c_i}~ mét vuông.

Mình có ~Q~ truy vấn. Với mỗi truy vấn cho một số nguyên ~A~. Mình chỉ xét những đảo có diện tích ít nhất ~A~ mét vuông. Hãy tìm vùng biển có nhiều đảo được xét nhất. Nếu có nhiều vùng biển cùng đạt số lượng lớn nhất, hãy chọn vùng biển có chỉ số lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 10^5)~: số vùng biển và số truy vấn.

• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ mô tả vùng biển thứ ~i~. Dòng này bắt đầu bằng số nguyên ~c_i~ ~(1 \le c_i \le 3 \cdot 10^5)~, tiếp theo là ~c_i~ số nguyên ~s_{i,1}, s_{i,2}, \dots, s_{i,c_i}~ ~(1 \le s_{i,j} \le 10^9)~: diện tích các đảo của vùng biển đó.

• Trong ~Q~ dòng cuối cùng, mỗi dòng chứa một số nguyên ~A~ ~(1 \le A \le 10^9)~, là ngưỡng diện tích của một truy vấn.

Gọi ~T = c_1 + c_2 + \dots + c_N~ là tổng số đảo. Dữ liệu đảm bảo ~T \le 3 \cdot 10^5~.

Output

• Với mỗi truy vấn, in ra một dòng chứa chỉ số của vùng biển có số lượng đảo có diện tích ít nhất ~A~ là lớn nhất. Nếu có nhiều vùng biển thỏa mãn, in ra chỉ số lớn nhất trong số đó.

Scoring

Sample Input 1

4 5
5 2 5 5 9 12
4 1 5 8 12
3 6 6 15
5 3 4 10 10 11
5
10
12
13
1

Sample Output 1

1
4
3
3
4

Notes

Với ~A = 5~, số đảo được xét của bốn vùng biển lần lượt là ~4, 3, 3, 3~, nên đáp án là ~1~. Với ~A = 10~, vùng biển ~4~ có ~3~ đảo được xét, nhiều nhất trong bốn vùng biển. Với ~A = 12~, các vùng biển ~1, 2, 3~ cùng có ~1~ đảo được xét, nên chọn chỉ số lớn nhất là ~3~. Với ~A = 1~, vùng biển ~1~ và ~4~ cùng có ~5~ đảo được xét, nên đáp án là ~4~.

Ở trường YYY có ~N~ học sinh, được đánh số từ ~1~ đến ~N~. Học sinh thứ ~i~ có kỹ năng chơi bóng chuyền là ~S_i~ và độ nổi tiếng là ~P_i~.

Thầy Minh muốn chọn hai đội bóng chuyền. Mỗi đội phải có ít nhất một học sinh, mỗi học sinh được chọn vào nhiều nhất một đội, và không bắt buộc phải chọn hết tất cả học sinh. Để trận đấu công bằng, tổng kỹ năng của hai đội phải bằng nhau.

Đội trưởng của một đội là học sinh có độ nổi tiếng lớn nhất trong đội đó. Nếu có nhiều học sinh cùng đạt độ nổi tiếng lớn nhất, chọn ai trong số họ làm đội trưởng cũng cho cùng một giá trị độ nổi tiếng của đội trưởng. Độ hấp dẫn của trận đấu được định nghĩa là giá trị tuyệt đối của hiệu độ nổi tiếng giữa hai đội trưởng.

Hãy tìm độ hấp dẫn lớn nhất có thể của một trận đấu công bằng.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 1000)~: số học sinh.

• Dòng thứ hai chứa ~N~ số nguyên ~S_1, S_2, \dots, S_N~ ~(1 \le S_i)~: kỹ năng của các học sinh.

• Dòng thứ ba chứa ~N~ số nguyên ~P_1, P_2, \dots, P_N~ ~(1 \le P_i \le 10^9)~: độ nổi tiếng của các học sinh.

Gọi ~T = S_1 + S_2 + \dots + S_N~. Dữ liệu đảm bảo ~1 \le T \le 10^5~.

Output

In ra một số nguyên duy nhất là độ hấp dẫn lớn nhất có thể. Dữ liệu đảm bảo luôn tồn tại cách chọn hai đội thỏa mãn điều kiện.

Scoring

Sample Input 1

8
4 7 3 8 5 6 9 2
15 3 20 11 8 30 6 25

Sample Output 1

24

Notes

Có thể chọn đội thứ nhất gồm học sinh ~2~ và ~7~, có tổng kỹ năng ~7+9=16~ và độ nổi tiếng đội trưởng là ~6~. Đội thứ hai gồm học sinh ~3, 5, 6, 8~, có tổng kỹ năng ~3+5+6+2=16~ và độ nổi tiếng đội trưởng là ~30~. Độ hấp dẫn khi đó là ~30-6=24~, và không thể đạt giá trị lớn hơn.

Tỉnh ZZZ có ~N~ thành phố, được đánh số từ ~0~ đến ~N-1~, và ~N-1~ con đường hai chiều. Từ mỗi thành phố luôn có thể đi đến mọi thành phố khác bằng một dãy các con đường. Khoảng cách giữa hai thành phố là số con đường ít nhất cần đi qua để di chuyển từ thành phố này đến thành phố kia.

Hai cán bộ Nam và Huy cần thực hiện một chuyến tuần tra toàn tỉnh. Ban đầu Nam đứng ở thành phố ~X~, Huy đứng ở thành phố ~Y~. Mỗi ngày, đúng một trong hai người di chuyển từ thành phố hiện tại sang một thành phố kề với nó qua một con đường. Chuyến tuần tra kết thúc khi cả Nam và Huy đều đã từng đến tất cả các thành phố ít nhất một lần và cả hai quay lại đúng thành phố xuất phát của mình.

Độ an toàn của một chuyến tuần tra là khoảng cách nhỏ nhất giữa Nam và Huy trong suốt chuyến đi, tính cả thời điểm ban đầu và các thời điểm sau mỗi lần di chuyển. Với mỗi truy vấn ~(X,Y)~, hãy tìm độ an toàn lớn nhất có thể đạt được nếu Nam bắt đầu ở ~X~ và Huy bắt đầu ở ~Y~.

Input

• Dòng đầu tiên chứa ba số nguyên ~S, N~ và ~Q~ ~(1 \le S \le 5, 1 \le N \le 2 \cdot 10^5, 1 \le Q \le 10^5)~: chỉ số subtask của test, số thành phố và số truy vấn.

• Trong ~N-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~A_i~ và ~B_i~ ~(0 \le A_i,B_i < N)~, mô tả một con đường nối hai thành phố ~A_i~ và ~B_i~.

• Trong ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~X~ và ~Y~ ~(0 \le X,Y < N)~, mô tả một truy vấn.

Dữ liệu đảm bảo các con đường tạo thành một cây.

Output

In ra ~Q~ dòng. Dòng thứ ~j~ chứa một số nguyên là độ an toàn lớn nhất cho truy vấn thứ ~j~.

Scoring

Sample Input 1

1 13 5
0 1
1 2
2 3
0 4
4 5
5 6
0 7
7 8
8 9
0 10
10 11
11 12
3 6
3 2
1 10
12 9
0 3

Sample Output 1

3
1
2
3
3

Notes

Xét truy vấn đầu tiên ~(3,6)~. Một cách đạt độ an toàn ~3~ là cho hai người luân phiên đứng chờ ở một lá của cây, còn người kia đi từ lá hiện tại qua thành phố ~0~ sang một lá thuộc nhánh khác. Cụ thể, có thể thực hiện lần lượt các đoạn sau:

• Nam đi ~3 \rightarrow 9~, Huy đứng tại ~6~.

• Huy đi ~6 \rightarrow 12~, Nam đứng tại ~9~.

• Nam đi ~9 \rightarrow 6~, Huy đứng tại ~12~.

• Huy đi ~12 \rightarrow 3~, Nam đứng tại ~6~.

• Nam đi ~6 \rightarrow 12~, Huy đứng tại ~3~.

• Huy đi ~3 \rightarrow 9~, Nam đứng tại ~12~.

• Nam đi ~12 \rightarrow 3~, Huy đứng tại ~9~.

• Huy đi ~9 \rightarrow 6~, Nam đứng tại ~3~.