Độ khó: Khó (4/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Ở 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}, \ldots, 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, \ldots, \delta_v~ sao cho ~L \le \delta_1 < \delta_2 < \cdots < \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], \ldots, [\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}, \ldots, a_{i,k_i}~ (~1 \le a_{i,1} < a_{i,2} < \cdots < 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, \ldots, b_{l_j}~ (~1 \le b_1 < b_2 < \cdots < 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, \ldots, R_j~.

Output

Ghi ra file PHUTHUY.OUT:

• 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~.

Độ khó: Khá (3/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

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, \ldots, N~). Hội đồng đánh giá có ~Q~ cặp giám khảo là ~M_j~ và ~N_j~ (~j = 1, 2, \ldots, 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, \ldots, 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, \ldots, 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

Độ khó: Khá (3/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

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~.