Số nguyên dương ~N~ là chia hết cho ~9~ khi và chỉ khi tổng các chữ số của nó chia hết cho ~9~.

Yêu cầu: Cho số nguyên dương ~N~. Hãy đổi một chữ số trong ~𝑁~ sao cho số mới được tạo ra có giá trị nhỏ nhất và chia hết cho ~9~. Số mới được tạo ra có thể có chữ số ~0~ ở đầu tiên.

Dữ liệu nhập vào từ file văn bản CH9.INP:

• Dòng đầu tiên chứa ~T~ là số test dữ liệu của bài toán ~(T \le 15);~
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~N~.

Tổng số lượng chữ số ở mọi test không quá ~10^6~.

Kết quả ghi ra file văn bản CH9.OUT:

Gồm ~𝑇~ dòng, mỗi dòng chứa một số nguyên dương tương ứng là kết quả theo yêu cầu.

Ràng buộc:

• Có ~50\%~ số test tương ứng với ~50\%~ số điểm của bài thoả mãn: ~T=1;~
• ~50\%~ số test còn lại ứng với ~50\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3
34125
5441
22221

Output

34128
0441
22221

Cho một ma trận ~n~ hàng ~m~ cột, ô ở hàng thứ ~i~ từ trên xuống và cột thứ ~j~ từ trái sang được gọi là ô ~(i, j)~.

Có một dãy cấp số nhân ~k, k^2, k^3, \dots, k^{n \times m}~. Các số này được xếp lên ma trận đã cho lần lượt theo từng hàng từ trên xuống dưới, ở mỗi hàng xếp các số lần lượt từ trái sang phải.

Cho ~q~ truy vấn, mỗi truy vấn gồm bốn số nguyên ~x_1~, ~y_1~, ~x_2~, ~y_2~. Hãy tính tổng các số trong ma trận con có góc trái trên là ~(x_1, y_1)~ và góc phải dưới là ~(x_2, y_2)~. Vì kết quả mỗi truy vấn có thể rất lớn, hãy in ra dưới modulo ~M~.

Input

Dòng đầu chứa bốn số nguyên ~n~, ~m~, ~k~, ~M~ (~1 \le n, m \le 10^9~; ~1 \le k \le 10^9~; ~10^9 + 5 \le M \le 2 \times 10^9~).

Dòng tiếp theo chứa số nguyên ~q~ (~1 \le q \le 10000~).

~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~x_1~, ~y_1~, ~x_2~, ~y_2~ (~1 \le x_1 \le x_2 \le n~; ~1 \le y_1 \le y_2 \le m~).

Output

Với mỗi truy vấn, in ra một số nguyên là tổng của ma trận con tương ứng, modulo ~M~.

Scoring

• Subtask 1 (~20~ điểm): ~n, m \le 1000~; ~q = 1~.
• Subtask 2 (~20~ điểm): ~n, m \le 1000~;
• Subtask 3 (~20~ điểm): ~q = 1~; ~(x_2 - x_1 + 1) \times (y_2 - y_1 + 1) \le 10^7~.
• Subtask 4 (~20~ điểm): ~M~ là số nguyên tố.
• Subtask 5 (~20~ điểm): Không có ràng buộc gì thêm.

Example

Input

3 3 2 1000000007
2
1 1 2 2
1 2 3 3

Output

54
876

Cho dãy ~a_1, a_2, \dots, a_n~ gồm ~n~ số nguyên. Bạn nhận được ~q~ truy vấn, truy vấn thứ ~i~ được mô tả bằng hai số nguyên ~L_i~, ~R_i~. Với truy vấn thứ ~i~ bạn cần tìm bất kì số nào xuất hiện đúng ~1~ lần trong đoạn từ ~L_i~ đến ~R_i~ của dãy ~a~, tức là ~a_{L_i}, a_{L_i + 1}, \dots, a_{R_i}~.

Input

Dòng đầu chứa số nguyên ~n~ (~1 \le n \le 5 \times 10^5~).

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 5 \times 10^5~).

Dòng thứ ba chứa số nguyên ~q~ (~1 \le q \le 5 \times 10^5~).

~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~L_i~, ~R_i~ (~1 \le L_i \le R_i \le n~).

Output

In ra ~q~ dòng, dòng thứ ~i~ chứa một số nguyên là số xuất hiện đúng ~1~ lần tìm được, hoặc ~0~ nếu không tìm được số nào.

Scoring

• Subtask 1 (~25~ điểm): ~n, q \le 10^3~.
• Subtask 1 (~25~ điểm): ~n, q \le 10^5~.
• Subtask 1 (~50~ điểm): ~n, q \le 5 \times 10^5~.

Example

Input

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

Output

4
0

Đối với mỗi số tự nhiên ~x~, ta định nghĩa hàm trọng số của ~x~ là ~f(x)~ có công thức như sau:

• ~f(x) = ~ tổng của các số sinh ra từ các đoạn con liên tiếp của ~x~ dưới dạng cơ số ~10~.
• Ví dụ: ~f(1004) = 1 + 10 + 100 + 1004 + 0 + 00 + 004 + 0 + 04 + 4 = 1136~.

