Cho một phương trình có dạng: ~N = ax + by + cxy~. Trong đó ~N, a, b, c~ là các hằng số nguyên cho trước.

Yêu cầu: Hãy tìm tất cả các cặp số nguyên không âm ~(x, y)~ thỏa mãn phương trình trên. Dữ liệu bài toán đảm bảo rằng số lượng cặp nghiệm nguyên của phương trình luôn là một số hữu hạn.

Dữ liệu nhập vào từ bàn phím

• Gồm một dòng duy nhất chứa bốn số nguyên ~N, a, b, c~ cách nhau bởi khoảng trắng.

Kết quả ghi ra màn hình

• Dòng đầu tiên: In ra một số nguyên không âm ~K~, là số lượng cặp nghiệm nguyên không âm tìm được.
• ~K~ dòng tiếp theo: Mỗi dòng in ra một cặp nghiệm ~(x, y)~ cách nhau khoảng trắng. Các cặp nghiệm phải được in ra theo thứ tự tăng dần của giá trị ~x~.

Ví dụ

Input 1

24 -4 2 3

Output 1

3
0 12
2 4
10 2

Giải thích 1: Phương trình có dạng: ~24 = -4x + 2y + 3xy~. Có ~3~ cặp số nguyên không âm ~(x, y)~ thỏa mãn phương trình này là ~(0, 12)~, ~(2, 4)~ và ~(10, 2)~. Các cặp nghiệm đã được in ra theo thứ tự ~x~ tăng dần.

Input 2

24 5 0 5

Output 2

0

Giải thích 2: Phương trình có dạng: ~24 = 5x + 5xy~. Phương trình này vô nghiệm vì vế phải luôn là một số chia hết cho ~5~ (bội của ~5~), trong khi vế trái là ~24~ không chia hết cho ~5~. Do đó số lượng nghiệm là ~0~.

Ràng buộc:

• Các hằng số thỏa mãn: ~1 \le N \le 10^{12}~; ~-10 \le a, b, c \le 10~; ~c \neq 0~.
• Có ~40\%~ số test tương ứng với ~40\%~ số điểm thỏa mãn: ~1 \le N \le 10^6~;
• ~35\%~ số test khác tương ứng với ~35\%~ số điểm thỏa mãn: ~1 \le N \le 10^{12}~ và ~b = 0~;
• ~25\%~ số test còn lại tương ứng với ~25\%~ số điểm thỏa mãn: ~1 \le N \le 10^{12}~.

Trên lưới kích thước ~10^9 \times 10^9~, các hàng được đánh số từ ~1~ đến ~10^9~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~10^9~ từ trái sang phải. Ô nằm ở hàng ~i~ (~1 \le i \le 10^9~), cột ~j~ (~1 \le j \le 10^9~) được gọi là ô ~(i, j)~.

Có ~N~ robot trên lưới, robot thứ ~i~ (~1 \le i \le N~) đang ở ô ~(x_i, y_i)~. Mỗi lượt bạn được phép chọn một robot và di chuyển nó sang ô kề cạnh (chung cạnh). Bạn cần tập trung toàn bộ ~N~ robot về cùng một ô để kiểm tra và bảo dưỡng.

Yêu cầu: Hãy tìm cách di chuyển tất cả ~N~ robot về cùng một ô sao cho tổng số lượt di chuyển cần thực hiện là ít nhất.

Dữ liệu nhập vào từ bàn phím

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N \le 10^5~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ (~1 \le i \le N~) chứa hai số nguyên dương ~x_i~ và ~y_i~ (~x_i, y_i \le 10^9~) là tọa độ của robot thứ ~i~. Các số trên cùng một dòng cách nhau bởi khoảng trắng.

Kết quả ghi ra màn hình

• Ghi ra một số nguyên duy nhất là tổng số lượt di chuyển ít nhất để tập trung tất cả ~N~ robot về một ô.

Ví dụ

Input

3
1 3
2 2
3 1

Output

4

Giải thích: Giả sử ta chọn ô ~(2, 2)~ làm điểm tập trung cho cả ~3~ robot:

