Châu cần ship ~V~ lít cồn qua NUS. Để làm được điều đó, cậu cần đóng một chiếc thùng có dạng hình hộp chữ nhật có độ dài các cạnh là số nguyên và có thể tích đúng bằng ~V~. Châu muốn bạn giúp tính toán xem diện tích bề mặt nhỏ nhất có thể của chiếc thùng có thể làm được điều đó là bao nhiêu.

Input

• Gồm một số nguyên dương ~V~ duy nhất ~(1 \le V \le 10^7)~.

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): ~V \le 100~
• Subtask ~2~ (~30\%~ số điểm): ~V \le 5000~
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm

Sample Input 1

12

Sample Output 1

32

Explaination

Chiếc thùng có kích cỡ ~2 \times 2 \times 3~

Trong giờ học Toán tuần này, Bảo đang học về phép nhân. Cậu có 2 số ~A~ và ~B~, khi nhân lại thì thu được kết quả là ~C~. Tuy nhiên, do bất cẩn, cậu đã làm đổ nước lên giấy nên có một vị trí trong số ~C~ bị nhoè đi. Bảo muốn nhờ bạn giúp để tính lại xem chữ số bị nhoè đi là bao nhiêu.

Input

• Dòng đầu chứa số nguyên dương ~T~ - số thứ tự của subtask.
• Dòng thứ hai chứa số nguyên dương ~A~ (~A~ có không quá ~10^6~ chữ số).
• Dòng thứ ba chứa số nguyên dương ~B~ (~B~ có không quá ~10^6~ chữ số).
• Dòng thứ tư chứa số nguyên dương ~C~ (~C~ có không quá ~2 \times 10^6~ chữ số).

Trong dòng chứa số ~C~ có một vị trí bị thay bằng dấu ~*~, đại diện cho vị trí bị nhoè.

Output:

• In ra một chữ số là kết quả của bài toán.

Subtask:

• Subtask ~1~ (~15\%~ số điểm): ~A, B \le 100~
• Subtask ~2~ (~30\%~ số điểm): Số chữ số của ~A~, ~B~ không vượt quá ~100~; Chữ số bị nhoè chắc chắn không phải ~0~
• Subtask ~3~ (~30\%~ số điểm): Chữ số bị nhoè chắc chắn không phải ~0~
• Subtask ~4~ (~25\%~ số điểm): Không có ràng buộc gì thêm

Sample Input 1

1
10
10
*00

Sample Output 1

1

Trên mặt phẳng toạ độ vô hạn, người ta xây nhà tại tất cả các toạ độ ~(x, y)~ khi và chỉ khi ~x~ và ~y~ đồng thời là số nguyên tố. Để cung cấp điện cho những ngôi nhà này, chính phủ có ~q~ dự án đặt trạm phát điện chuẩn bị đưa vào triển khai.

Ở dự án thứ ~i~, chính phủ dự kiến sẽ xây trạm phát điện ở toạ độ ~(X_i, Y_i)~ và trạm phát điện này sẽ cung cấp điện cho tất cả những ngôi nhà nằm trong khu vực hình chữ nhật có 2 đỉnh đối nhau là ~(u_i, \ v_i)~ và ~(p_i, q_i)~. Chi phí để tải điện từ trạm điện đặt ở toạ độ ~(a, b)~ đến ngôi nhà đặt ở toạ độ ~(c, d)~ chính là khoảng cách Manhattan giữa chúng. Cụ thể hơn, chi phí được tính bằng công thức: ~|a - c| + |b - d|~.

Với mỗi dự án, hãy cho biết chi phí truyền tải điện của dự án đó là bao nhiêu.

Lưu ý rằng các dự án này đều là giả định, và độc lập với nhau.

Input

• Dòng đầu tiên chứa số nguyên dương ~Q~ ~(1 \le Q \le 10^5)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa sáu số nguyên dương ~X_i, Y_i, u_i, v_i, p_i, q_i~ ~(1 \le u_i \le X_i \le p_i \le 10^6; \ 1 \le v_i \le Y_i \le q_i \le 10^6)~.

Output:

• In ra ~q~ dòng, dòng thứ ~i~ chứa một số nguyên không âm là kết quả của giả định thứ ~i~.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~X_i, Y_i, u_i, v_i, p_i, q_i \le 100 \ \forall i~; ~Q \le 10^4~
• Subtask ~2~ (~25\%~ số điểm): ~u_i = p_i = 2; \ (X_i, Y_i) = (p_i, q_i) \ \forall i~
• Subtask ~3~ (~25\%~ số điểm): ~(X_i, Y_i) = (p_i, q_i) \ \forall i~
• Subtask ~4~ (~25\%~ số điểm): Không có ràng buộc gì thêm

Sample Input 1

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

Sample Output 1

4 
0
24

Explaination

Dưới đây là hình vẽ cho ~3~ giả định

