Cho ~2~ số nguyên dương ~a~ và ~b~, hãy in ra ~a \mod b~, hay ~a \% b~.

Input

• Gồm một dòng chứa hai số nguyên dương ~a,b~.

Output

• In ra ~a \% b~.

Điều kiện

• ~1 \le a \le 10^{10^5}~.
• ~1 \le b \le 10^9~.

Subtask

• ~50\%~ số điểm: ~a \le 10^9~.
• ~50\%~ số điểm: Không ràng buộc gì thêm.

Ví dụ

Input 1:

4 3

Output 1:

1

Input 2:

16 2

Output 2:

0

Cho hai số nguyên dương ~a~ và ~b~. Tính tổng tất cả các số nguyên dương ~x~ thỏa mãn:

• ~x~ là ước của a
• ~3x~ là ước của b

Input

• Gồm ~2~ số nguyên dương ~a~ và ~b~ ~(1 \le a,b \le 10^{12})~.

Output

• In ra tổng tất cả các số nguyên dương ~x~ thỏa mãn điều kiện trên. Dữ liệu đảm bảo kết quả không quá ~10^{18}~. Nếu không có giá trị ~x~ thỏa mãn thì kết quả được xem là ~0~.

Subtask

• Có ~80\%~ số test ứng với ~0 < a,b \le 10^6~.
• Có ~20\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

4 18

Sample Output 1

3

Sample Input 2

1 2

Sample Output 2

0

Trang trại gà của nhà Bé Dino có ~n~ con gà siêu trứng đánh số từ ~1~ đến ~n~. Con gà ~i~ ~(1 \le i \le n)~ đẻ quả trứng đầu tiên ở giây ~p_i~, sau đó cứ ~t_i~ giây tiếp theo sẽ đẻ thêm một quả trứng. Yêu cầu: Bạn hãy viết chương trình tính thời gian nhỏ nhất (tính bằng giây) để Bé Bo thu được ít nhất ~x~ quả trứng.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~n,x~;
• ~n~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le n)~ chứa hai số nguyên dương ~p_i,t_i~ ~(1 \le p_i,t_i \le 500)~.

Output

• Một số nguyên duy nhất là thời gian nhỏ nhất để Bé Bo thu được ít nhất ~x~ quả trứng.

Subtask

• ~20\%~ số test tương ứng với ~20\%~ số điểm có ~n=1,x \le 10^{15}~;
• ~45\%~ số test tương ứng với ~45\%~ số điểm có ~n \le 20, x \le 1000~;
• ~35\%~ số test tương ứng với ~35\%~ số điểm có ~n \le 20,x \le 10^{15}~.

Sample Input 1

2 3
10 30
5 25

Sample Output 1

30

Sample Input 2

2 3
10 5
5 10

Sample Output 2

15

Bạn được nhận ~k \le 7~ chữ số ngẫu nhiên.

Yêu cầu: Dùng các chữ số bạn nhận được, hãy đếm xem có thể tạo ra được bao nhiêu số nguyên tố khác nhau.

Input

• Dòng đầu tiên là số ~T \le 10~ - số lượng test.
• ~T~ dòng tiếp theo, mỗi dòng gồm ~k~ chữ số tương ứng với một yêu cầu.

Output

• ~T~ dòng là kết quả của các test tương ứng theo thứ tự.

Sample Input 1

2
17
9999999

Sample Output 1

3
0

Giải thích

• Với ~2~ chữ số ~1,7~, tạo ra được 3 số nguyên tố là ~7, 17, 71~.
• Với ~7~ chữ số ~9~, không tạo ra được số nguyên tố nào.

Tewi đã ốm liệt giường nên Yagokoro Eirin phải chữa bệnh cho cô. Đoạn ADN của Tewi có độ dài ~n~ gồm cách kí tự ~a, b, c~ (vì sao thì chưa rõ). Eirin có thể sửa đổi một vị trí bất kì trên ADN với chi phí là 1.

