Bài tập

Cho bảng số nguyên \(a\) gồm \(m\) hàng và \(n\) cột. Các hàng được đánh chỉ số từ \(0\) đến \(m-1\), các cột từ \(0\) đến \(n-1\). Hãy liệt kê chỉ số \((i, j)\) của mọi ô có giá trị bằng \(25\), theo thứ tự tăng dần của \(i\), với cùng \(i\) thì tăng dần theo \(j\).

Đề bài đảm bảo trong bảng có ít nhất một ô mang giá trị \(25\).

Input

• Dòng đầu: hai số nguyên \(m, n\).
• \(m\) dòng tiếp theo, mỗi dòng gồm \(n\) số nguyên.

Output

• Mỗi ô tìm được in trên một dòng gồm hai số \(i\) và \(j\) cách nhau một dấu cách.

Constraints

• \(1 \le m, n \le 500\)
• \(|a_{ij}| \le 1000\)
• Có ít nhất một ô bằng \(25\).

Sample Input

3 3
25 1 2
3 25 25
7 8 9

Sample Output

0 0
1 1
1 2

Cho dãy \(A\) gồm \(N\) số nguyên dương. Gọi \(M\) là giá trị lớn nhất trong dãy. Hãy tìm số nguyên tố nhỏ nhất \(U\) thoả mãn cả hai điều kiện:

• \(U\) không có mặt trong dãy \(A\);
• \(U \le M\).

Nếu không tồn tại \(U\) như vậy (mọi số nguyên tố không vượt quá \(M\) đều đã xuất hiện trong \(A\), hoặc \(M\) nhỏ hơn \(2\)) thì in ra dòng No prime number missing!.

Ví dụ: với \(A = [2, 3, 6, 9, 11]\) thì \(M = 11\), các số nguyên tố \(\le 11\) là \(2, 3, 5, 7, 11\); số nhỏ nhất vắng mặt là \(5\).

Input

• Dòng 1: số nguyên dương \(N\).
• Dòng 2: \(N\) số nguyên dương \(A_1, \dots, A_N\).

Output

• Một số nguyên là số nguyên tố nhỏ nhất bị thiếu, hoặc dòng No prime number missing! nếu không có.

Constraints

• \(1 \le N \le 10^5\)
• \(1 \le A_i \le 10^6\)

Sample Input

7
2 3 5 8 9 13 7

Sample Output

11

Explanation

Giá trị lớn nhất là \(13\); các số nguyên tố \(\le 13\) gồm \(2, 3, 5, 7, 11, 13\), trong đó chỉ có \(11\) chưa xuất hiện.

Trên một trục số có hai chú mèo A, B và một chú chuột C. Chuột đứng yên gặm mồi, còn hai chú mèo cùng chạy thẳng về phía chuột với vận tốc bằng nhau. Chú nào đến chỗ chuột trước thì chộp được chuột.

Toạ độ của mèo A, mèo B và chuột C lần lượt là \(a\), \(b\), \(c\). Hãy cho biết kết cục:

• Mèo A chộp được chuột: in ra Cat_A.
• Mèo B chộp được chuột: in ra Cat_B.
• Hai mèo đến cùng lúc thì chúng giành nhau và chuột chạy thoát: in ra Mouse_C.

Input

• Một dòng gồm ba số nguyên \(a, b, c\).

Output

• Một dòng duy nhất là Cat_A, Cat_B hoặc Mouse_C theo yêu cầu trên.

Constraints

• \(-10^9 \le a, b, c \le 10^9\)

Sample Input 1

3 9 5

Sample Output 1

Cat_A

Sample Input 2

2 8 5

Sample Output 2

Mouse_C

Explanation

Ở ví dụ 1, khoảng cách của mèo A tới chuột là \(2\), của mèo B là \(4\) nên mèo A đến trước. Ở ví dụ 2, cả hai mèo cùng cách chuột \(3\) đơn vị.

Cho hai số nguyên dương \(x\) và \(n\). Hãy tính \(x^n\) theo modulo \(10^9 + 7\), bằng một hàm đệ quy chia đôi số mũ (mỗi lần gọi đệ quy chỉ cần \(O(\log n)\) tầng): \(x^n = (x^{n/2})^2\) khi \(n\) chẵn và \(x^n = x \cdot (x^{\lfloor n/2 \rfloor})^2\) khi \(n\) lẻ.

Input

Một dòng gồm hai số nguyên dương \(x\) và \(n\).

Output

In ra một số nguyên: phần dư của \(x^n\) khi chia cho \(10^9+7\).

Constraints

• \(1 \le x, n \le 10^9\)

Sample Input 1

5 7

Sample Output 1

78125

Sample Input 2

2 30

Sample Output 2

73741817

Explanation

\(5^7 = 78125\). Còn \(2^{30} = 1073741824\), chia \(10^9+7\) dư \(73741817\).