Lớp ~12~ tin có ~n~ bạn học sinh. Lớp dự định sẽ tổ chức đi chơi tốt nghiệp tại đảo Phú Quốc. Tuy nhiên, chuyến tàu ra đảo chỉ có thể chở tối đa ~k~ hành khách nên lớp chỉ có thể chọn ra tối đa ~k~ bạn để tham gia chuyến đi chơi này.

Mỗi bạn học sinh đều có những người bạn mà mình muốn đi chơi cùng. Bạn thứ ~i~ muốn đi cùng ~f_i~ người bạn là ~a_{i, 1}, a_{i, 2}, \ldots, a_{i, f_i}~. Tất cả học sinh đều đồng ý rằng, mình sẽ chỉ tham gia chuyến đi chơi nếu tất cả những người bạn mình muốn đi cùng đều tham gia vào chuyến đi. Lưu ý có thể tồn tại bạn ~a_{i,k}=i~.

Hãy giúp MrTee giải quyết vấn đề trên bằng cách chọn ra nhiều bạn nhất có thể để tham gia vào chuyến đi này nhé.

Lưu ý rằng bạn ~A~ muốn đi cùng bạn ~B~ không đồng nghĩa với việc bạn ~B~ muốn đi cùng bạn ~A~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, k~ ~(1 \le k \le n \le 1000)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ có dạng như sau:
  • Số nguyên không âm đầu tiên là ~f_i~ - số lượng người bạn mà học sinh thứ ~i~ muốn đi chơi cùng.
  • Theo sau là ~f_i~ số nguyên dương ~a_{i, 1}, a_{i, 2}, \ldots, a_{i, f_i}~ ~(1 \le a_u \le n)~ - danh sách các học sinh mà bạn thứ ~i~ muốn đi chơi cùng.

Tổng ~F = f_1 + f_2 + \ldots + f_n~ không vượt quá 5000.

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~
• Subtask ~2~ (~20\%~ số điểm): ~f_i = 1 \ \forall i~; Mỗi học sinh chỉ xuất hiện trong danh sách người bạn muốn đi chơi cùng của chính xác ~1~ học sinh khác
• Subtask ~3~ (~20\%~ số điểm): ~i - 7 \le a_{i, 1}, a_{i, 2}, \ldots, a_{i, f_i} \le i - 1 \ \forall i~
• Subtask ~4~ (~20\%~ số điểm): ~f_i = 1 \ \forall i~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample Input 1

4 2
2 2 3
1 3
2 2 1
0

Sample Output 1

1

Sample Input 2

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

Sample Output 2

3

Explaination

Ở ví dụ đầu tiên, MrTee chỉ có thể chọn bạn ~4~ tham gia vào chuyến đi chơi.

Ở ví dụ thứ hai, MrTee có thể chọn các bạn ~1, 2, 3~ tham gia vào chuyến đi chơi.

Đất nước HNAms gồm ~n~ hộ gia đình, được đánh số từ ~1~ tới ~n~.

Kì bầu cử tổng thống đang được diễn ra. Kì này có ~m~ ứng cử viên được đánh số từ ~1~ tới ~m~ cùng tranh suất vào vị trí lãnh đạo đất nước. Mỗi hộ gia đình bầu một ứng cử viên, hộ thứ ~i~ bầu ứng cử viên ~a_i~. Một ứng cử viên được coi là chiến thắng nếu giành lợi thế đa số (nói cách khác, giành được ít nhất ~\left\lfloor \frac{K}{2} \right\rfloor + 1~ phiếu bầu nếu có tổng cộng ~K~ phiếu).

Hội đồng bầu cử đang chuẩn bị cho ~q~ tình huống có thể xảy ra trong giai đoạn bầu cử. Mỗi tình huống thuộc một trong hai loại sau:

• "~1~ ~X~ ~Y~" - hộ gia đình ~X~ chuyển sang bầu cử ứng cử viên ~Y~.
• "~2~ ~L~ ~R~" - giả sử phiếu bầu của tất cả các hộ có chỉ số nằm ngoài đoạn ~[L,R]~ bị hủy, hãy tìm ứng cử viên chiến thắng trong kì bầu cử này.

Hãy giúp hội đồng bầu cử xử lý ~q~ tình huống trên. Với mỗi tình huống thuộc loại thứ hai, nếu tồn tại ứng cử viên giành chiến thắng thì in ra chỉ số của ứng viên đó, ngược lại in ra ~-1~.

Input

