Bài tập

Số \(fib(n)\) với \(n \geq 0\) được tính theo công thức sau:

• \(fib(n) = n\) nếu \(n \leq 1\).
• \(fib(n) = fib(n - 1) + fib(n - 2)\) với \(n > 1\).

Yêu cầu: Cho ba số nguyên \(a, b, M\), gọi \(u\) là ước số chung lớn nhất của \(fib(a)\) và \(fib(b)\), hãy tính phần dư của phép chia \(u\) cho \(M\).

Input

Vào từ thiết bị vào chuẩn gồm ba số nguyên dương \(a, b, M\) \((a, b, M \leq 10^{12})\)

Output

Ghi ra thiết bị ra chuẩn một số là phần dư của phép chia \(u\) cho \(M\).

Example

6 9 10

2

Scoring

Subtask \(1\) với \(70\%\) số điểm : \(a, b, M \leq 50\).

Subtask \(2\) với \(20\%\) số điểm : \(a, b, M \leq 10^9\)

Subtask \(3\) với \(10\%\) số điểm : \(a, b, M \leq 10^{12}\)

Những ngọn nến lung linh huyền ảo khiến biết bao người đam mê, trong số đó có Nhan_Tai. Một hôm, Tai_Nhan đưa cho anh \(n\) cây nến với độ cao đôi một khác nhau. Theo đó, Nhan_Tai sẽ phải xếp \(n\) cây nến này theo một đường thẳng sao cho các cây nến ở vị trí chẵn thì cao hơn hai cây nến hai bên (nếu có), và dĩ nhiên, các cây nến ở vị trí lẻ thì thấp hơp hai cây nến hai bên (nếu có). Cụ thể, cách xếp phải thỏa mãn với mọi \(1 ≤ i ≤ n\):

• Nếu \(i\) chẵn: \(i > 1\) ⇒ \(h_{i−1} < h_{i}\); \(i < n\) ⇒ \(h_{i+1} < h_{i}\)

• Nếu \(i\) lẻ: \(i > 1\) ⇒ \(h_{i−1} > h_{i}\) ; \(i < n\) ⇒ \(h_{i+1} > h_{i}\)

Ở đây \(h_{i}\) được hiểu như là độ cao của cây nến xếp ở vị trí thứ \(i\) trên đường thẳng. Anh ta muốn biết mình có bao nhiêu cách khác nhau để xếp các cây nến. Vốn nhìn xa trông rộng, Nhan_Tai biết sẽ có thể có rất nhiều cách xếp, anh ta chỉ yêu cầu in ra \(9\) chữ số tận cùng của số cách xếp

Input

• Dòng đầu chứa \(2\) số nguyên \(Q\) là số lượng testcase

• Mỗi testcase nằm trên một dòng chứa đúng một số nguyên dương: \(n\)

Output

Gồm \(Q\) dòng trả lời cho \(Q\) testcase

Example

5
6
7
8
9
10

000000061
000000272
000001385
000007936
000050521

Scoring

• \(N, Q ≤ 5000\)

• Có \(50\%\) số test với \(n ≤ 100\)

Xét dãy vô hạn các số tự nhiên liên tiếp bắt đầu từ \(1\): \(1, 2, 3,...\) và \(n\) số nguyên dương \(a_{1}, a_{2}, ..., a_{n}\). Trên dãy vô hạn các số tự nhiên này, tiến hành xóa hết các số chia hết cho \(a_{1}\), sau đó xóa hết các số chia hết cho \(a_{2}\) mà chưa được xóa,..., cuối cùng xóa hết các số chia hết cho \(a_{n}\) mà chưa được xóa. Đánh số các số chưa được xóa bắt đầu từ \(1\), người ta muốn biết số được đánh số thứ \(k\) là số nào?

Yêu cầu: Cho dãy số \(a_{1}, a_{2}, ..., a_{n}\) và \(k\), hãy tìm số tự nhiên được đánh số thứ \(k\) trên dãy sau khi xóa.

Input

--- Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu;

--- \(T\) nhóm dòng sau, mỗi nhóm có dạng:

o Dòng đầu của nhóm chứa hai số nguyên dương \(n\) và \(k\) \((1 ≤ k ≤ 10^{15})\);

o Dòng thứ hai của nhóm chứa \(n\) số nguyên dương \(a_{1}, a_{2}, ..., a_{n}\) \((1 < a_{i} ≤ 10^{15})\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số tự nhiên là kết quả tương ứng của bộ test trong dữ liệu vào.

Example

1
2 5
3 4

10

Scoring

\(30\%\) số test có \(n = 1\)

\(30\%\) số test có \(n = 2\)

\(40\%\) số test có \(n \leq 10\)

Cho bảng chữ kích thước \(m \cdot n\), mỗi ô chứa một kí tự \(A\) hoặc \(B\). Một hình chữ nhật con của bảng được gọi là bảng đẹp bậc \(k\) nếu số lượng kí tự \(A\) và số lượng kí tự \(B\) trong bảng con chênh lệch không quá \(k\).

Yêu cầu:
Cho bảng chữ kích thước \(m \cdot n\) và số nguyên \(k\), hãy tìm bảng con là bảng đẹp lớn nhất.

Input

• Dòng đầu chứa số nguyên \(T(T \leq 5)\) là số bộ dữ liệu.

• \(T\) nhóm dòng sau, mỗi dòng mô tả một bộ dữ liệu có dạng:

• Dòng đầu chứa ba số nguyên \(m, n, k\).

• \(m\) dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài \(n\) chỉ gồm kí tự \(A\) hoặc \(B\).

Output

• Ghi ra thiết bị ra chuẩn \(T\) dòng, mỗi dòng chứa một số là số lượng ô trong bảng tìm được
  tương ứng với dữ liệu vào.

Example

2
3 4 0
AAAA
BBBB
BAAA
3 4 1
AAAA
BBBB
BAAA

8
9

Scoring

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 100\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 2000\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 40000, k = 0\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 60000\).