Trong một trò chơi tìm kho báu, bản đồ được mã hóa thành một bảng hình chữ nhật có \(M\) hàng và \(N\) cột. Các hàng được đánh số từ \(1\) đến \(M\), các cột được đánh số từ \(1\) đến \(N\), ô ở hàng \(i\), cột \(j\) trên bảng gọi là ô \((i,j)\) có giá trị là một trong bốn loại ký tự:

• 0: mô tả ô đất liền;
• 1: mô tả ô biển;
• @: mô tả ô vị trí xuất phát của nhân vật (luôn ở trên đất liền);
• #: mô tả ô chứa kho báu (luôn ở trên đất liền).

Nhân vật không biết bơi nên sẽ không thể đi vào ô biển và luôn luôn đứng ở ô đất liền. Nhân vật có thể di chuyển trên bản đồ theo các cách sau:

• Đi bộ tự do sang các ô đất liền chung cạnh;
• Nhảy qua biển theo một trong \(4\) hướng Đông, Tây, Nam, Bắc đến ô đất liền đầu tiên trên hướng nhảy đó.

Yêu cầu: Nhân vật xuất phát ở ô có ký tự @ và muốn di chuyển đến ô có ký tự # chứa kho báu. Vì mỗi lần nhảy qua biển tiêu hao nhiều năng lượng, hãy giúp nhân vật tìm số lần nhảy nhỏ nhất để có thể di chuyển đến ô có kho báu.

Input

• Dòng đầu tiên gồm hai số nguyên \(M\), \(N\) (\(1 \leq M, N \leq 10^3\));
• \(M\) dòng tiếp theo, mỗi dòng gồm \(N\) ký tự mô tả bản đồ.

Output

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

Scoring

• Subtask \(1\) (\(20\%\) số điểm): tối đa một cột chứa toàn ô số 1 và một hàng chứa toàn ô số 1;
• Subtask \(2\) (\(30\%\) số điểm): \(M \leq 2\);
• Subtask \(3\) (\(50\%\) số điểm): không có ràng buộc thêm.

Example

4 8
@0011011
11111011
1001101#
11111011

2

1 9
@1011101#

3

Hai số nguyên dương \(a, b\) được gọi là nguyên tố cùng nhau khi ước chung lớn nhất của chúng là \(1\).

Cho hai số nguyên dương \(N\) và \(Q\).

Yêu cầu: Thực hiện \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên \(L, R\). Hãy đếm số lượng số nguyên tố cùng nhau với \(N\) trong đoạn \([L, R]\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(Q\) \((1 \leq N \leq 10^{11}; 1 \leq Q \leq 3 \times 10^4)\);
• Q dòng tiếp theo, mỗi dòng gồm hai số nguyên \(L\) và \(R\) \((1 \leq L \leq R \leq 10^{15})\) mô tả truy vấn.

Output

• Gồm \(Q\) dòng, mỗi dòng in ra kết quả của truy vấn tương ứng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(R \times Q \leq 10^{6}\).
• Subtask \(2\) (\(20\%\) số điểm): \(R \leq 10^{6}\).
• Subtask \(3\) (\(20\%\) số điểm): \(N\) là lũy thừa của một số nguyên tố;
• Subtask \(4\) (\(20\%\) số điểm): \(N\) là tích của hai lũy thừa của một số nguyên tố;
• Subtask \(5\) (\(20\%\) số điểm): \(20\%\) số điểm không có ràng buộc thêm.

Example

10 2
1 5
5 10

2
2

Có \(N\) búp bê Matryoshka rỗng ruột được đánh số từ \(1\) đến \(N\). Búp bê thứ \(i\) \((1 \leq i \leq N)\) có đường kính \(D_{i}\), chiều cao \(H_{i}\) và nó có thể đặt vào bên trong búp bê khác nếu cả đường kính và chiều cao đều nhỏ hơn. Các búp bê đặt được vào bên trong nhau được gọi là một nhóm.

Có \(Q\) truy vấn, mỗi truy vấn cho hai số nguyên dương \(A\) và \(B\) với ý nghĩa như sau:

• Chỉ xét những búp bê có kích thước đường kính \(D\) và chiều cao \(H\) thỏa mãn: \(D \geq A\) và \(H \leq B\).
• Tìm cách đặt các búp bê vào bên trong nhau sao cho số nhóm búp bê tạo thành nhỏ nhất.

Yêu cầu: Với mỗi truy vấn, hãy tính số nhóm búp bê nhỏ nhất có thể.

Input

• Dòng đầu tiên gồm số nguyên \(N\) \((1 \leq N \leq 2 \times 10^{5})\) là số lượng búp bê.
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(D_i\) và \(H_{i}\) \((1 \leq i \leq N; 1 \leq D_i , H_{i} \leq 10^9)\) mô tả đường kính và chiều cao của búp bê thứ \(i\).
• Dòng tiếp theo gồm số nguyên \(Q\) \((1 \leq Q \leq 2 \times 10^{5})\) là số lượng truy vấn;
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(A\), \(B\) \((1 \leq A, B \leq 10^9)\) mô tả truy vấn.

Output

• Gồm \(Q\) dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \leq 10; Q = 1\);
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 2000; Q \leq 2000\);
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc thêm.

