Trong một bảo tàng lịch sử nổi tiếng, người quản lí đang được giao nhiệm vụ bảo quản một bản đồ cổ vốn đã trải qua hàng trăm năm. Theo thời gian, để tiện lưu trữ, bản đồ đã được gấp lại nhiều lần tại những nếp gấp khác nhau. Bản đồ có ~N+1~ nếp gấp cách đều nhau được đánh số từ ~0~ đến ~N~ từ mép trái qua mép phải. Mỗi lần gấp tại nếp gấp vị trí ~X~, phần bản đồ ngắn hơn sẽ được gấp chồng lên phần còn lại. Trường hợp hai phần bằng nhau thì gấp phần bản đồ bên trái lên phần bên phải. Sau ~K~ lần gấp như thế, tại cùng một vị trí có thể có nhiều nếp gấp. Giả sử độ dày của bản đồ sau các lần gấp tăng không đáng kể.

Một ngày nọ, khi bảo tàng tổ chức triển lãm tấm bản đồ cổ, ông quản lí đặt tấm bản đồ đã được gấp trên mặt bàn để kiểm tra. Sau khi quan sát, ông muốn biết số nếp gấp chồng lên nhau tại những vị trí nếp gấp tiếp xúc với mặt bàn.

Yêu cầu: Hãy viết chương trình giúp người quản lí trả lời câu hỏi trên.

Input

Vào từ file BANDO.INP:

• Dòng 1: 2 số nguyên ~N~ và ~K~.

• Dòng 2: ~K~ số nguyên là các vị trí nếp gấp (~0 \le x_i < N + 1~ với ~i~ = ~1~, ~2~, ~3~, ... , ~K~).

Output

Ghi ra file BANDO.OUT:

• Dòng 1: Số lượng vị trí nếp gấp tiếp xúc với mặt bàn.

• Dòng 2: Số lượng nếp gấp tại vị trí đó theo thứ tự từ trái sang phải.

Scoring

Sample Input 1

7 2
3 2

Sample Output 1

4
2 3 2 1

Notes

Bạn Minh được cho trước một dãy số nguyên dương gồm ~N~ phần tử ~a_1, a_2, \ldots, a_N~. Bạn cần thực hiện ~Q~ truy vấn, trong đó mỗi truy vấn ứng với một đoạn con ~[L, R]~ của dãy trên với ~1 \leq L \leq R \leq N~ và cần tính tổng của tất cả các giá trị ~a_i \% a_j~ (~a_i~ chia lấy phần dư cho ~a_j~) với mọi cặp chỉ số ~(i, j)~ thỏa mãn ~L \leq i, j \leq R~.

Yêu cầu: Hãy viết chương trình giúp Minh trả lời các truy vấn đó.

Input

Dữ liệu vào từ file THAOTAC.INP:

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ cho biết số phần tử trong dãy và số lượng truy vấn.

• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~.

• Trong ~Q~ dòng tiếp theo, mỗi dòng là một cặp số nguyên ~L, R~ (~1 \leq L \leq R \leq N~).

Output

Ghi ra file THAOTAC.OUT gồm ~Q~ số trên các dòng khác nhau, mỗi dòng là câu trả lời các truy vấn đã cho theo thứ tự.

Scoring

Sample Input 1

3 2
1 2 4
1 3
2 2

Sample Output 1

4
0

Một công ty có ~N~ phòng, kết nối với nhau bằng ~N-1~ hành lang nội bộ có thể di chuyển theo hai chiều sao cho một hành lang nối trực tiếp hai phòng và giữa hai phòng bất kỳ luôn có đường đi đến nhau.

Công ty có ~M~ nhân viên, ban đầu mỗi nhân viên làm việc tại một phòng nhất định. Một phòng có thể có nhiều nhân viên. Phòng, hành lang và nhân viên đều được đánh chỉ số bằng các số nguyên liên tiếp nhau, bắt đầu từ ~1~.

Mỗi nhân viên có một chỉ số hiệu suất cá nhân, ban đầu bằng ~0~.

Khi phòng ~X~ được bổ sung tiện ích, hiệu suất của tất cả nhân viên hiện đang làm việc tại phòng ~X~ tăng thêm ~V~ đơn vị.

Khi một nhân viên bị điều chuyển từ phòng ~A~ qua phòng ~B~, hiệu suất của nhân viên đó giảm đi ~K~ đơn vị, với ~K~ là độ dài quãng đường ngắn nhất từ phòng ~A~ đến phòng ~B~ (tính bằng số hành lang).

Hãy cho biết hiệu suất làm việc của một nhân viên trong quá trình công ty thực hiện việc trang bị tiện ích cho các phòng và điều chuyển nhân viên giữa các phòng.

