Walking

Problem Description

There is a very long number line, and you start at position $0$. You are going to take $n$ steps. On the $i$-th step, you may move right by $a_i$ or by $b_i$.

After $n$ steps, for each position from $0$ to $m$, can you reach it?

Input Format

The first line contains two integers $n, m$.

The next $n$ lines each contain two integers $a_i, b_i$.

Output Format

One line consisting of a total of $m+1$ digits, each being 0 or 1 indicating whether that position can be reached. The digits are concatenated with no spaces in between.

Sample Input

3 10
1 2
2 6
3 3

Sample Output

00000011001

Constraints

For all data, $1\leq n\leq 100$, $1\leq m\leq 10^5$, $1\leq a_i,b_i\leq 1000$.