Bạn được nhận hai số nguyên dương ~n~ và ~k~. Xét tập ~S~ là tập các số nguyên dương gồm ~n~ chữ số, tất cả các chữ số đều bé hơn hoặc bằng ~7~ và chúng không có số ~0~ đứng đầu, hãy đếm số bộ ~(x,y,z) \in S~ thỏa mãn ~x < y < z~ và tổng ~(f(x) + f(y) + f(z))~ chia hết cho ~k~.

Input

• Gồm hai số nguyên dương ~n, k~

Output

• Ghi một số nguyên duy nhất là số bộ ba tìm được, chỉ cần in ra kết quả sau khi chia lấy dư cho ~10^9+7.~.

Subtask

• Có ~8\%~ test với ~n≤6;k≤10~
• Có ~20\%~ test với ~n≤9;k≤100~
• Có ~28\%~ test với ~n≤100;k≤100~
• Có ~44\%~ test với ~n≤1000;k≤1000~

Example

Sample input

1 7

Sample output

5

Sample input

3 30

Sample output

494146

Cho một hoán vị ~p_1,p_2,…,p_n~. Bạn cần trả lời ~q~ truy vấn. Truy vấn thứ ~i~ là một cặp số nguyên (~l_i,r_i~ ), bạn cần tính ~f(l_i,r_i )~.

Gọi ~m_{l,r}~ là vị trí của phần tử lớn nhất trong đoạn ~p_l,p_{l+1},…,p_r~

~f(l,r)=(r-l+1)+f(l,m_{l,r}-1)+f(m_{l,r}+1,r)~ nếu ~l \leq r~ và bằng 0 trong trường hợp ngược lại .

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \leq n, q \leq 10^6~) - kích thước của hoán vị ~𝑝~ và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ các số nguyên đôi một phân biệt ~p_1,p_2,…,p_n~ ~(1 \leq p_i \leq n, p_i \neq p_j \forall i \neq j)~ - hoán vị ~p~.
• Dòng thứ ba chứa ~q~ số nguyên ~l_1,l_2,…,l_q~ – giá trị ~l~ của các truy vấn.
• Dòng thứ tư chứa ~q~ số nguyên ~r_1,r_2,…,r_q~ – giá trị ~r~ của các truy vấn.
• Đầu vào đảm bảo rằng ~1 \leq l_i \leq r_i \leq n~ cho tất cả các truy vấn.

Output

• In ~q~ số nguyên - các giá trị ~f(l_i,r_i )~ cho các truy vấn tương ứng.

Subtask

• Subtask ~1~ (30%): ~1 \leq n, q \leq 500~
• Subtask ~2~ (30%): ~1 \leq n, q \leq 5000~
• Subtask ~3~ (20%): Hoán vị được sắp xếp tăng dần hoặc giảm dần
• Subtask ~4~ (20%): Giới hạn gốc

Example

Sample input

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

Sample output

1 8 6 5 3

Cho ~A~ là ~1~ ma trận vuông có kích thước ~n \times n~ và ~A~ chỉ gồm các ô có giá trị ~0~ hoặc ~1~. Tìm số nguyên dương ~k~ nhỏ nhất sao cho lũy thừa bậc ~k~ của ma trận ~A~ là ma trận gồm toàn các số ~0~, biết rằng lũy thừa của một ma trận được mô tả như sau:

Input:

• Dòng đầu gồm ~2~ số nguyên ~n~ và ~m~ trong đó ~n~ là kích thước ma trận còn ~m~ là số ô có giá trị bằng ~1~ trên ma trận ~A~.
• ~m~ dòng tiếp theo, trên mỗi dòng có một cặp số ~(i, j)~ ~(1 \leq i, j \leq n)~ là tọa độ của các ô có giá trị bằng ~1~ trên ma trận ~A~, dữ liệu đảm bảo rằng không có cặp số ~(i, j)~ nào xuất hiện ~2~ lần. Một ô có tọa độ ~(i, j)~ nếu như nó nằm tại dòng thứ ~i~ tính từ trên xuống và cột thứ ~j~ tính từ bên trái sang của ma trận ~A~, nếu toạ độ của ô không nằm trong ~m~ cặp số được cho thì ô đó mặc định có giá trị bằng ~0~.

Constraints

• ~1 \leq n \leq 5 \times 10^5~
• ~0 \leq m \leq 5 \times 10^5~

Subtask

• ~10\%~ số test có ~1 \le n \le 4~.
• ~30\%~ số test khác có ~1 \le n \le 60~.
• ~60\%~ số test còn lại không có điều kiện gì thêm.

Output:

• In ra số nguyên dương ~k~ nhỏ nhất hoặc ~-1~ nếu ~k~ không tồn tại.

Sample Input 1:

4 2
1 2
4 3

Sample Output 1:

2

Sample Input 2:

3 3
1 1
2 2
3 3

Sample Output 2:

-1

Explanation

• Ở Sample test 1, dễ thấy ~A^2~ là ma trận toàn ~0~.

• Ở Sample test 2, ma trận ~A~ đã cho được gọi là một Identity matrix, khi lấy lũy thừa bậc ~k~ của một Identity matrix thì giá trị các ô trên ma trận hoàn toàn giữ nguyên.