Cho hai dãy số nguyên cùng độ dài, ~A = (a_1, a_2, \dots, a_n); B = (b_1, b_2, \dots, b_n)~. Yêu cầu: Hãy trả lời ~Q~ truy vấn, truy vấn thứ ~i~ ~(1 \le i \le Q)~ có tham số ~k_i~ và yêu cầu xác định các giá trị ~x_i, y_i~, trong đó:

• ~x_i~ là số lượng giá trị có số lần xuất hiện trong dãy ~A~ lớn hơn hay bằng ~k_i~;

• ~y_i~ là số lượng giá trị có số lần xuất hiện trong dãy ~B~ lớn hơn hay bằng ~k_i~.

Input

• Dòng 1: hai số nguyên dương ~n, Q~ ~(1 \le n \le 10^6; 1 \le Q \le 10^6)~;

• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \le 10^5)~;

• Dòng 3: ~n~ số nguyên ~b_1, b_2, \dots, b_n~ ~(|b_i| \le 10^5)~;

• Dòng 4: ~Q~ số nguyên dương ~k_1, k_2, \dots, k_Q~ ~(1 \le k_i \le n)~.

Output

Dòng ~1 \dots Q~: dòng ~i~ ~(1 \le i \le Q)~ ghi hai số nguyên ~x_i, y_i~.

Scoring

Sample Input 1

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

Sample Output 1

3 3
4 3

Notes

• Các giá trị xuất hiện ít nhất 2 lần trong dãy A: ~1, 3, 4~; trong dãy B: ~1, 3, 5~;

• Các giá trị xuất hiện ít nhất 1 lần trong dãy A: ~1, 2, 3, 4~; trong dãy B: ~1, 3, 5~.