Một khu du lịch sinh thái có ~N~ địa điểm tham quan đánh số từ ~1~ đến ~N~ và ~M~ con đường hai chiều nối giữa các địa điểm được đánh số từ ~1~ đến ~M~. Giữa hai địa điểm bất kì luôn có đường đi giữa chúng bằng một con đường trực tiếp hoặc các con đường kết nối nhau. Khu sinh thái là nơi hiểm trở nên người ta đánh giá các con đường tương ứng với một độ an toàn. Cụ thể, con đường thứ ~i~ ~(1\leq i\leq M)~ nối giữa hai địa điểm ~u_i~ và ~v_i~ có độ an toàn là ~t_i~.

Để phục vụ khách tham quan đi lại trong khu sinh thái người ta cho thuê các loại xe, mỗi loại tương ứng với một độ an toàn. Chỉ có những chiếc xe có độ an toàn lớn hơn hoặc bằng độ an toàn của con đường mới có thể đi qua đó.

Có ~Q~ khách tham quan cần thuê xe, người thứ ~i~ ~(1\leq i\leq Q)~ muốn thuê một chiếc xe có độ an toàn nhỏ nhất sao cho từ địa điểm xuất phát ~x_i~ trong khu sinh thái có thể đi đến ~k~ địa điểm tham quan khác ~x_i~.

Yêu cầu: Hãy tìm độ an toàn nhỏ nhất của chiếc xe cần thuê cho mỗi khác tham quan.

Input

Vào từ file văn bản SAFETY.INP:

• Dòng đầu tiên chứa ba số nguyên ~N, M, Q~ ~(N, Q\leq 2*10^5, M\leq 4*10^5)~.
• ~M~ dòng đầu tiên chứa ba số nguyên ~u_i, v_i, s_i~ ~(1\leq u_i, v_i\leq N, u_i\ne v_i, 1\leq s_i\leq 10^9)~.
• Q dòng tiếp theo mỗi dòng chứa hai số nguyên ~x_i, k_i~ ~(1\leq x_i\leq N, 1\leq k_i<N)~. Các số trên một dòng cách nhau dấu cách.</li>

Output

Ghi ra file văn bản SAFETY.OUT: Tương ứng với mỗi yêu cầu của khác tham quan theo thứ tự trong tệp dữ liệu vào ghi ra một dòng gồm một số là độ an toàn nhỏ nhất của chiếc xe cần thuê của vị khách đó.

Scoring

• Subtask ~1~ ~(20\%)~: ~N, Q\leq 1000,~ ~M\leq 2000~.
• Subtask ~2~ ~(10\%)~: ~N, Q\leq 1000,~ ~M\leq 4*10^5~.
• Subtask ~3~ ~(10\%)~: ~N, Q\leq 4000,~ ~M\leq 4*10^5~.
• Subtask ~4~ ~(10\%)~: ~N, Q\leq 2*10^5, M\leq 4*10^5~ và ~k_i=1~.
• Subtask ~5~ ~(20\%)~: ~N, Q\leq 2*10^5, M\leq 4*10^5~ và ~k_i=k_j~ với mọi ~i, j~.
• Subtask ~6~ ~(30\%)~: Không còn ràng buộc gì thêm.

Example input 1

5 6 2
1 2 4
1 3 1
2 4 2
2 5 4
3 4 3
4 5 3
1 3
4 4

Example output 1

3
3

Note 1

Trong ví dụ trên:

• Với vị khách đầu tiên sẽ có thể chọn chiếc xe có độ an toàn là ~3~ và từ địa điểm ~1~ có thể đi đến 3 địa điểm ~2, 3~ và ~4~(hoặc ~5~).
• Với vị khách thứ hai sẽ có thể chọn chiếc xe có độ an toàn là 3 và từ địa điểm ~4~ có thể đi đến 4 địa điểm ~1, 2, 3, 5~.