• Robot 1 từ ô ~(1, 3)~ di chuyển đến ô ~(2, 2)~ cần ~2~ bước.
• Robot 2 từ ô ~(2, 2)~ đi đến ô ~(2, 2)~ cần ~0~ bước (vì đã ở sẵn vị trí).
• Robot 3 từ ô ~(3, 1)~ di chuyển đến ô ~(2, 2)~ cần ~2~ bước. Tổng số bước di chuyển là: ~2 + 0 + 2 = 4~ bước. Đây là phương án tốn ít lượt di chuyển nhất.

Ràng buộc:

• Có ~50\%~ số test tương ứng với ~50\%~ số điểm thỏa mãn: ~N \le 100~ và ~x_i, y_i \le 100~;
• ~50\%~ số test còn lại tương ứng với ~50\%~ số điểm không có ràng buộc gì thêm.

Một sàn nhà có kích thước ~M \times N~ (~M \le N~), được chia thành lưới ô vuông. Các hàng được đánh số từ ~1~ đến ~M~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~N~ từ trái sang phải. Ô nằm ở hàng ~i~ (~1 \le i \le M~), cột ~j~ (~1 \le j \le N~) được gọi là ô ~(i, j)~.

Để lát sàn, người ta dùng các viên gạch có kích thước ~1 \times K~ (với ~M < 2 \times K~ và ~K > 1~). Khi lát sàn, mỗi viên gạch có thể được đặt dọc (chiếm ~K~ ô trên cùng một cột) hoặc đặt ngang (chiếm ~K~ ô trên cùng một hàng). Yêu cầu bắt buộc là tất cả các ô trên sàn đều phải được phủ kín bởi gạch, và không có hai viên gạch nào đè lên nhau.

Yêu cầu: Cho ba số nguyên dương ~M, N, K~. Hãy đếm số cách lát sàn khác nhau. Hai cách lát được gọi là khác nhau nếu tồn tại ít nhất một ô trên sàn mà ở cách lát này nó thuộc một viên gạch đặt ngang, nhưng ở cách lát khác nó lại thuộc một viên gạch đặt dọc.

Dữ liệu nhập vào từ bàn phím

• Gồm một dòng duy nhất chứa ba số nguyên dương ~M, N, K~ (~M \le N \le 2000~; ~M < 2K~; ~K > 1~), các số được viết cách nhau bởi khoảng trắng.

Kết quả ghi ra màn hình

• Gọi ~S~ là số cách lát sàn thỏa mãn. Hãy in ra phần dư của ~S~ khi chia cho ~10^9 + 7~.

Ví dụ

Input

3 5 3

Output

4

Giải thích: Với sàn kích thước ~3 \times 5~ và viên gạch kích thước ~1 \times 3~.

Một cách lát hợp lệ được mô tả như sau:

• Đặt ~1~ viên dọc chiếm trọn cột ~1~.
• Đặt ~3~ viên ngang nằm chồng lên nhau, phủ kín các cột ~2, 3, 4~.
• Đặt ~1~ viên dọc chiếm trọn cột ~5~. Ngoài cách xếp trên, ta còn có thể tìm thêm được ~3~ cách xếp khác thỏa mãn toàn bộ các điều kiện của đề bài. Tổng cộng có ~4~ cách lát sàn hợp lệ.

Ràng buộc:

• Có ~30\%~ số test tương ứng với ~30\%~ số điểm thỏa mãn: ~M \le N \le 5~ và ~K = M~;
• ~30\%~ số test khác tương ứng với ~30\%~ số điểm thỏa mãn: ~K = M~;
• ~40\%~ số test còn lại tương ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Cho một lưới ô vuông gồm ~m~ dòng và ~n~ cột. Các dòng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái qua phải. Ô nằm trên giao của dòng ~x~ và cột ~y~ được ký hiệu là ~(x, y)~.

