Trò chơi đẩy bi được thực hiện trên lưới điểm nguyên của mặt phẳng tọa độ Oxy. Trên lưới có một số ô cấm, các ô còn lại là tự do. Khi bắt đầu chơi, một số viên bi sẽ xuất hiện trên lưới, mỗi viên bi sẽ nằm gọn trong một ô và không có ô nào chứa nhiều hơn một viên bi. Người chơi sẽ phải chọn một ô tự do trên lưới làm ô hố, nếu ô được chọn làm ô hố có chứa bi thì viên bi đó sẽ biến mất. Mỗi bước, người chơi có thể chọn một ô chứa bi và đẩy viên bi đó sang một trong bốn ô chung cạnh (hiện đang không có bi), nếu viên bi bị đẩy vào ô hố thì viên bi này cũng sẽ biến mất. Nhiệm vụ của người chơi là đẩy hết tất cả các viên bi trên lưới vào hố với số bước ít nhất.

Yêu cầu: Cho biết vị trí các ô cấm trên lưới và vị trí các ô có chứa bi. Hãy chọn một ô tự do là ô hố và tìm cách đẩy tất cả các viên bi trên lưới vào hố với số bước ít nhất.

Input

• Dòng thứ nhất ghi số nguyên dương ~n~ là số ô cấm;
• Dòng thứ ~i~ với ~i = 1, 2, ., n~ trong ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i, y_i~ mô tả ô ~(x_i, y_i)~ là ô cấm.
• Dòng tiếp theo ghi số nguyên dương ~𝑚~ là số ô chứa bi;
• Dòng thứ ~j~ với ~j = 1,2, … , m~ trong ~𝑚~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u_j, v_j~ mô tả ô ~(u_j, v_j)~ là ô chứa bi.

Output

Một dòng chứa một số nguyên là số bước ít nhất cần thiết để đẩy tất cả các viên bi trên lưới vào hố. Ghi ~-1~ nếu không tồn tại cách chọn hố để đẩy hết tất cả các viên bi trên lưới vào hố. Giới hạn:

• Subtask 1: ~𝑛 = 0; \, 𝑚 = 2~ và các số ~u_i, v_i~ là số nguyên dương không vượt quá ~100;~
• Subtask 2: ~𝑛 = 1; \, 𝑚 = 2~ và các số ~x_i, y_i, u_i, v_i~ là số nguyên dương không vượt quá ~100;~
• Subtask 3: ~𝑛 = 0; \, 𝑚 \le 100~ và các số ~u_i, v_i~ là số nguyên dương không vượt quá ~100;~
• Subtask 4: ~𝑛 \le 1000; \, 𝑚 \le 100~ và các số ~x_i, y_i, u_i, v_i~ là số nguyên dương không vượt quá ~100;~
• Subtask 5: ~𝑛 = 0; 𝑚 \le 100~ và các số ~u_i, v_i~ là số nguyên có giá trị tuyệt đối không vượt quá ~10^9~.

Sample input 1

1
2 2
2
1 2
3 2

Sample output 1

4

Sample input 2

0
2
1 1
5 5

Sample output 2

8

Cho dãy số nguyên dương gồm ~N~ phần tử ~a_1,a_2,...,a_N.~ Xét các chỉ số ~(i,j,k,t)~ thỏa mãn ~i<j<k<t~ và ~\gcd(a_i,a_j )+\gcd(a_k,a_t)~ là lớn nhất. Hãy tìm giá trị lớn nhất đó.</p>

Input

Dòng đầu gồm một số nguyên dương ~N~ với ~4 \le N \le 10^5~; dòng thứ hai gồm ~N~ phần tử nguyên dương ~a_1,a_2,…,a_N~ với ~a_i \le 10^5.~

Output

Đáp số của bài toán.

Sample input

6
8 12 4 20 30 15 19

Sample output

19

• Subtast 1: ~4<N \le 50;~</li>
• Subtast 2: ~50<N \le 1000;~</li>
• Subtast 3: ~1000<N \le 10^5.~</li>

Bảo đang học về các phép toán cộng trừ nhân chia, do đó cô giáo có một trò chơi để thách đố bạn Bảo. Cô giáo đưa ra ba số nguyên dương ~a, b, c~. Sau đó, cô viết lên bảng ~y_1~ lần số ~x_1~, ~y_2~ lần số ~x_2~,. . ., ~y_n~ lần số ~x_n~. Mỗi lượt, cô cho bạn chọn ra một số ~p~ trên bảng và xoá số này đi. Đồng thời, nhân ~a~ lên ~p~ hoặc nhân ~b~ lên ~p~. Cô giáo đố Bảo làm cho tổng ~a + b~ chia hết cho ~c~ sau một vài lượt chơi. Bảo chỉ mới học về các phép toán nên hiện đang cần sự trợ giúp của bạn. Hãy cho biết Bảo có thể hoàn thành thử thách mà cô giao với các thao tác đã cho không. Bạn phải trả lời ~q~ truy vấn riêng biệt.

Input

• Dòng đầu chứa số nguyên dương ~q~ với ~1 \le q \le 5~ là số truy vấn, trong mỗi truy vấn:
• Dòng đầu tiên chứa bốn số nguyên dương ~a, b, c, n~ với ~1 \le a, b, c \le 10^9; 1 \le n \le 4~.
• Trong ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~x_i, y_i~ với ~1 \le x_i \le 10^9; 1 \le y_i \le 35~.

Output

Với mỗi truy vấn, in ra YES nếu Bảo có thể hoàn thành thử thách hoặc NO nếu ngược lại.

Sample input

3
1 2 7 2
6 2
2 2
5 9 7 3
2 3
3 4
4 5
5 6 9 1
4 15

Sample output

YES
YES
NO

Giải thích: Trong truy vấn đầu tiên, Bảo có thể nhân ~a~ với ~6~ và nhân ~b~ với ~2~ hai lần. Khi đó ~1 × 6 + 2 × 2 × 2 = 14~ chia hết cho 7; trong truy vấn thứ hai, Bảo không cần làm gì vì ~a + b~ đã chia hết cho ~c~ ngay từ đầu. Trong truy vấn cuối cùng, Bảo không thể hoàn thành thử thách với các thao tác đã cho.

Subtasks

Đặt ~S~ là tổng các số ~y_1, y_2, ..., y_n~ thì:

• Subtask 1: ~1 \le S \le 15.~
• Subtask 2: ~1 \le S \le 35.~