• Dòng đầu gồm ba số nguyên ~n,m,q~ ~(1 \le n,m,q \le 5 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(1 \le a_i \le m)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một tình huống thuộc một trong hai loại sau:
  • "~1~ ~X~ ~Y~" ~(1 \le X \le n; 1 \le Y \le m)~
  • "~2~ ~L~ ~R~" ~(1 \le L \le R \le n)~.

Output:

• Với mỗi tình huống thuộc loại thứ hai, hãy in ra chỉ số của ứng viên giành chiến thắng nếu tồn tại, ngược lại in ra ~-1~.

Subtask:

• Subtask ~1~ (~20\%~ số điểm): ~n,q \le 1000~
• Subtask ~2~ (~20\%~ số điểm): ~n,q \le 10^5~; không có tình huống nào thuộc loại thứ nhất.
• Subtask ~3~ (~20\%~ số điểm): ~n,q \le 10^5~; ~m \le 20~.
• Subtask ~4~ (~20\%~ số điểm): ~n,q \le 10^5~.
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1
1
-1
2

Explaination

Ở truy vấn đầu tiên, tất cả mọi người trong đoạn ~[1,2]~ đều bầu cho ứng cử viên số ~1~ nên người này sẽ chiến thắng.

Ở truy vấn thứ tư, hộ gia đình thứ ~2~ đã đổi sang bầu cử cho ứng cử viên số hai, dẫn tới có ~2~ trên ~3~ hộ gia đình trong đoạn ~[1,3]~ bầu cho ứng cử viên số ~2~, vậy nên người này chiến thắng ở truy vấn thứ ~5~.

Vùng đất Ams có ~n~ thành phố tạo thành cấu trúc cây. Bạn đang chơi game nhập vai ở vùng đất này. Thành phố thứ ~i~ có NPC sẽ đưa cho bạn nhiệm vụ cấp độ ~a_i~.

Thành phố tân thủ là thành phố ~1~, có NPC phát nhiệm vụ cấp độ thấp nhất: cấp độ ~1~. Thành phố đích đến là thành phố ~n~, có NPC phát nhiệm vụ cấp độ cao nhất: cấp độ ~m~. Mỗi ngày, bạn có thể di chuyển từ thành phố hiện tại tới một thành phố kề nó.

Để vượt qua trò chơi, bạn cần tìm một lộ trình để hoàn thành tất cả ~m~ cấp độ nhiệm vụ của NPC, cụ thể như sau:

• Với mỗi cấp độ từ ~2~ đến ~m-1~, bạn cần chọn ra một thành phố có NPC cung cấp nhiệm vụ cấp độ đó. Gọi các thành phố mà bạn muốn đến để hoàn thành các nhiệm vụ đó lần lượt là ~u_2, u_3, …, u_{m-1}~. Đồng thời, gọi ~u_1 = 1, u_m = n~.
• Di chuyển từ ~u_1~, đi đến ~u_2~, rồi đến ~u_3~, …, cuối cùng đến ~u_m~ để lần lượt hoàn thành các nhiệm vụ ở các thành phố này.
• Để di chuyển giữa hai thành phố, bạn luôn lựa chọn sử dụng cách đi tốn ít thời gian nhất (đường đi ngắn nhất giữa hai thành phố đó trên cây). Bạn có thể đi qua thành phố có nhiệm vụ cấp cao để di chuyển giữa các thành phố cấp độ thấp hơn, tuy nhiên khi đó bạn vẫn chưa được tính là hoàn thành nhiệm vụ cấp cao.
• Thời gian hoàn thành của lộ trình này là tổng số ngày để di chuyển giữa các thành phố.

Có rất nhiều cách chọn ra lộ trình các thành phố ~u_1, u_2, …, u_m~ như vậy để hoàn thành trò chơi. Là một người nghiện game ham học hỏi, Quân muốn khám phá hết các cách hoàn thành trò chơi. Do đó, Quân nhờ bạn tính xem, tổng thời gian để hoàn thành của tất cả các lộ trình hoàn thành được trò chơi là bao nhiêu. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le m \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le m; \ a_1 = 1; \ a_n = m)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ ~(1 \le u, v \le n)~ mô tả các cạnh của cây.

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~
• Subtask ~2~ (~20\%~ số điểm): ~n \le 100~
• Subtask ~3~ (~20\%~ số điểm): ~n \le 5000~
• Subtask ~4~ (~20\%~ số điểm): Cây có dạng đường thẳng
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample Input 1

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

Sample Output 1

24

Explaination

Số màu đỏ ở dưới mỗi thành phố là cấp độ của nhiệm vụ ở thành phố đó. Các lộ trình để hoàn thành trò chơi:

• ~1 → 2 → 3 → 6~. Thời gian di chuyển: ~dist(1, 2) + dist(2, 3) + dist(3, 6) = 2 + 1 + 1 = 4~
• ~1 → 2 → 4 → 6~. Thời gian di chuyển: ~dist(1, 2) + dist(2, 4) + dist(4, 6) = 2 + 2 + 2 = 6~
• ~1 → 5 → 3 → 6~. Thời gian di chuyển: ~dist(1, 5) + dist(5, 3) + dist(3, 6) = 3 + 2 + 1 = 6~
• ~1 → 5 → 4 → 6~. Thời gian di chuyển: ~dist(1, 5) + dist(5, 4) + dist(4, 6) = 3 + 3 + 2 = 8~

Vậy đáp án là ~4 + 6 + 6 + 8 = 24~