Input

Vào từ file văn bản HSNV.INP:

• Dòng đầu gồm ba số nguyên ~N~, ~M~, ~Q~ (~2 \le N \le 2 \cdot 10^5~, ~1 \le M, Q \le 2 \cdot 10^5~) lần lượt là số phòng, số nhân viên, số yêu cầu.
• Dòng thứ hai gồm ~M~ số nguyên ~a_1, a_2, \ldots, a_M~, trong đó ~a_i~ là phòng mà nhân viên ~i~ ban đầu làm việc (~1 \le a_i \le N~).
• ~N-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u, v~ (~1 \le u, v \le N~, ~u \ne v~), cho biết có một hành lang nối trực tiếp giữa phòng ~u~ và phòng ~v~.
• ~Q~ dòng tiếp theo mô tả các yêu cầu, thuộc một trong ba dạng sau:
  • e X V: phòng ~X~ được bổ sung tiện ích, tăng thêm ~V~ đơn vị hiệu suất cho tất cả nhân viên hiện đang làm việc tại phòng đó (~1 \le X \le N~, ~0 \le V \le 10^9~).
  • t L R Z: tất cả nhân viên có chỉ số từ ~L~ đến ~R~ đồng loạt được chuyển về phòng ~Z~ (~1 \le L \le R \le M~, ~1 \le Z \le N~).
  • q K: truy vấn hiệu suất hiện tại của nhân viên ~K~ (~1 \le K \le M~).

Đảm bảo có ít nhất một yêu cầu dạng q.

Output

Ghi ra file văn bản HSNV.OUT:

• Với mỗi yêu cầu dạng q K, in ra một số nguyên trên một dòng là hiệu suất hiện tại của nhân viên ~K~.

Scoring

Sample Input 1

3 2 5
1 2
1 2
2 3
q 1
e 2 5
q 2
t 1 1 3
q 1

Sample Output 1

0
5
-2

Với số nguyên dương ~K~ cho trước, số nguyên dương ~N~ được gọi là "số đẹp" nếu tổng các chữ số của ~N~ cũng như tổng chữ số của ~N~ ~+~ ~1~ khi viết trong hệ thập phân thì đều chia hết cho ~K~.

Yêu cầu: Cho ~Q~ câu hỏi, mỗi câu gồm một số nguyên dương ~K~. Viết chương trình tìm số đẹp nhỏ nhất ứng với mỗi số ~K~. Biết rằng giá trị số đẹp như thế có thể rất lớn và thậm chí không tồn tại.

Input

Vào từ file SODEP.INP:

• Dòng 1: gồm một số nguyên ~Q~ (~1 \le Q \le 10~) là số lượng số ~K~;

• Trong ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~K~ (~K \le 10^{12}~).

Output

Ghi ra file SODEP.OUT gồm ~Q~ dòng, mỗi dòng ứng với mỗi ~K~ trong dữ liệu vào. Nếu tìm được số đẹp thì in ra hai số nguyên: chữ số đầu tiên từ trái qua và tổng chữ số của nó; trong trường hợp không tồn tại số đẹp thì in ra ~-1~.

Scoring

Sample Input 1

3
2
2025
10

Sample Output 1

1 10
-1
1 90

Notes

• Với ~K = 2~, số ~N = 19~ là số đẹp nhỏ nhất vì khi đó ~N~ ~+~ ~1~ ~=~ ~20~ và ~N~, ~N~ ~+~ ~1~ có tổng chữ số lần lượt là ~10~, ~2~ đều chia hết cho ~2~.

• Với ~K = 2025~ không tồn tại số đẹp ~N~.

• Với ~K = 10~ thì ~N = 18999999999~ có tổng chữ số là ~90~ và ~N~ ~+~ ~1~ ~=~ ~19000000000~ có tổng chữ số là ~10~; các tổng này đều chia hết cho ~10~.

Một trung tâm nghệ thuật tổ chức một cuộc thi ảnh đẹp với ~N~ bức ảnh của các thí sinh đăng ký tham dự. Những bức ảnh đặc sắc sẽ được chọn trưng bày. Mỗi bức ảnh được đánh giá bởi hai tiêu chí: độ sắc nét và độ sáng tạo. Biết rằng bức ảnh thứ ~i~ có điểm sắc nét là ~S_i~ và điểm sáng tạo là ~T_i~ (~i = 1, 2, \dots, N~). Hội đồng đánh giá có ~Q~ cặp giám khảo là ~M_j~ và ~N_j~ (~j = 1, 2, \dots, Q~). Mỗi cặp giám khảo có những tiêu chí đánh giá khác nhau, trong đó:

