Trên bảng có hai dãy gồm ~n~ số nguyên phân biệt: ~A = [a_1, a_2, \dots, a_n]~ và ~B = [b_1, b_2, \dots, b_n]~. Chúng ta hãy lập ~n^2~ phân số có dạng ~a_i / b_j~ từ chúng, tối giản từng phân số và sắp xếp chúng theo thứ tự không giảm.

Cho một số nguyên ~q~ và ~q~ số nguyên ~c_1, c_2, \dots, c_q~. Với mỗi ~c_j~, bạn cần in phân số thứ ~c_j~ theo thứ tự không giảm từ các phân số kết quả.

Yêu cầu: Với mỗi truy vấn ~c_j~, in phân số không giảm thứ ~c_j~ trong danh sách các phân số đã tối giản.

Input

• Dòng đầu tiên chứa các số nguyên ~n~ và ~q~ (~1 \le n \le 10^5~, ~1 \le q \le 10^5~, ~q \le n^2~).
• Dòng thứ hai chứa ~n~ số nguyên phân biệt ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^6~).
• Dòng thứ ba chứa ~n~ số nguyên phân biệt ~b_1, b_2, \dots, b_n~ (~1 \le b_i \le 10^6~).
• Dòng thứ tư chứa ~q~ số nguyên phân biệt ~c_1, c_2, \dots, c_q~ (~1 \le c_j \le n^2~).

Output

• In ~q~ dòng. Trên dòng thứ ~j~, in phân số thứ ~c_j~ dưới dạng "a b" (phân số tối giản).

Sample Input 1

4 8
3 4 1 2
2 3 4 5
1 16 2 4 5 6 10 15

Sample Output 1

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