Cho hoán vị ~P~ = {~p_1~, ~p_2~,....~p_n~} của {1, 2,....,~n~}. Người ta muốn sắp xếp lại hoán vị này để thu được hoán vị {1, 2,....,~n~} bằng cách như sau: "Lần lượt xét các vị trí 1, 2,...,~n~. Với mỗi vị trí ~i~ liên tục đổi chỗ ~p_i~ cho số đằng trước nó chừng nào số này lớn hơn ~p_i~"

Ví dụ, với hoán vị {3,2,1,5,4} qui trình đổi chỗ thực hiện như sau:

• Với ~p_1~ = 3: (3,2,1,5,4) có 0 phép đổi chỗ
• Với ~p_2~ = 2 : (3,2,1,5,4) -> (2,3,4,5,4) có 1 phép đổi chỗ
• Với ~p_3~ = 1 : (2,3,1,5,4) -> (2,1,3,5,4) -> (1,2,3,5,4) có 2 phép đổi chỗ
• Với ~p_4~ = 5 : (1,2,3,5,4) có 0 phép đổi chỗ
• Với ~p_5~ = 4 : (1,2,3,5,4) -> (1,2,3,4,5) có 1 phép đổi chỗ

Cho biết số phép đổi chỗ của các vị trí 1, 2, ..., ~n~ . Hãy xác định hoán vị ban đầu

Dữ liệu vào: Dòng đầu tiên ghi số nguyên dương ~T~ <= 5 là số lượng tests. Tiếp theo là ~T~ nhóm dòng, mỗi nhóm mô tả một test có cấu trúc:

• Dòng 1: Ghi số nguyên dương ~n~ (1 <= ~n~ <= 200000)
• Dòng 2: Ghi các số nguyên ~w_1~, ~w_2~,...,~w_n~ với ~W_i~ là số lần đổi chỗ mà ~p_i~ thực hiện (~i~ =1,2,..., ~n~) .