Trên lưới đã cho, người ta đánh dấu ~k~ ô khác nhau. Ô đánh dấu thứ ~i~ có tọa độ là ~(x_i, y_i)~ với ~i = 1, 2, \dots, k~. Từ một ô đánh dấu có tọa độ ~(x_i, y_i)~, ta chỉ có thể di chuyển đến một ô đánh dấu khác có tọa độ ~(x_j, y_j)~ nếu thỏa mãn một trong hai điều kiện sau đây:

1. ~(x_i \le x_j)~ và ~(y_j \le y_i)~;
2. ~(x_i \ge x_j)~ và ~(y_j \ge y_i)~.

Yêu cầu: Cho ~q~ truy vấn, mỗi truy vấn yêu cầu trả lời câu hỏi sau: Cho hai ô được đánh dấu thứ ~s~ và thứ ~t~ (~1 \le s, t \le k~, ~s \neq t~), hãy tìm một đường di chuyển chỉ đi qua các ô được đánh dấu từ ô ~s~ đến ô ~t~ sao cho đi qua ít ô trung gian nhất. In ra số lượng ô trung gian trên đường đi tìm được.

Dữ liệu nhập vào từ bàn phím

• Dòng đầu tiên chứa ba số nguyên dương ~m, n, k~ (~1 < m, n \le 10^9~; ~1 \le k \le 10^6~).
• ~k~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~x_i, y_i~ là tọa độ của ô được đánh dấu thứ ~i~ (~i = 1, 2, \dots, k~). Các số cách nhau bởi khoảng trắng.
• Dòng tiếp theo ghi duy nhất một số nguyên dương ~q~ là số lượng truy vấn (~1 \le q \le 20~).
• ~q~ dòng cuối cùng, dòng thứ ~j~ chứa hai số nguyên dương ~s_j, t_j~ tương ứng với truy vấn thứ ~j~ (~j = 1, 2, \dots, q~).

Kết quả ghi ra màn hình

• Gồm ~q~ dòng, dòng thứ ~i~ ghi một số nguyên là câu trả lời cho truy vấn thứ ~i~ (số lượng ô trung gian ít nhất). Nếu không tìm được bất kỳ con đường nào thỏa mãn luật di chuyển, ghi ra ~-1~.

Ví dụ

Input

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

Output

1
0

Giải thích: Lưới có ~6~ ô được đánh dấu: Ô 1 ~(2, 4)~, Ô 2 ~(3, 3)~, Ô 3 ~(4, 1)~, Ô 4 ~(1, 2)~, Ô 5 ~(5, 2)~, Ô 6 ~(5, 3)~.

• Truy vấn 1 (Từ ô 1 đến ô 4): Không thể đi trực tiếp từ Ô 1 ~(2, 4)~ đến Ô 4 ~(1, 2)~ vì không thỏa mãn cả hai điều kiện di chuyển. Tuy nhiên, ta có thể di chuyển theo đường đi: Ô 1 ~(2, 4)~ ~\to~ Ô 3 ~(4, 1)~ ~\to~ Ô 4 ~(1, 2)~.

  • Bước 1: Từ ~(2, 4)~ đến ~(4, 1)~ hợp lệ vì ~2 \le 4~ và ~1 \le 4~ (thỏa mãn điều kiện 1).
  • Bước 2: Từ ~(4, 1)~ đến ~(1, 2)~ hợp lệ vì ~4 \ge 1~ và ~2 \ge 1~ (thỏa mãn điều kiện 2). Đường đi này chỉ đi qua đúng ~1~ ô trung gian (là Ô 3). Do đó, số lượng ô trung gian ít nhất là ~1~. (Ngoài ra, đường đi Ô 1 ~\to~ Ô 5 ~\to~ Ô 4 cũng là một đường đi hợp lệ với ~1~ ô trung gian).

• Truy vấn 2 (Từ ô 6 đến ô 5): Từ Ô 6 ~(5, 3)~ ta có thể đi trực tiếp thẳng đến Ô 5 ~(5, 2)~ vì ~5 \le 5~ và ~2 \le 3~ (thỏa mãn hoàn toàn điều kiện 1). Vì có thể đi trực tiếp mà không cần ghé qua ô nào khác, số lượng ô trung gian là ~0~.

Ràng buộc:

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