Example

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

2

An có \(N\) chiếc kẹo dự định chia cho \(M\) bạn được đánh số từ 1 đến \(M\). Bạn nào cũng sẽ nhận
được tối thiểu \(1\) chiếc kẹo. An biết rằng, bạn thứ \(i\) \((1 \leq i \leq M)\) có mức độ thích đồ ngọt là \(D_{i}\).

Gọi \(S_i\) là số lượng bạn nhận được nhiều kẹo hơn bạn thứ \(i\). Khi đó, độ vui vẻ của bạn thứ \(i\) sẽ bị giảm đi \(D_{i} \times S_{i}\).

Yêu cầu: Cho \(T\) truy vấn \(N_{1}, N_{2}, \ldots, N_{T}\) tương ứng với số kẹo mà An có. Với mỗi truy vấn, hãy giúp An tìm cách chia kẹo để tổng độ vui vẻ bị giảm đi của \(M\) bạn là nhỏ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên \(M\) và \(T\) \((1 \leq M \leq 100; 1 \leq T \leq 10^{5})\) là số lượng bạn của An và số truy vấn;
• Dòng thứ hai gồm \(M\) số nguyên \(D_{1}, D_{2}, \ldots, D_{M}\) \((0 \leq D_{i} \leq 10^{5}; 1 \leq i \leq M)\) là mức độ thích đồ ngọt của \(M\) bạn;
• Dòng thứ ba gồm \(T\) số nguyên mô tả các truy vấn tương ứng là số kẹo mà An có: \(N_{1}, N_{2}, \ldots, N_{T}\) \((1 \leq i \leq T; M \leq N_{i} \leq 10^9)\).

Output

• Gồm một dòng chứa \(T\) số, số thứ \(i\) (\(1 \leq i \leq T\)) là tổng độ vui vẻ bị giảm đi nhỏ nhất trong trường hợp An có \(N_{i}\) chiếc kẹo.

Scoring

• Subtask \(1\): (\(30\%\) số điểm): \(M \leq 3; N_{i} \leq 100; T \leq 3\);
• Subtask \(2\): (\(20\%\) số điểm): \(M \leq 5; N_{i} \leq 100; T \leq 3\);
• Subtask \(3\): (\(20\%\) số điểm): \(M \leq 10; N_{i} \leq 100\);
• Subtask \(4\): (\(20\%\) số điểm): \(N_{i} \leq 5000\);
• Subtask \(5\): (\(10\%\) số điểm): không có ràng buộc thêm.

Example

3 2
100 200 300
5 6

200 0