Cô đang nghi ngờ ~q~ đoạn con ~[l_i, r_i]~ có thể là nguyên nhân gây bệnh. Với mỗi đoạn ADN con này, Eirin muốn sửa lại đoạn này sao cho không tồn tại đoạn con nào có độ dài lớn hơn 1 là xâu đối xứng. Ví dụ ~aab~ là không thỏa mãn vì có ~aa~ là xâu đối xứng. Hãy giúp cô tính trước chi phí để chữa bệnh nhé!

Input:

• Dòng đầu tiên gồm 2 số ~n, q~.
• Dòng tiếp theo là một xâu gồm ~n~ kí tự chỉ gồm ~a, b, c~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số ~l_i, r_i~.

Output:

• ~q~ dòng là chi phí chữa bệnh.

Sample Test

Input:

5 4
baacb
1 3
1 5
4 5
2 3

Output:

1
2
0
1

Giới hạn:

• Trong mọi test ~n, q \le 10^5~
• 10% số điểm: ~n, q \le 5~.
• 30% số điểm: ~n, q \le 2000~.
• 30% số điểm: ADN chỉ gồm 2 kí tự ~a, b~.
• 30% số điểm: Không có giới hạn gì thêm.

Trò chơi Bắc Nam không phải là trò chơi của miền Bắc và miền Nam mà là trò chơi giữa hai bạn Bắc và Nam. Hai bạn Bắc và Nam quen nhau trong một cuộc thi lập trình danh giá. Hai bạn đều được giải cao. Điều thú vị là Bắc quê ở miền Nam còn Nam quê ở miền Bắc. Trong buổi lễ trao phần thưởng, Ban tổ chức cuộc thi có tổ chức một trò chơi trí tuệ dành cho những bạn đạt giải. Mỗi lượt chơi gồm ~2~ bạn chơi. Bắc và Nam cùng chơi một lượt. Nội dung trò chơi được phát biểu:

Cho một vòng tròn được chia thành ~n~ vạch cách đều (~n~ là một số chẵn). Các vạch được đánh chỉ số từ ~1~ đến ~n~ theo chiều kim đồng hồ. Tại vạch ~i~ có ghi một số nguyên dương ~a_i (1 \le a_i \le n)~. Dãy gồm ~n~ số ~a_1,a_2,…,a_n~ tạo thành một hoán vị của ~n~ số nguyên ~1,2,3,…,n~. Hai bạn Bắc và Nam đều phải lập trình điều khiển robot di chuyển quanh vòng tròn để xóa số.

Robot của Bắc xuất phát từ vạch ~1~, di chuyển theo chiều kim đồng hồ. Khi robot đến vạch nào thì có thể xóa số ở vạch đó, tuy nhiên các số mà robot của bạn Bắc cần xóa lần lượt là ~1,3,5,...,n – 1~. Tức là số ~1~ sẽ được xóa đầu tiên, rồi đến số ~3,...,~ số ~n – 1~ sẽ được xóa cuối cùng. Khi xóa xong, robot sẽ di chuyển đến vạch ~1~ và dừng lại. Robot của Bắc chỉ được xóa các số lẻ.

Robot của Nam cũng xuất phát từ vạch ~1~, di chuyển theo chiều kim đồng hồ. Khi robot đến vạch nào thì có thể xóa số ở vạch đó, tuy nhiên các số mà robot của bạn Nam cần xóa lần lượt là ~2,4,6,...,n~. Tức là số ~2~ sẽ được xóa đầu tiên, rồi đến số ~4,...,~ số ~n~ sẽ được xóa cuối cùng. Khi xóa xong, robot sẽ di chuyển đến vạch ~1~ và dừng lại. Robot của Nam chỉ được xóa các số chẵn.

Bạn Bắc và Nam cần đưa ra số vòng mà robot của mình cần di chuyển quanh vòng tròn để xóa hết tất cả các số cần xóa. Bạn nào đưa ra kết quả đúng và nhanh sẽ được điểm cao và được nhận được nhiều phần quà có giá trị của Ban tổ chức.

Input

