F. Escape Route
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In a tourist archipelago consisting of $$$n$$$ islands, there are $$$m$$$ bidirectional bridges connecting them. The islands are numbered $$$1, 2, \ldots, n$$$. The $$$i$$$-th bridge connects islands $$$u_i$$$ and $$$v_i$$$, and it takes $$$t_i$$$ minutes to cross. Furthermore, each bridge has a height $$$h_i$$$, representing its height above sea level in centimeters.

An unprecedented natural disaster has struck the archipelago, causing the sea level to rise at a rate of $$$1$$$ centimeter per minute. A bridge $$$i$$$ becomes unusable exactly $$$h_i$$$ minutes after the disaster begins. To ensure safety, a vehicle can only cross bridge $$$i$$$ if the entire traversal completes before the bridge is submerged. Specifically, if a vehicle starts crossing bridge $$$i$$$ at time $$$T$$$, it must arrive at the other end by time $$$T + t_i$$$, and this arrival time must satisfy $$$T + t_i \le h_i$$$.

Island $$$1$$$ serves as the evacuation center. Residents on each island are intelligent; they will choose a route that allows them to reach island $$$1$$$ safely before any bridge they cross becomes submerged. If no such path exists, they will remain on their current island to await rescue.

Given this scenario, for each island $$$k$$$ (where $$$k \in \{1, \ldots, n\}$$$), determine if the residents on island $$$k$$$ can safely reach island $$$1$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$, representing the number of islands and the number of bridges, respectively.

Followed by $$$m$$$ lines, the $$$i$$$-th of which contains four integers $$$u_i, v_i, t_i, h_i$$$, representing a bridge connecting islands $$$u_i$$$ and $$$v_i$$$ with travel time $$$t_i$$$ and height $$$h_i$$$.

  • $$$1\leq n\leq 10^5$$$
  • $$$1\leq m\leq 3\times 10^5$$$
  • $$$1\leq u_i, v_i \leq n, u_i\neq v_i$$$
  • $$$1\leq t_i \leq h_i \leq 10^9$$$
Output

Output a single string of length $$$n$$$. The $$$i$$$-th character of the string should be '1' if the residents of island $$$i$$$ can safely reach island $$$1$$$, and '0' otherwise.

Examples
Input
3 2
1 3 2 4
2 3 3 5
Output
101
Input
5 6
1 2 4 4
1 4 8 13
2 3 1 3
2 4 3 7
3 5 2 2
4 5 7 8
Output
11110
Note

Explanation for Sample 1

Residents of island $$$1$$$ are already at island $$$1$$$. Residents of island $$$3$$$ can safely cross the first bridge and arrive at island $$$1$$$ at time $$$2$$$. However, residents of island $$$2$$$ must first cross the second bridge to reach island $$$3$$$ at time $$$3$$$; if they then attempt to cross the first bridge, they will get stuck in the middle at time $$$4$$$, exactly when the bridge becomes unusable since $$$h_1=4$$$. Therefore, the residents of island $$$2$$$ cannot safely reach island $$$1$$$.