Cho một tờ giấy hình chữ nhật kích thước ~M (cm) \times N (cm)~ và một số tự nhiên ~K~.

Yêu cầu

Nếu cắt những hình vuông có kích thước ~K (cm) \times K (cm)~ từ tờ giấy này thì diện tích còn lại nhỏ nhất là bao nhiêu ~cm^2~?

Dữ liệu đầu vào

Gồm ba số tự nhiên ~M,\ N,\ K~ lần lượt mỗi số trên một dòng ~(1 \le M, N, K \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Ví dụ 1

INPUT

8
7
3

OUTPUT

20

Giải thích:

Cho mạch mã gốc DNA bốn loại nucleotide A, T, G, C. Để tiết kiệm bộ nhớ, mạch mã gốc đã được nén lại thành một chuỗi ~S~ gồm các cặp là số lần xuất hiện liên tiếp nucleotide và loại nucleotide tương ứng.

Ví dụ: Mạch mã gốc AAACAATGGGGA nén thành 3A1C2A1T4G1A.

Các nucleotide ở hai mạch của phân tử DNA liên kết với nhau theo nguyên tắc bổ sung, trong đó A liên kết với T, G liên kết với C. Do vậy, nếu biết trình tự nucleotide trên một mạch có thể suy ra trình tự của mạch còn lại.

Ví dụ: Một đoạn phân tử DNA ở sinh vật nhân thực có trình tự nucleotide trên mạch mã gốc là AAACAATGGGGA. Trình tự nucleotide trên mạch bổ sung của đoạn DNA này là: TTTGTTACCCCT.

Yêu cầu

Cho một chuỗi ký tự ~S~ mô tả mạch mã gốc DNA sau khi đã nên. Hãy lập trình xác định mạch bổ sung của mạch mã gốc sau khi giải nén.

Dữ liệu đầu vào

Một chuỗi ~S~ có độ dài không vượt quá ~1000~. Dữ liệu đảm bảo chuỗi sau khi giải nén có độ dài không vượt quá ~10^5~.

Dữ liệu đầu ra

Gồm chuỗi ký tự là mạch bổ sung của mạch mã gốc sau khi giải nén.

Ràng buộc dữ liệu

• Có 20% số test ứng với 20% số điểm của bài thỏa mãn: độ dài chuỗi ~S~ là ~2~, trong đó ký tự đầu tiên là chữ số, ký tự thứ hai là một trong ~4~ chữ cái A, T, G, C;
• Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn: có duy nhất một loại nucleotide;
• Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn: số lần xuất hiện liên tiếp nucleotide A, T, G, C nhỏ hơn ~10~;
• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5A2G1A11T1C

OUTPUT

TTTTTCCTAAAAAAAAAAAG

Giải thích: Mạch mã gốc sau khi giải nén là: AAAAAGGATTTTTTTTTTTC. Mạch bổ sung là: TTTTTCCTAAAAAAAAAAAG.

Để trang trí Tết, Nam treo một dây đèn gồm ~N~ bóng đèn, được đánh số từ ~1~ đến ~N~, từ trái sang phải. Mỗi bóng đèn khi bật sẽ có hai màu vàng hoặc đỏ. Dây đèn được nhúng một mã lệnh cho phép nhận một số tự nhiên ~X~. Khi đó, màu của bóng đèn thứ ~X~ và các bóng đèn cách bóng đèn thứ ~X~ không quá ~K~ bóng đèn sẽ đều đổi từ vàng thành đỏ hoặc ngược lại.

Ban đầu các bóng đèn đều có màu vàng. Để dây đèn trông đẹp mắt, Nam đã lập trình để điều khiển màu của các bóng đèn. Chương trình của Nam có ~M~ dòng lệnh, mỗi dòng lệnh tương ứng với một lần gọi mã lệnh của dây đèn. Vì số lượng bóng đèn quá lớn, sau khi lập trình xong, Nam muốn kiểm tra ngẫu nhiên màu một số bóng đèn xem có đúng như ý tưởng ban đầu không.

Yêu cầu

Cho các số tự nhiên ~X~ là tham số của ~M~ dòng lệnh trong chương trình của Nam. Hãy lập trình để trả lời ~Q~ câu hỏi tương ứng với các lần kiểm tra của Nam. Biết rằng mỗi câu hỏi chứa một số nguyên dương ~P~ để xác định xem bóng đèn thứ ~P~ trong dây đèn có màu vàng hay đỏ.

Dữ liệu đầu vào

• Dòng đầu tiên gồm bốn số nguyên dương lần lượt là ~N,\ M,\ Q,\ K~ ~(1 \le N \le 10^9;\ 1 \le M \le 10^5,\ 1 \le Q \le 10^5,\ 0 \le K \le N)~;
• Dòng thứ hai gồm ~M~ số nguyên dương ~X_i~ mô tả tham số của lệnh thứ ~i~ ~(1 \le X_{i} \le N)~;
• Dòng thứ ba gồm ~Q~ số nguyên dương ~P_i~ mô tả câu hỏi thứ ~i~ ~(1 \le P_{i} \le N)~.

Dữ liệu đầu ra

Gồm ~Q~ dòng, dòng thứ ~i~ là câu trả lời cho câu hỏi thứ ~i~. Nếu bóng đèn tại vị trí ~P_i~ đang có màu vàng thì ghi ra ký tự V, ngược lại ghi ra ký tự D.

Ràng buộc dữ liệu

• Có 60% số test ứng với 60% số điểm của bài thoả mãn: ~N, M, Q \le 10^3~;
• 20% số test khác ứng với 20% số điểm của bài thoả mãn: ~N, M \le 10^5~;
• 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ụ

Ví dụ 1

INPUT

7 2 4 1
3 5
2 7 4 5

OUTPUT

D
V
V
D

Giải thích:

• Sau lần gọi mã lệnh thứ nhất, các bóng trong dây đèn có màu là: V, D, D, D, V, V, V;
• Sau lần gọi mã lệnh thứ hai, các bóng trong dây đèn có màu là: V, D, D, V, D, D, V;

Cho một bảng vuông kích thước ~N \times N~, ~N~ là số lẻ. Các hàng của bảng được đánh số từ ~1~ tới ~N~, từ trên xuống dưới; các cột của bảng được đánh số từ ~1~ tới ~N~, từ trái sang phải. Ban đầu, các số từ ~1~ đến ~N^2~ được ghi vào bảng này lần lượt từ trái sang phải, từ trên xuống dưới. Khi ~N = 5~ thì bảng vuông sẽ có dạng như Hình 1.

Luật chơi: Có ~Q~ lượt chơi, mỗi lượt chơi quản trò sẽ cấp cho người chơi thông tin là ba số nguyên ~P,\ X,\ Y~ ~(1 \le P \le N^2;\ 1 \le X, Y \le N)~. Người chơi cần đưa số nguyên ~P~ đến vị trí hàng ~X~ cột ~Y~ với số lần dịch bảng nhỏ nhất bằng cách sau:

• Dịch các số trên hàng chứa số ~P~ sang phải hoặc sang trái một ô theo vòng tròn cho đến khi số ~P~ nằm trên cột ~Y~;
• Dịch các số trên cột ~Y~ lên trên hoặc xuống dưới một ô theo vòng tròn cho đến khi số ~P~ nằm trên hàng ~X~;
• Mỗi thao tác dịch hàng hoặc cột như trên được tính là một lần dịch bàng. Bảng đầu tiên của lượt chơi sau chính là bảng kết thúc của lượt chơi trước.

Ví dụ: Xét bàng vuông ~5 \times 5~ cần dịch số ~17~ trên bảng ban đầu đến vị trí hàng ~2~ cột ~5~. Để số lần dịch bảng nhỏ nhất thực hiện như Hình 2.

Yêu cầu

Cho thông tin của ~Q~ lượt chơi. Hãy lập trình đưa ra số lần dịch bảng nhỏ nhất tìm được tương ứng với mỗi lượt.

Dữ liệu đầu vào

Gồm ~Q + 1~ dòng:

• Dòng đầu tiên chứa hai số nguyên dương ~N,\ Q~ ~(1 \le N < 30000 ;\ 1 \le Q \le 2000)~;
• ~Q~ dòng sau, mỗi dòng chứa ba số nguyên dương ~P,\ X,\ Y~ ~(1 \le P \le N^2;\ 1 \le X, Y \le N)~ mô tả thông tin của một lượt chơi.

Dữ liệu đầu ra

Gồm ~Q~ dòng, dòng thứ ~i~ tương ứng là số lần dịch bảng nhỏ nhất tìm được trong lượt chơi thứ ~i~.

Ràng buộc dữ liệu

• Có 40% số test ứng với 40% số điểm của bài thoả mãn: ~N < 100;\ Q \le 100~;
• 40% số test khác ứng với 40% số điểm của bài thoả mãn: ~N < 1500;\ Q \le 1500~;
• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5 3
17 2 5
5 4 2
18 1 1

OUTPUT

4
2
4

Giải thích:

• Lượt chơi đầu tiên được mô tả bởi Hình 2;
• Lượt chơi thứ hai thực hiện ~2~ lần dịch bảng như sau:

• Lượt chơi thứ ba thực hiện ~2~ lần dịch hàng ~4~ sang trái và ~2~ lần dịch cột ~1~ xuống dưới.

An đi mua ~M~ sản phẩm khác nhau, các sản phẩm được đánh số từ ~1~ đến ~M~. Ở chợ có ~N~ quầy hàng xếp thành hàng ngang được đánh số từ ~1~ đến ~N~, từ trái sang phải. Quầy hàng thứ ~i~ chỉ bán một loại sản phẩm duy nhất là ~A_{i}~ ~(1 \le A_{i} \le M)~ và với mỗi sản phẩm trong ~M~ sản phẩm luôn tồn tại ít nhất một quầy hàng bán sản phẩm loại đó. Thời gian để An mua sản phẩm tại quầy hàng thứ ~i~ là ~T_i~ phút. Thời gian để di chuyển giữa hai quầy hàng liền kề là ~1~ phút.

Yêu cầu

Tìm cách mua hàng sao cho:

• Mua đủ ~M~ sản phẩm theo đúng thứ tự ~1, 2, 3, ..., M~. Có thể bắt đầu từ một quầy hàng bất kì bán sản phẩm ~1~;
• Thời gian tính từ lúc bắt đầu mua sản phẩm ~1~ đến khi mua xong sản phẩm ~M~ là nhỏ nhất;

Dữ liệu đầu vào

Gồm ~Q + 1~ dòng:

• 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 gồm ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(1 \le A_i \le M;\ 1 \le i \le N)~. Dữ liệu đảm bảo các số từ ~1~ đến ~M~ xuất hiện ít nhất một lần;
• Dòng thứ ba gồm ~N~ số nguyên dương ~T_1, T_2, ..., T_N~ ~(1 \le T_i \le 10^9;\ 1 \le i \le N)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số phút nhỏ nhất để An mua ~M~ sản phẩm theo yêu cầu đề bài.

Ràng buộc dữ liệu

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

Ví dụ

Ví dụ 1

INPUT

5 2
1 2 1 1 2
5 10 6 8 3

OUTPUT

11

Giải thích: Cách mua sao cho tổng số phút nhỏ nhất là:

• Mua sản phẩm ~1~ ở quầy hàng thứ ~3~ mất ~6~ phút;
• Di chuyển sang quầy hàng thứ ~5~ mất ~2~ phút;
• Mua sản phẩm ~2~ ở quầy hàng thứ ~5~ mất ~3~ phút;

Tổng số phút là: ~6 + 2 + 3 = 11~.