Your younger sibling got a new toy for Christmas: a set of balls, tracks, and switches!

A ball sculpture is a construction made out of said tracks and switches where a small ball is placed at the top of the sculpture and travels down the tracks to the bottom. In between the top and bottom of the sculpture, there are ~N~ switches that control the path that the ball takes.

The switches are labelled from ~1~ to ~N~ in order of height from the top of the sculpture to the bottom. Each switch ~i~ has two output tracks which each lead either to another switch further down in the sculpture, or go directly to the bottom of the sculpture. This is denoted by two values ~a_i~ and ~b_i~ where ~i < a_i, b_i \le N+1~, where a value of ~N+1~ represents the track going to the very bottom.

A switch can be in one of two states: ~0~ or ~1~. If a ball arrives while it is in state ~0~, the ball goes down a track to ~a_i~, but if it is in state ~1~, it goes to ~b_i~. In either case, the state of the switch is flipped to the opposite state.

Initially, all switches are in state ~0~. Then, a sequence of ~M~ balls are placed at the top of the sculpture, where the previous ball must reach the bottom of the sculpture before the next ball is placed.

Bored, your younger sibling asks you: what is the final state of all the switches after all ~M~ balls reach the bottom?

Constraints

~1 \le N \le 10^6~

~1 \le M \le 10^9~

~i < a_i, b_i \le N+1~

Input Specification

The first line contains two space-separated integers ~N~ and ~M~.

~N~ lines follow; the ~i~-th one contains two space-separated integers ~a_i, b_i~.

Output Specification

Output ~N~ digits on a single line, with the ~i~-th digit being the state of switch ~i~.

Sample Input 1

3 5
2 3
4 4
4 4

Output for Sample Input 1

110

Explanation for Output for Sample Input 1

The sequence of states is 000, 110, 011, 101, 000, 110.

Sample Input 2

4 11
5 2
5 3
5 4
5 5

Output for Sample Input 2

1101