Ăn ngon

Nông trại có $N$ đồng cỏ được đánh số từ $1$ đến $N$ và $M$ con đường hai chiều. Con đường thứ $i$ nối hai đồng cỏ khác nhau $p_i$ và $q_i$, đi hết $t_i$ đơn vị thời gian theo cả hai chiều. Chuồng bò nằm ở đồng cỏ $N$, và từ mọi đồng cỏ đều có thể đi tới chuồng.

Trên nông trại còn có $K$ kiện cỏ. Kiện thứ $j$ nằm ở đồng cỏ $h_j$ và có độ ngon $y_j$.

Ở mỗi đồng cỏ $1,2,\dots ,N-1$ có đúng một con bò, và tất cả đều phải về chuồng. Gọi $D_i$ là thời gian ít nhất để đi từ đồng cỏ $i$ về đồng cỏ $N$. Con bò ở đồng cỏ $i$ chịu ghé kiện cỏ thứ $j$ nếu thời gian ít nhất của một hành trình đi từ đồng cỏ $i$, có đi qua đồng cỏ $h_j$, rồi về đồng cỏ $N$ vượt quá $D_i$ không quá $y_j$ đơn vị. Mỗi con bò ăn nhiều nhất một kiện cỏ, và một kiện cỏ có thể phục vụ nhiều con bò.

Với mỗi con bò, hãy xác định nó có ăn được cỏ trên đường về chuồng hay không.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $N$, $M$, $K$.
• $M$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $p_i$, $q_i$, $t_i$ mô tả một con đường.
• $K$ dòng tiếp theo, dòng thứ $j$ chứa hai số nguyên $h_j$, $y_j$ mô tả một kiện cỏ.

Dữ liệu ra

• In ra $N-1$ dòng. Dòng thứ $i$ ghi $1$ nếu con bò ở đồng cỏ $i$ ăn được một kiện cỏ, ghi $0$ nếu ngược lại.

Ràng buộc

• $2\le N\le 50000$
• $1\le M\le 100000$
• $1\le K\le N$
• $1\le p_i,q_i\le N$ và $p_i\ne q_i$
• $1\le t_i\le {10}^9$
• $1\le h_j\le N$ và $1\le y_j\le {10}^9$
• Từ mọi đồng cỏ đều có thể đi tới đồng cỏ $N$.

Ví dụ