Có \(N\) học sinh (được đánh số từ \(1\) đến \(N\)) đang đứng trên mặt phẳng tọa độ \(\text{Oxy}\). Học sinh \(1\) đứng ở gốc tọa độ (điểm \((0,0)\)).

Cho biết \(M\) thông tin về vị trí tương đối của học sinh này so với học sinh kia. Cụ thể, thông tin thứ \(i\) cho biết rằng đối với học sinh \(A_i\) thì học sinh \(B_i\) đang đứng cách \(X_i\) đơn vị theo hướng trục hoành và \(Y_i\) theo hướng trên trục tung. Bạn hãy viết chương trình tổng hợp tất cả các thông tin đã cho để kết luận tọa độ cụ thể của từng học sinh nhé!

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) \(\left(1\le N\le 2\times 10^5, 0\le M\le 2\times 10^5\right)\).
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa bốn số nguyên \(A_i\), \(B_i\), \(X_i\), \(Y_i\) \(\left(1\le A_i\ne B_i\le N, -10^9\le X_i, Y_i\le 10^9\right)\).
• Dữ liệu đảm bảo các thông tin được cho luôn nhất quán và không mâu thuẫn lẫn nhau.

Output

• Gồm \(N\) dòng. Dòng thứ \(i\) in ra hai số nguyên thể hiện tọa độ của học sinh \(i\). Nếu bạn không đủ thông tin để kết luận về tọa độ của một học sinh nào đó thì in ra NA ở dòng tương ứng.

Ví dụ

Sample input 01

3 2
1 2 2 1
1 3 -1 -2

Sample output 01

0 0
2 1
-1 -2

Minh họa

Sample input 02

3 2
2 1 -2 -1
2 3 -3 -3

Sample output 02

0 0
2 1
-1 -2

Minh họa

Sample input 03

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

Sample output 03

0 0
0 0
0 0
NA
NA