Quốc gia ~Beta~ có ~N~ thành phố được đánh số từ ~1~ đến ~N~. Các thành phố được nối với nhau bởi ~M~ con đường hai chiều, được đánh số từ ~1~ đến ~M~, giữa hai thành phố bất kỳ có tối đa một con đường nối trực tiếp chúng. Con đường hai chiều số ~i~ ~(1 \le i \le M)~ nối trực tiếp giữa hai thành phố phân biệt ~U_i~ và ~V_i~ có độ dài ~W_i~. Một đường đi gồm ~K~ thành phố từ thành phố ~X~ tới thành phố ~Y~ là một chuỗi các thành phố ~P_1, P_2, \dots, P_k,~ sao cho ~P_1 = X~, ~P_k = Y~ và có con đường trực tiếp giữa hai thành phố ~P_i~ và ~P_{i + 1}~ ~(\forall i = 1, 2, \dots, K - 1)~. Ở quốc gia ~Beta~, mọi thành phố đều có đường đi tới thành phố khác. Chi phí di chuyển của một đường đi từ ~X~ tới thành phố ~Y~ là tổng độ dài của các con đường trên đường đi đó. Gọi ~D(X, Y)~ là chi phí di chuyển nhỏ nhất trong số các chi phí di chuyển của các đường đi từ thành phố ~X~ tới thành phố ~Y~. Quy ước ~D(X, X) = 0~ với mọi thành phố ~X~.

Thành phố số ~1~ có một nhà máy đúc khuôn và thành phố số ~2~ có một nhà máy sản xuất mạ tĩnh điện. Một doanh nghiệp muốn chọn một thành phố nào đó để mở một trung tâm chế tạo thép trang trí sử dụng nguyên liệu từ nhà máy đúc khuôn và nhà máy sản xuất mạ tĩnh điện. Thành phố ~Y~ được gọi là tốt hơn hoặc tương đương với thành phố ~X~ khi và chỉ khi ~D(Y, 1) \le D(X, 1)~ và ~D(Y, 2) \le D(X, 2)~. Lưu ý, thành phố ~X~ được xem là tố hơn hoặc tương đương so với chính nó. Doanh nghiệp tính hạng của thành phố ~X~ là số lượng thành phố ~Y~ tốt hơn hoặc tương đương so với thành phố ~X~. Cụ thể, công thức tính hạng là:

$$R(X) = |\{Y \in \{1, 2, \dots, N\} : D(Y, 1) \le D(X, 1) \text{ và } D(Y, 2) \le D(X, 2) \}|$$

Ngoài ra, doanh nghiệp cũng cam kết với chính quyền địa phương rằng trước khi đặt trung tâm chế tạo thép ở thành phố ~X~ nào đó, họ sẽ cải tạo một con đường nối với thành phố ~X~. Doanh nghiệp đã khảo sát và đứa ra ~P~ phương án. Với Phương án thứ ~j~ ~(1 \le j \le P)~. Với phương án thứ ~j~ ~(1 \le j \le P)~, con đường ~T_j~ nối giữa thành phố ~U_{T_j}~ và ~V_{T_j}~ sẽ được chọn để cải tạo giúp cho độ dài mới ~W_{T_j}'~ bé hơn độ dài ban đầu ~W_{T_j}~. Với mỗi phương án, sau khi cải tạo đường, doanh nghiệp cần tính hạng của thành phố ~U_{T_j}~ và thành phố ~V_{T_j}~. Các phương án là độc lập, nghĩa là các phương án đều chỉ áp dụng lên hiện trạng ban đầu của ~M~ con đường.

~\textbf{Yêu cầu:}~ Với phương án thứ ~j~ ~(1 \le j \le P)~, hãy giúp doanh nghiệp tìm ra hạng của thành phố ~U_{T_j}~ và thành phố ~V_{T_j}~ sau khi cải tạo con đường ~T_j~.

Input

Vào từ file văn bản ~\texttt{IMPEVAL.INP}~:

– Dòng đầu chứa ba số nguyên ~N, M~ và ~P~ lần lượt là số lượng thành phố, số lượng con đường và số lượng phương án ~(2 \le N \le 10^5; 1 \le M, P \le 10^5).~

– Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa ba số nguyên ~U_i~, ~V_i~ và ~W_i~ lần lượt là hai thành phố được nối bởi con đường số ~i~ và độ dài của con đường này ~(1 \le U_i, V_i \le N; 1 \le W_i \le 10^9).~

– Dòng thứ ~j~ trong số ~P~ dòng tiếp theo chứa hai số nguyên ~T_j~ và ~W_{T_j}'~ lần lượt là chỉ số con đường được lên phương án cải tạo và độ dài sau khi cải tạo ~(1 \le T_j \le M; 1 \le W_{T_j}' < W_{T_j}).~

Output

Ghi ra file văn bản ~\texttt{IMPEVAL.OUT}~:

– Gồm ~P~ dòng, trong đó dòng thứ ~j~ ghi ra hai số nguyên ~R(U_{T_j})~ và ~R(V_{T_j})~ tương ứng là hạng của thành phố ~U_{T_j}~ và thành phố ~V_{T_j}~ nếu phương án thứ ~j~ được triển khai.

Scoring

Sample Input 1

5 6 2
1 5 8
5 2 10
1 3 6
3 2 12
3 4 3
4 2 11
5 2
6 9

Sample Output 1

1 2
1 1

Notes

– Với con đường số ~5~ có độ dài mới bằng ~2~, thành phố số ~3~ có hạng ~1~ do chỉ có duy nhất thành phố số ~3~ tốt hơn hoặc tương đương với thành phố số ~3~, thành phố số ~4~ có hạng ~2~ do có hai thành phố tốt hơn hoặc tương đương với nó là thành phố số ~4~ và thành phố số ~5~.

– Với con đường số ~6~ có độ dài mới bằng ~9~, thành phố số ~4~ và thành phố ~2~ đều có hạng ~1~.