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

Cho một cây gồm \(N\) đỉnh và \(N − 1\) cạnh có trọng số. Các cạnh được đánh số từ 1 đến \(N − 1\),
cạnh thứ \(i\) nối cặp đỉnh \((u, v)\) có trọng số \(c\).

Chi phí đường đi giữa hai đỉnh \((u, v)\) là tổng trọng số các cạnh trên đường đi từ \(u\) đến \(v\) \((u \neq v)\).

Nếu không tồn tại đường đi từ \(u\) đến \(v\) thì chi phí đường đi giữa cặp đỉnh \((u, v)\) là \(0\).
Một cách xóa cạnh được mô tả như sau:

• Chọn hai số nguyên dương \(L\), \(R\) thoả mãn \(1 \leq L \leq R \leq N − 1\);
• Xóa tất cả các cạnh được đánh số từ \(L\) đến \(R\);

Cho trước một số nguyên dương \(K\). Một cách xóa cạnh được gọi là “đẹp” nếu mọi chi phí đường đi giữa cặp đỉnh bất kỳ không vượt quá \(K\). Hai cách xóa cạnh được coi là khác nhau khi có một cạnh trong cách xóa này không có trong cách xóa kia.
Yêu cầu: Đếm số lượng cách xóa cạnh được gọi là “đẹp”.
Dữ liệu vào từ tệp văn bản XC.INP:

• Dòng đầu tiên gồm hai số nguyên \(N\) và \(K\) \((1 \leq N \leq 10^5; 1 \leq K \leq 10^9)\);
• \(N − 1\) dòng sau, mỗi dòng gồm ba số nguyên \(u, v\) và \(c\) \((1 \leq u, v \leq N; 1 \leq c \leq 10^6)\) mô tả cạnh nối đỉnh \(u\) và đỉnh \(v\), có trọng số là \(c\).

Output

• Một số nguyên duy nhất là số lượng cách xóa cạnh được gọi là “đẹp”.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 100\);
• Subtask \(3\) (\(20\%\) số điểm): \(N \leq 2500\);
• Subtask \(4\) (\(20\%\) số điểm): cây là một đường thẳng;
• Subtask \(5\) (\(10\%\) số điểm): không có ràng buộc thêm.

Example

6 12
1 2 3
1 4 5
2 3 6
2 5 4
3 6 9

9