• Giám khảo ~M_j~ đánh giá riêng lẻ từng tiêu chí. Một bức ảnh được giám khảo này chấp nhận nếu có điểm sắc nét ít nhất ~X_j~ điểm và điểm sáng tạo ít nhất ~Y_j~ điểm;

• Giám khảo ~N_j~ chỉ quan tâm đến tổng thể. Một bức ảnh được giám khảo này chấp nhận nếu tổng điểm sắc nét và sáng tạo ít nhất ~Z_j~ điểm.

Với mỗi cặp giám khảo, một bức ảnh sẽ được chọn trưng bày nếu cả hai người đều chấp nhận.

Cho trước điểm sắc nét, điểm sáng tạo của ~N~ bức ảnh và tiêu chí đánh giá của ~Q~ cặp giám khảo, hãy viết chương trình xác định có bao nhiêu bức ảnh sẽ được chọn trưng bày ứng với mỗi cặp giám khảo.

Input

Vào từ file ANHDEP.INP:

• Dòng đầu gồm hai số nguyên ~N, Q~ (~1 \le N, Q \le 10^5~);

• ~N~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~S_i, T_i~ là điểm sắc nét và điểm sáng tạo của bức ảnh ~i~ (~0 \le S_i, T_i \le 10^9~; ~i=1, 2, \dots, N~);

• ~Q~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~X_j, Y_j, Z_j~ (~0 \le X_j, Y_j \le 10^9~; ~0 \le Z_j \le 2 \times 10^9~; ~j=1, 2, \dots, Q~).

Output

Ghi ra file ANHDEP.OUT gồm ~Q~ dòng, dòng ~j~ chứa một số nguyên duy nhất là số lượng bức ảnh được chọn trưng bày ứng với cặp giám khảo thứ ~j~.

Scoring

Sample Input 1

4 3
30 50
60 20
40 70
20 90
20 20 60
50 10 100
10 80 110

Sample Output 1

4
0
1

Ở vương quốc nọ có rất nhiều phù thủy, họ sở hữu một số phép thuật trong số ~M~ loại phép thuật. Các loại phép thuật được đánh số từ ~1~ đến ~M~. Đức vua đã triệu tập ~N~ phù thủy. Các phù thủy xếp thành một hàng ngang, được đánh số từ ~1~ đến ~N~ từ trái sang phải. Phù thủy thứ ~i~ sở hữu ~k_i~ loại phép thuật đó là ~a_{i,1}, a_{i,2}, \dots, a_{i,k_i}~.

Đức vua cần chọn các nhóm phù thủy đi bảo vệ vương quốc. Một nguyên tắc ghép nhóm phù thủy là nếu có hai phù thủy sở hữu cùng một loại phép thuật thì khi sử dụng, chúng sẽ triệt tiêu lẫn nhau. Tuy nhiên nếu có phù thủy thứ ba cũng sở hữu loại phép thuật đó thì nó vẫn có thể sử dụng bình thường. Nói cách khác, để một loại phép thuật hoạt động ở một nhóm phù thủy, số phù thủy trong nhóm sở hữu nó phải là một số lẻ. Ví dụ, ba phù thủy có tập các loại phép thuật là ~\{1, 2, 5\}~, ~\{1, 3, 5\}~ và ~\{2, 4, 5\}~ thì khi ghép nhóm sẽ có tập các loại phép thuật có thể sử dụng là ~\{3, 4, 5\}~.

Do chưa biết phải chọn các phù thủy nào đi thực hiện nhiệm vụ nên đức vua muốn thực hiện ~Q~ yêu cầu thuộc một trong hai dạng:

1. Thay đổi phù thủy: Cho số nguyên ~i~ và mô tả của một phù thủy mới. Đức vua yêu cầu phù thủy mới này thế chỗ của phù thủy đang đứng ở vị trí ~i~;

2. Thử ghép nhóm: Cho hai số nguyên ~L, R~. Đức vua muốn thử chọn nhóm cho tất cả phù thủy có chỉ số trong đoạn ~[L; R]~ thực hiện nhiệm vụ. Sau đó, họ sẽ được tách ra thành các nhóm gồm các phù thủy có chỉ số liên tiếp sao cho tập các loại phép thuật tổng hợp của mọi nhóm chứa đủ ~M~ loại phép thuật.

