Số nguyên dương ~N~ là chia hết cho ~9~ khi và chỉ khi tổng các chữ số của nó chia hết cho ~9~.

Yêu cầu: Cho số nguyên dương ~N~. Hãy đổi một chữ số trong ~𝑁~ sao cho số mới được tạo ra có giá trị nhỏ nhất và chia hết cho ~9~. Số mới được tạo ra có thể có chữ số ~0~ ở đầu tiên.

Dữ liệu nhập vào từ file văn bản CH9.INP:

• Dòng đầu tiên chứa ~T~ là số test dữ liệu của bài toán ~(T \le 15);~
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~N~.

Tổng số lượng chữ số ở mọi test không quá ~10^6~.

Kết quả ghi ra file văn bản CH9.OUT:

Gồm ~𝑇~ dòng, mỗi dòng chứa một số nguyên dương tương ứng là kết quả theo yêu cầu.

Ràng buộc:

• Có ~50\%~ số test tương ứng với ~50\%~ số điểm của bài thoả mãn: ~T=1;~
• ~50\%~ số test còn lại ứng với ~50\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3
34125
5441
22221

Output

34128
0441
22221

Trong một cơ quan, có ~𝑁~ yêu cầu sử dụng phòng họp trực tuyến. Cơ quan đã đăng kí với cấp trên đường truyền ưu tiên theo ~𝑀~ mốc thời gian được đánh số từ ~1~ đến ~M~. Mỗi yêu cầu đăng kí sử dụng phòng họp trong các mốc thời gian liên tiếp từ ~𝐿~ đến ~𝑅~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑀)~. Để tiện cho việc sắp xếp và phục vụ các phòng họp, cần biết mỗi yêu cầu xung đột với bao nhiêu yêu cầu khác (hai yêu cầu gọi là xung đột với nhau nếu có chung ít nhất một mốc thời gian).

Yêu cầu: Cho biết ~𝑁~ yêu cầu sử dụng phòng họp. Với mỗi yêu cầu, hãy tính số lượng yêu cầu xung đột với nó.

Dữ liệu nhập vào từ file văn bản XPH.INP:

• Dòng đầu chứa số hai nguyên ~𝑁,𝑀~ ~(1 ≤ 𝑁 ≤ 2 \times 10^5; \ 1 ≤ 𝑀 ≤ 10^9)~ là số lượng yêu cầu và số lượng mốc thời gian~;~
• ~N~ dòng tiếp theo, dòng thứ ~𝑖~ chứa hai số nguyên ~𝐿_i,𝑅_i \ (1 ≤ 𝐿_i ≤ 𝑅_i ≤ 𝑀; \ 1 ≤ 𝑖 ≤ 𝑁)~ là mốc thời gian bắt đầu và kết thúc của yêu cầu thứ ~𝑖~.

Kết quả ghi ra file văn bản XPH.OUT:

Gồm ~𝑁~ dòng, dòng thứ ~𝑖~ mô tả số lượng yêu cầu xung đột với yêu cầu thứ ~𝑖~ ~(1 ≤ 𝑖 ≤ 𝑁)~.

Ràng buộc

• Có ~25\%~ số test ứng với ~25\%~ số điểm của bài thoả mãn: ~𝑁, 𝑀 ≤ 400;~
• ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 2000;~
• ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thoả mãn: ~𝑀 ≤ 4 \times 10^5;~
• ~25\%~ số test còn lại ứng với ~25\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

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

Output

1
3
2
0
2

Lớp A1 tổ chức liên hoan cuối năm và đã đặt các món ăn cho từng học sinh trong lớp từ một nhà hàng. Cụ thể, lớp có ~𝑁~ học sinh, nhà hàng cung cấp ~𝑀~ món ăn khác nhau với giá tương ứng ~c_1, c_2, … , c_m~. Hiện tại, mỗi học sinh đã chọn xong cho mình một món ăn. Tuy nhiên, các bạn trong lớp nghĩ rằng có càng nhiều món ăn khác nhau trong buổi liên hoan thì cả lớp sẽ càng vui hơn.

Sau khi cân nhắc, các bạn muốn buổi liên hoan có ít nhất ~𝐾~ món ăn khác nhau. Nhà hàng cho phép học sinh đổi món ăn của họ bằng một món ăn khác đắt tiền hơn và phải trả thêm khoản chênh lệch chi phí giữa hai món ăn.

Yêu cầu: Hãy giúp lớp A1 tính toán tổng chi phí nhỏ nhất để có ít nhất ~K~ món ăn khác nhau trong buổi liên hoan, hoặc thông báo là không thể thực hiện được điều này.

Dữ liệu nhập vào từ file văn bản CMA.INP:

• Dòng đầu chứa ba số nguyên ~𝑁, 𝑀, 𝐾~ ~(1 ≤ 𝑁, 𝑀 ≤ 2 \times 10^5; \ 1 ≤ 𝐾 ≤ 𝑁);~
• Dòng thứ hai chứa ~𝑁~ số nguyên ~a_1, 𝑎_2, … , 𝑎_N~ là các món ăn mà các bạn trong lớp đã chọn ~(1 ≤ 𝑎_i ≤ 𝑀; \ 1 ≤ 𝑖 ≤ 𝑁);~
• Dòng thứ ba chứa ~𝑀~ số nguyên ~𝑐_1, 𝑐_2, … , 𝑐_M~ là giá của các món ăn ~(1 ≤ 𝑐_j ≤ 10^9; \ 1 ≤ 𝑗 ≤ 𝑀).~

Kết quả ghi ra file văn bản CMA.OUT:

Tổng chi phí nhỏ nhất cần để đổi các món ăn của các bạn trong lớp để thoả mãn yêu cầu, hoặc in ra ~-1~ nếu không có cách nào để có được ~𝐾~ món ăn khác nhau.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑎_1 = 𝑎_2 = ⋯ = 𝑎_N;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝐾 = 𝑁;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑀 ≤ 15;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑐_i = 𝑖;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3 4 3
1 1 2
1 2 3 4

Output

2

Trong một trò chơi, có một robot di chuyển trên một bản đồ dạng cây gồm ~𝑁~ ngọn núi và ~𝑁 − 1~ con đường nối các ngọn núi. Mỗi ngọn núi có ~𝐾~ kho báu và mỗi con đường nối hai ngọn núi đều có ~2~ kho báu. Quy tắc di chuyển của robot như sau:

• Robot chọn một ngọn núi để xuất phát~;~
• Tại mỗi lượt di chuyển qua một ngọn núi hoặc một con đường, robot khai thác để lấy một kho báu và di chuyển tiếp~;~
• Robot có thể di chuyển từ ngọn núi ~𝑢~ đến ~𝑣~ nếu thoả mãn cả hai điều kiện: con đường nối ngọn núi ~u~ đến ngọn núi ~𝑣~ còn lại ít nhất một kho báu và ngọn núi ~𝑣~ còn lại ít nhất một kho báu. Nếu không còn kho báu, ngọn núi và con đường sẽ bị phá huỷ, robot không thể di chuyển đến.

Yêu cầu: Em hãy tính xem robot có thể đi qua nhiều nhất bao nhiêu con đường.

Dữ liệu nhập vào từ file văn bản TKB.INP:

• Dòng đầu tiên chứa hai số nguyên dương ~𝑁, 𝐾~ ~(𝑁 ≤ 10^5; \ 𝐾 ≤ 10^9);~
• ~𝑁 − 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~𝑢, 𝑣~ ~(1 ≤ 𝑢, 𝑣 ≤ 𝑁)~ mô tả con đường nối hai ngọn núi.

Kết quả ghi ra file văn bản TKB.OUT:

In ra một số nguyên là số lượng con đường nhiều nhất mà robot đi qua.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thoả mãn: ~𝐾 = 1;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 20;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 300; \ 𝐾 = 2;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 1000;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

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

Output

4

Giải thích

Robot có thể di chuyển theo thứ tự các ngọn núi: ~3 − 2 − 1 − 6 − 7~. Robot đi qua 4 con đường.

Input

4 3
1 2
2 4
2 3

Output

6

Giải thích

Robot có thể di chuyển theo thứ tự các ngọn núi: ~1 − 2 − 4 − 2 − 3 − 2 − 1~. Robot đi qua ~6~ con đường.

Cho dãy số nguyên dương ~𝐴~ có ~𝑁~ phần tử ~𝑎_1, 𝑎_2, … , 𝑎_N~. Có ~𝑄~ truy vấn có dạng ~𝐿, 𝑅, 𝐾~ với ý nghĩa như sau:

• Xét dãy con ~𝐵~ là dãy con của ~𝐴~ gồm các phần tử liên tiếp từ vị trí ~𝐿~ đến vị trí ~𝑅~ : ~𝑎_L, 𝑎_{L+1}, … , a_R~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁)~, ta xây dựng dãy số ~𝐶~ bằng cách coi ~𝐶~ là tập hợp tất cả các dãy con liên tiếp của ~B~. Ví dụ: dãy ~𝐵 = \{1, 2, 1\}~ các dãy con của ~B~ là ~\{1\}, \{2\}, \{1\}, \{1,2\}, \{2,1\}, \{1,2,1\}~ ta sẽ có dãy ~𝐶 = \{1, 2, 1, 1, 2, 2,1, 1,~~ 2, 1\};~
• Sắp xếp dãy ~𝐶~ theo thứ tự không giảm và đưa ra phần tử thứ ~𝐾~. Ví dụ: với dãy ~𝐶~ trên ta sắp xếp thành ~\{1, 1, 1, 1, 1, 1, 2, 2, 2, 2\}~ và phần tử thứ ~8~ là ~2~.

Yêu cầu: Cho dãy số ~𝐴~ và ~𝑄~ truy vấn như trên, hãy đưa ra kết quả phần tử thứ ~𝐾~ của dãy số ~𝐶~ tương ứng trong mỗi truy vấn.

Dữ liệu nhập vào từ file văn bản DLT.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~𝑁~ và ~𝑄~ ~(1 ≤ 𝑁, 𝑄 ≤ 5 \times 10^5)~ là số phần tử của dãy số ~𝐴~ và số lượng truy vấn~;~
• Dòng thứ hai gồm ~𝑁~ số nguyên dương ~𝑎_1, 𝑎_2, … , 𝑎_N~ ~(1 ≤ 𝑎_i ≤ 5 \times 10^5; \ 1 ≤ 𝑖 ≤ 𝑁);~
• ~𝑄~ dòng sau, mỗi dòng chứa ba số ~𝐿, 𝑅, 𝐾~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁)~ mô tả truy vấn.

Dữ liệu đảm bảo đúng đắn, luôn có kết quả.

Kết quả ghi ra file văn bản DLT.OUT:

~𝑄~ dòng là kết quả tương ứng của mỗi truy vấn.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄 ≤ 100;~
• ~10\%~ số test khác ứng với ~10\%~ số điểm của bài thoả mãn: ~𝑁, 𝑎_i ≤ 100;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄, 𝑎_i ≤ 5000;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄 ≤ 10^5; 𝑎_i ≤ 100;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄, 𝑎_i ≤ 10^5;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5 2
1 2 1 3 2
1 3 8
1 4 18

Output

2
3