D. Black and White Bead String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are a craftsman in the Kuanzhai Alley. One day, a customer ordered a black and white bead string from you. The black and white bead string is shaped like a chain, with black and white beads arranged on it. The customer also presented you with $$$k$$$ conditions, each of which is as follows:

  • Given $$$x,y$$$, it is required that there exists at least one substring in the black and white bead string, such that the length of the substring is $$$x$$$, and it contains exactly $$$y$$$ black beads.

Here, a substring refers to a continuous segment of beads in the black and white bead string.

Please construct a black and white bead string for the customer that satisfies all the above conditions and has the minimum length. To ensure that the bead string you construct meets the above conditions, you also need to provide the position of a substring that satisfies each condition.

Input

The first line contains an integer $$$k$$$ ($$$1\leq k\leq 10^5$$$), indicating the number of conditions.

The next $$$k$$$ lines, where the $$$i$$$-th line contains two integers $$$x_i,y_i$$$ ($$$1\leq x_i\leq 10^6,0\leq y_i\leq x_i$$$), representing the content of the $$$i$$$-th condition.

Output

The first line contains an integer $$$l$$$, representing the minimum length of the black and white bead string that satisfies the conditions.

The second line contains a string consisting of 0 and 1, with a length of $$$l$$$, representing the black and white bead string you constructed. Here, 0 represents a white bead, and 1 represents a black bead.

The next $$$k$$$ lines, where the $$$i$$$-th line contains an integer $$$p_i$$$, representing the starting position of a substring that satisfies the $$$i$$$-th condition in the bead string. Here, the position of the bead string is numbered starting from $$$0$$$.

Examples
Input
3
3 1
3 2
2 0
Output
4
1100
1
0
2
Input
4
2 1
3 3
4 0
3 2
Output
7
1110000
2
0
3
1