Lưu ý: để tách một đoạn ~[L; R]~ thành ~v~ nhóm gồm các phần tử có chỉ số liên tiếp, ta chọn một dãy số nguyên ~\delta_1, \delta_2, \dots, \delta_v~ sao cho ~L \le \delta_1 < \delta_2 < \dots < \delta_v = R~ và ~v \ge 1~. Khi đó, ta tách đoạn ~[L; R]~ thành ~v~ nhóm gồm các đoạn ~[L; \delta_1], [\delta_1+1; \delta_2], [\delta_2+1; \delta_3], \dots, [\delta_{v-1} + 1; \delta_v]~.

Yêu cầu: Hãy viết chương trình cho biết với mỗi yêu cầu loại 2, có thể chia nhóm (tối thiểu 1 nhóm) các phù thủy được chọn theo ý đức vua hay không. Nếu có, tìm số nhóm tối đa có thể chia.

Input

Vào từ file PHUTHUY.INP:

• Dòng đầu tiên chứa ba số nguyên ~N, M, Q~ cho biết số phù thủy được triệu tập, số loại phép thuật ở vương quốc và số lượng yêu cầu cần xử lý;

• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ được bắt đầu bởi số nguyên ~k_i~ (~0 \le k_i \le M~) là số phép thuật mà phù thủy thứ ~i~ sở hữu. Sau đó là ~k_i~ số nguyên ~a_{i,1}, a_{i,2}, \dots, a_{i,k_i}~ (~1 \le a_{i,1} < a_{i,2} < \dots < a_{i,k_i} \le M~) mô tả các loại phép thuật đó;

• Trong ~Q~ dòng tiếp theo, dòng thứ ~j~ mô tả yêu cầu thứ ~j~, bắt đầu bằng một số ~t_j~ (với ~t_j \in \{1; 2\}~)

  • Nếu ~t_j = 1~, tiếp theo là hai số nguyên ~i_j, l_j~ (~0 \le l_j \le M~) cho biết vị trí cập nhật và số loại phép thuật của phù thủy mới. Sau đó là ~l_j~ số nguyên ~b_1, b_2, \dots, b_{l_j}~ (~1 \le b_1 < b_2 < \dots < b_{l_j} \le M~) mô tả các loại phép thuật đó.

  • Nếu ~t_j = 2~, tiếp theo là hai số nguyên ~L_j, R_j~ (~1 \le L_j \le R_j \le N~) mô tả một phép thử ghép nhóm trên các phù thủy có chỉ số ~L_j, L_j+1, \dots, R_j~.

Output

Ghi ra file PHUTHUY.INP:

• Với mỗi truy vấn loại 2, nếu không tồn tại cách chia nhóm thỏa mãn yêu cầu đề bài, in ra ~-1~. Ngược lại, in ra số nhóm tối đa có thể chia. Mỗi số nguyên được in trên một dòng riêng biệt.

Scoring

Sample Input 1

12 3 7
1 3
2 1 3
2 2 3
0
3 1 2 3
2 1 2
1 2
2 1 3
0
3 1 2 3
3 1 2 3
1 2
2 1 12
1 9 1 1
2 1 12
2 5 12
2 4 9
1 4 1 3
2 1 6

Sample Output 1

-1
3
2
-1
1

Notes

• Với yêu cầu đầu tiên (được hỏi trên cả ~N~ phù thủy), không thể chia nhóm thỏa mãn yêu cầu đề bài, do đó, in ra ~-1~.

• Với yêu cầu thứ ba (được hỏi trên cả ~N~ phù thủy), ta chia được tối đa ~3~ nhóm như sau:

  • Nhóm đầu tiên gồm các phù thủy từ vị trí ~1~ đến ~4~ có tập các loại phép thuật lần lượt là ~\{3\}, \{1,3\}, \{2,3\}, \emptyset~.

  • Nhóm thứ hai gồm đúng phù thủy thứ ~5~. Phù thủy này sở hữu cả ~3~ loại phép thuật.

  • Nhóm thứ ba gồm các phù thủy từ vị trí ~6~ đến ~12~ có tập các loại phép thuật lần lượt là ~\{1,2\}, \{2\}, \{1,3\}, \{1\}, \{1,2,3\}, \{1,2,3\}, \{2\}~.

• Với yêu cầu thứ tư (được hỏi trên đoạn ~[5; 12]~), ta chia được tối đa ~2~ nhóm. Nhóm đầu tiên gồm phù thủy thứ ~5~; nhóm còn lại gồm các phù thủy từ vị trí ~6~ đến ~12~.

• Với yêu cầu thứ năm: không thể chia nhóm thỏa mãn yêu cầu đề bài, do đó, in ra ~-1~.

• Với yêu cầu thứ bảy: chia được tối đa một nhóm gồm các phù thủy từ vị trí ~1~ đến ~6~.