Giải bài trực tuyến

Ở một công ty nọ có một quy định khá lạ lùng đó là Sếp thì không được thấp hơn nhân viên! Sếp trực tiếp của một nhân viên A được định nghĩa là nhân viên có chiều cao không thấp hơn A và có mức lương nhỏ nhất nhưng vẫn cao hơn A. Quan hệ lính được định nghĩa đệ quy như sau, nếu A là sếp của B thì B và các lính của B đều là lính của A.

Biết công ty này có N nhân viên và một số truy vấn đến các nhân viên. Với mỗi truy vấn, bạn hay tìm sếp trực tiếp và số lượng lính của nhân viên đó.

Dữ liệu

Dòng đầu tiên chứa số lượng test. Mỗi test có cấu trúc như sau:

• Dòng 1 chứa hai số N và Q là số nhân viên và số truy vấn (1 ≤ N ≤ 30000, 1 ≤ Q ≤ 200)
• N dòng tiếp theo mỗi dòng chứa thông tin về một nhân viên gồm 3 số nguyên: số hiệu của nhân viên (luôn có 6 chữ số, chữ số đầu tiên khác 0), lương và chiều cao. Lương không vượt quá 10000000. Chiều cao trong phạm vi 1000000 đến 2500000.
• Q dòng tiếp theo mỗi dòng chứa số hiệu của một nhân viên cần truy vấn.

Kết quả

Với mỗi truy vấn in ra hai số nguyên là số hiệu của sếp trực tiếp và số lính. Nếu không có sếp thì in ra số 0.

Ví dụ

Dữ liệu
2
3 3
123456 14323 1700000
123458 41412 1900000
123457 15221 1800000
123456
123458
123457
4 4
200002 12234 1832001
200003 15002 1745201
200004 18745 1883410
200001 24834 1921313
200004
200002
200003
200001

Kết quả
123457 0
0 2
123458 1
200001 2
200004 0
200004 0
0 3