HSG THCS Hà Nội 2016

Cho ba số nguyên dương \(a, b, c\).

Yêu cầu: Tìm số dư của phép chia tích các số nguyên trong đoạn \([a \ldots b]\) cho số \(c\).

Input

• Gồm 1 dòng chứa ba số nguyên dương \(a, b, c\) \((1 \le a < b \le 10^4, 1 < c \le 10^9)\).

Output

• In ra 1 số nguyên duy nhất là số dư tìm được.

Example

5  10  11

5

Trong cuộc thi Tin học trẻ, mỗi thí sinh phải trả lời \(n\) câu hỏi. Để tăng tính hấp dẫn của cuộc thi, ban tổ chức quyết định đưa ra \(n\) số điểm thưởng \(a_1, a_2, \ldots, a_n\). Theo thể lệ của cuộc thi, thí sinh trả lời đúng \(k\) câu hỏi (\(1 \leq k \leq n\)) sẽ nhận được số điểm thưởng bằng số lớn nhất trong các số \(a_1, a_2, \ldots, a_k\).

Yêu cầu: Xác định số điểm thưởng của thí sinh tương ứng với mỗi giá trị \(k\) từ \(1\) đến \(n\).

Input

• Dòng đầu chứa số nguyên dương \(n\) không vượt quá \(30000\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\), mỗi số không vượt quá \(10^3\).

Output

• Ghi ra một dòng gồm \(n\) số là điểm thưởng cho thí sinh trả lời đúng lần lượt \(1, 2, \ldots, n\) câu hỏi.

Example

3
6 1 7

6 6 7

Cho trước xâu kí tự \(s\) độ dài \(n\) chỉ chứa các chữ cái tiếng Anh. Bắt đầu từ xâu \(s\), thực hiện phép hoán vị vòng quanh các kí tự sẽ nhận được một dãy gồm \(m\) xâu khác nhau (\(m \leq n\)). Sau khi sắp xếp \(m\) xâu trong dãy nhận được theo thứ tự từ điển, xâu kí tự \(s\) ban đầu có vị trí thứ \(k\).

Ví dụ: Với \(s =\) BCA khi hoán vị vòng quanh các kí tự nhận được 3 xâu khác nhau: BCA, CAB, ABC. Sắp xếp theo thứ tự từ điển có dãy các xâu lần lượt là: ABC, BCA, CAB; xâu \(s\) ban đầu đứng ở vị trí thứ \(k = 2\).

Yêu cầu: Cho biết xâu \(x\) là một trong \(m\) xâu nhận được từ \(s\) bằng cách hoán vị vòng quanh các kí tự và vị trí \(k\) của xâu \(s\). Xác định xâu \(s\).

Input

• Dòng đầu chứa số nguyên dương \(k\);
• Dòng thứ hai chứa xâu \(x\) có độ dài \(n\) (\(k \leq n \leq 100\)).

Output

• Ghi ra xâu \(s\) tìm được. Trong trường hợp không xác định được \(s\) thì ghi số \(-1\).

Example

2
ABC

BCA

Thành phố ZXY có một vườn bách thảo được mô tả dưới dạng bản đồ hình chữ nhật gồm \(m\) dòng và \(n\) cột. Trong vườn có \(k\) loại cây khác nhau, đánh số từ \(1\) đến \(k\) (\(k \leq 100\)). Mỗi ô của bản đồ chứa duy nhất số nguyên dương \(i\) (\(i \leq k\)) nếu tại ô này có trồng một cây loại \(i\), hoặc số \(0\) nếu ô này không có cây. Chính quyền thành phố muốn chỉnh trang khu vườn cho đẹp hơn bằng cách giữ lại những hàng cây có ít nhất \(t\) cây liền nhau, thuộc cùng một loại cây, nằm trên cùng một dòng hoặc cùng một cột. Những cây không thuộc hàng cây nào đó sẽ được di chuyển đến vị trí khác phù hợp hơn.

Yêu cầu: Cho trước bản đồ vườn cây như trên, hãy đếm số lượng cây cần phải di chuyển.

Input

• Dòng đầu chứa ba số nguyên dương \(m\), \(n\) và \(t\) (\(1 < m, n, t \leq 100\));
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số tự nhiên mô tả bản đồ vườn bách thảo.

Output

• Ghi ra số lượng cây cần phải di chuyển.

Example

5 6 3
1 3 3 3 3 4
1 2 3 2 0 4
3 2 2 2 4 4
1 0 0 2 4 0
1 2 3 0 4 4

10