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

Lớp của Bách có ~n~ học sinh, được đánh số từ ~1~ đến ~n~. Là thư kí lớp, sau nửa năm học Bách ghi lại được ~m~ mối quan hệ, mối quan hệ thứ ~i~ gồm hai số nguyên ~a_i~, ~b_i~ mô tả việc bạn ~a_i~ "để ý" bạn ~b_i~. Biết rằng việc "để ý" này có tính chất bắc cầu, nghĩa là nếu ~u~ để ý ~v~ và ~v~ để ý ~w~ thì ~u~ cũng để ý ~w~. Những mối quan hệ này là một chiều.

Trong buổi sinh hoạt cuối kì, cô chủ nhiệm hỏi Bách: Trong lớp có bao nhiêu bạn được cả lớp "để ý"? Vì bỏ hơi nhiều tiết Toán nên Bách tính mãi không ra. Là một người bạn, hãy giúp Bách trả lời câu hỏi của cô giáo.

Input

Dòng đầu chứa hai số nguyên ~n~, ~m~ (~1 \le n \le 5 \cdot 10^5~; ~1 \le m \le 10^6~).

~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~, ~b_i~ (~1 \le a_i, b_i \le n~; ~a_i \ne b_i~) mô tả mối quan hệ thứ ~i~.

Output

In ra một số nguyên là số lượng học sinh được cả lớp "để ý".

Scoring

• Subtask 1 (~50~ điểm): ~n \le 10^4~; ~m \le 5 \cdot 10^4~.
• Subtask 2 (~50~ điểm): Không có ràng buộc gì thêm.

Example

Input

3 3
1 2
2 1
2 3

Output

1

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

Nhân dịp sinh nhật Alice được cha mẹ tặng ~n~ bộ xếp chữ, được đánh số từ ~1~ đến ~n~. Bộ xếp chữ thứ ~i~ có ~a_i~ chữ cái "A" và ~b_i~ chữ cái "B". Alice đưa ra một trò chơi như sau: chọn ra hai bộ xếp chữ trong ~n~ bộ, nhóm các chữ cái "A" và chữ cái "B" của hai bộ đã chọn, rồi xếp tất cả chúng thành một hàng ngang. Ví dụ là có ~3~ chữ cái "A" và ~4~ chữ cái "B" thì "ABABABB" và "BBBBAAA" là một trong các cách xếp hợp lệ, và "AAAABBB" là một trong các cách xếp không hợp lệ.

Alice muốn biết: có bao nhiêu cách chọn bộ và xếp chữ như vậy? Hai cách là khác nhau khi hai bộ xếp chữ được chọn ở hai cách là khác nhau, hoặc cách xếp nhận được là khác nhau.

Vì số cách chọn và xếp có thể rất lớn, bạn hãy in ra số cách tìm được chia lấy dư cho ~10^9+7~.

Input

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

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

Output

In ra một số nguyên duy nhất là số cách chọn bộ và xếp chữ tìm được, modulo ~10^9+7~.

Scoring

• Subtask 1 (~20~ điểm): ~n \le 5~; ~a_i, b_i \le 10~.
• Subtask 2 (~20~ điểm): ~n \le 2000~.
• Subtask 3 (~30~ điểm): ~a_i, b_i \le 50~.
• Subtask 4 (~30~ điểm): Không có ràng buộc gì thêm.

Example

Input

2
1 1
2 1

Output

10