Cho hai dãy số nguyên cùng độ dài, ~A = (a_1, a_2, ..., a_n); B = (b_1, b_2, ..., b_n)~. 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~.

Dữ liệu

• 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, ..., a_n~ ~(|a_i| \le 10^5)~
• Dòng ~3~: ~n~ số nguyên ~b_1, b_2, ..., b_n~ ~(|b_i| \le 10^5)~
• Dòng ~4~: ~Q~ số nguyên ~k_1, k_2, ..., k_Q~ ~(1 \le k_i \le n)~

Kết quả

• Gồm ~Q~ dòng, dòng thứ ~i~ ~(1 \le i \le Q)~ ghi hai số nguyên ~x_i, y_i~.

Ví dụ

Dữ liệu

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

Kết quả

3 3 
4 3

Giải thích

• Các giá trị xuất hiện ít nhất ~2~ lần trong dãy ~A~: ~1, 3, 4~; trogn 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~; trogn dãy ~B~: ~1, 3, 5~