Kết quả: In ra ~T~ dòng, dòng thứ ~i~ ghi ~n~ số nguyên mô tả hoán vị ~p_1~, ~p_2~,....~p_n~ ban đầu ứng với test thứ (~i~ =1,2,..., ~T~ . Thứ tự test là thứ tự xuất hiện trong input.

Ví dụ:

input:

2
3
0 1 0
5
0 1 2 0 1

output

2 1 3
3 2 1 5 4

• Có 30% số test có ~n~ <= 10 ứng với 30% số điểm;
• Có 10% số test có ~n~ <= 100 ứng với 10% số điểm;
• Có 10% số test có ~n~ <= 500 ứng với 10% số điểm;
• Có 20% số test có ~n~ <= 5000 ứng với 20% số điểm;
• Có 30% số test có ~n~ <= 2x~10^5~ ứng với 30% số điểm;

Cho hai số nguyên dương ~M~ và ~N~ (1 ≤ ~M~ ≤ ~N~ ≤ 60000) và số ~S~ được xác định bằng công thức sau: ~S~ = ~n~!/(~m~!(~n~−~m~)!)

Yêu cầu: Đếm số lượng ước nguyên tố của ~S~

Input: gồm một dòng ghi hai số ~N~ và ~M~ cách nhau một dấu cách.

Output: gồm một dòng ghi 1 số duy nhất là số lượng ước nguyên tố của ~S~.

Ví dụ:

Input

7 3

Output

2

Đạt có ~n~ quyển sách, quyển sách thứ ~i~ có chiều cao ~h_i~ và chiều rộng ~w_i~ . Đạt muốn xây dựng một số giá sách để chứa hết tất cả ~n~ quyển sách này.

Qua tìm hiểu, Đạt nhận được các thông tin sau: Nhà sản xuất nhận làm ~m~ loại giá sách, mỗi loại giá sách gồm các thông tin: ~H_i~, ~F_i~, ~C_i~ . Giá sách loại thứ ~i~ có thể chứa được các quyển sách có độ cao không vượt quá ~H_i~ và nếu muốn dựng giá sách có độ rộng là ~W~ thì giá tiền tương ứng là: ~F_i~ + ~W~ x ~C_i~ .

Yêu cầu: Cho thông tin về các quyển sách và các loại giá sách, hãy giúp Đạt tính chi phí ít nhất để dựng một số giá sách chứa tất cả các quyển sách. Input

• Dòng 1: gồm 2 số ~n~, ~m~
• Dòng 2 đến dòng ~n + 1~ , mỗi dòng chứa 2 số nguyên dương mô tả chiều chiều cao ~h_i~ và chiều rộng ~w_i~ của quyển sách
• Dòng thứ ~n + 2~ đến dòng ~n + m + 1~ , mỗi dòng chứa 3 số nguyên dương ~H_i~, ~F_i~, ~C_i~ mô tả các thông tin về các loại giá sách.

Output

• Gồm một dòng chứa một số là chi phí phí ít nhất để dựng một số giá sách chứa tất cả các quyển sách.

Ví dụ:

Input

3 3
20 5
21 10
22  5
20 100 1
21 150 2
25 1000 100

Output

1680

Ràng buộc:

• Có 25% số test ứng với: ~n~ <= 20; ~m~ <= 2;
• Có 25% số test ứng với : ~n~ <= 1000; ~m~ <= 10;
• Có 25% số test ứng với : ~n~ <= 100; ~m~ <= 100;
• Có 25% số tests ứng với : ~n~ <= 1000; ~m~ <= 1000;

Kaito là một tên trộm tài ba, chuyên trộm những món đồ quý giá. Tuy nhiên, hắn lại có sở thích kì dị là công khai món đồ mình chuẩn bị lấy trộm. Chính điều này đã đẩy Kaito vào thế tiến thoái lưỡng nan bởi chủ sở hữu món đồ Kaito chuẩn bị đánh cắp đã đầu tư vào căn nhà với công nghệ chống trộm tiên tiến.Với sự trợ giúp của trợ thủ, Kaito biết trước được một số thông tin sau : Ngôi nhà có thể được biểu diễn bởi một hình chữ nhật được chia làm ~M~ cột và ~N~ hàng. Các cột được đánh số từ 1 tới ~M~ theo chiều từ trái qua phải (chiều hướng Tây đến Đông). Các hàng được đánh số từ 1 tới ~N~ theo chiều từ dưới lên trên (chiều hướng Nam đến Bắc). Ngôi nhà có ~M\times N~ phòng, phòng nằm trên cột ~i~ hàng ~j~ được ký hiệu là (~i, j~).Hai phòng có chung cạnh sẽ có một cửa nối giữa chúng. Ngôi nhà chỉ có một lối vào duy nhất là cửa chính (ô ~(1,1)~). Dù được canh giữ sát sao nhưng nhờ tài hóa trang thiên bẩm Kaito có thể dễ dàng tiến vào ngôi nhà. Tuy nhiên Kaito không ngờ rằng lối vào lại được đặt thiết bị báo động khi có kẻ xâm nhập và cảnh sát đang truy lùng Kaito khắp mọi ngõ ngách trong căn nhà. Để tránh bị phát hiện, Kaito mất 1p để đi qua mỗi cánh cửa (khi mà thiết bị báo động ở cánh cửa đó đã tắt). Ở một số căn phòng đã được đặt công tắc kiểm soát trạng thái của các thiết bị báo động ở các cửa, Kaito có thể hack thiết bị đó và chỉ mất 1p, mọi thiết bị báo động đang bật thì tắt và ngược lại. Ban đầu, tất cả thiết bị ở cửa nối 2 phòng theo hướng Nam-Bắc được bật, và các thiết bị còn lại thì tắt.

Nhằm tránh bị bắt, Kaito phải đi đến phòng (~M,N~) nhanh nhất có thể để đánh tráo báu vật và chuẩn bị hóa trang thoát ra ngoài. Bạn hãy giúp Kaito xác định thời gian ngắn nhất đi từ phòng ~(1, 1)~ tới phòng (~M, N~). Nếu không thể đến được phòng (~M,N~) thì in ra ~-1~ để anh ấy hủy kế hoạch trộm cắp.

Yêu cầu: Xác định thời gian ngắn nhất đi từ phòng ~(1, 1)~ tới phòng (~M, N~).

Dữ liệu vào

• Dòng đầu tiên chứa 3 số nguyên ~M, N, K~ (~2 ≤ M, N ≤ 100000, 1 ≤ K ≤ 200000~).
• ~K~ dòng sau, mỗi dòng gồm 2 số nguyên ~x, y~ (~1 ≤ x ≤ M, 1 ≤ y ≤ N~) mô tả phòng (~x, y~) có đặt công tắc. ~K~ tọa độ phòng là phân biệt.

Kết quả

• In ra số phút ít nhất để đi từ phòng (1, 1) tới phòng (~M, N~). Nếu không đi được, in ra ~-1~.

Sample Input 1

3 2 1 
1 2

Sample Output 1

4

Sample Input 2

3 2 1 
2 1

Sample Output 2

-1

Ràng buộc:

• Subtask 1:​ ~M, N ≤ 1000~
• Subtask 2:​ ~K ≤ 2000~
• Subtask 3:​ Không có ràng buộc gì thêm.

Nguồn: 2019 CLC-LC

Cho ~2n~ số nguyên phân biệt ~a_1~,~a_2~,…,~a_{2n}~. Một cách xếp ~2n~ số thành ~n~ nhóm gọi là cách xếp GRN nếu chênh lệch giữa hai số trong cùng một nhóm bằng với chênh lệch giữa hai số trong cùng nhóm khác. Hai cách xếp GRN được gọi là khác nhau nếu tồn tại hai số trong cách xếp này thì cùng nhóm nhưng trong cách xếp kia thì khác nhóm.

Yêu cầu: Cho ~2n~ số nguyên phân biệt ~a_1~,~a_2~,…,~a_{2n}~, hãy đếm số cách xếp GRN.

Dữ liệu vao:

• Dòng đầu là số nguyên dương ~n~;
• Dòng thứ hai gồm ~2n~ số nguyên, các số đôi một khác nhau và có giá trị tuyệt đối không vượt quá ~10^9~.

Kết quả: Ghi ra một số là số cách xếp GRN.

Vi du:

Input

2
1 3 7 5

Output

2

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài có ~n~ = 2;
• Có 20% test khác ứng với 20% số điểm của bài có ~n~ ≤ 5;
• Có 20% test khác ứng với 20% số điểm của bài có ~n~ ≤ 100;
• Có 20% test khác ứng với 20% số điểm của bài có ~n~ ≤ 1000;
• Có 20% số test còn lại ứng với 20% số điểm của bài có ~n~ ≤ ~10^6~ và ~a_i~ = ~a_{i-1}~ + 1 (~1<i≤2n~)</li>