• Dòng ~1~ ghi số nguyên dương chẵn ~n~ ~(2 ≤n≤200000)~.
• Dòng ~2~ ghi ~n~ số nguyên dương ~a_1,a_2,…,a_n~ là một hoán vị của ~n~ số ~1,2,3,…,n~. Các số được ghi cách nhau bởi dấu cách.

Output

• Dòng ~1~ ghi số vòng mà robot của bạn Bắc cần di chuyển quanh vòng tròn để lần lượt xóa hết tất cả các số ~1,3,5,...,n – 1~.
• Dòng ~2~ ghi số vòng mà robot của bạn Nam cần di chuyển quanh vòng tròn để lần lượt xóa hết tất cả các số ~2,4,6,...,n~.

Subtask

• Có ~25\%~ số test ứng với ~n = 8~.
• Có ~25\%~ số test ứng với ~n \le 1000~.
• ~50~ số test còn lại không giới hạn gì thêm.

  Sample Input 1

8
1 7 3 2 4 6 5 8

Sample Output 1

2
1

Explanation 1

• Robot của Bắc:
  • Vòng ~1~: Xóa các số: ~1, 3, 5~.
  • Vòng ~2~: Xóa số ~7~.
• Robot của Nam:
  • Vòng ~1~: Xóa các số: ~2, 4, 6, 8~.

Kaguya đang bị Mokou đuổi đánh trên một đồ thị gồm ~n~ đỉnh và ~m~ cạnh. Kaguya hiện đang ở đỉnh ~a~ và Mokou thì ở đỉnh ~b~. Cả hai đều cần 1 đơn vị thời gian để di chuyển từ đỉnh này sang đỉnh khác.

Có bao nhiêu đỉnh mà nếu bạn đứng ở đó sẽ cứu được Kaguya?

Input

• Dòng đầu tiên gồm 2 số nguyên ~n, m~.
• Dòng thứ hai gồm 2 số nguyên ~a, b~.
• ~n~ dòng tiếp theo, mỗi dùng gồm 2 số nguyên ~u, v~, thể hiện có cạnh nối ~u~ và ~v~.

Output

• In ra số lượng đỉnh bạn có thể đứng để cứu Kaguya.

Điều kiện

• ~1 \le n, m \le 10^5~.
• ~1 \le u, v, a, b \le n~.

Ví dụ

Input:

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

Output:

2

Chú ý: Bạn có thể đứng ở đỉnh ~2~ hoặc ~3~.

Giới hạn

• Subtask 1 (60%): ~n, m \le 1000~
• Subtask 2 (40%): Không có giới hạn gì thêm.

Cho một dãy số gồm ~n~ phần tử ~a_1~, ~a_2~, ..., ~a_n~. Với một dãy số gồm ~m~ phần tử ~b_1~, ~b_2~, ..., ~b_m~, trọng số của dãy ~b~ được định nghĩa là tích của giá trị lớn nhất và nhỏ nhất của dãy. Hãy tìm tổng trọng số của các dãy con của dãy ~a~.

Dãy con của dãy ~a~ được định nghĩa là một tập ~a_{i_1}~, ~a_{i_2}~, ..., ~a_{i_k}~ với 1 ~\le~ ~i_1~ < ~i_2~ < ... < ~i_k~ ~\le~ ~n~.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ (~1~ ~\le~ ~n~ ~\le~ ~10^5~).
• Dòng thứ hai chứ ~n~ số nguyên không âm ~a_i~ (~0~ ~\le~ ~a_i~ ~\le~ ~10^9~).

OUTPUT

• In ra một số nguyên duy nhất là tổng trọng số của tất cả các dãy con. Do output có thể rất lớn nên hãy in ra kết quả mod ~10^9 + 7~.

SAMPLE TEST

Input:

5
4 2 1 3 4

Output:

208

SUBTASKS

• ~30\%~ số điểm có ~n~ ~\le~ ~20~.
• ~30\%~ số điểm có ~n~ ~\le~ ~10^3~.
• ~40\%~ số điểm còn lại có ~n~ ~\le~ ~10^5~.