See Russian Translation

Fred is the captain of a spaceship crew. He wishes to build a some spaceships. Each spaceship requires n parts labeled from 1 to n.

Fred can buy parts from various vendors. More specifically, there are n vendors, labeled from 1 to n. Each vendor will sell some subset of the parts at various prices. Additionally, each of the vendors will sell the parts for some integer amount between 0 and 10 dollars, inclusive. It is also possible for a vendor to sell the same part for different prices. Each vendor has an unlimited supply of the part/cost that they are selling.

Each spaceship that Fred builds requires exactly one copy of each part. In addition, in the interest of fairness, the spaceship must have exactly one part from every vendor. The total cost of a spaceship is the sum of the cost of the parts.

Now, Fred wants to build spaceships of all kinds (i.e. luxury spaceships, cheap spaceships, and everything in between). Thus, he wants to know, what are all the possible costs a spaceship can take on. More specifically, he is interested in the (10n+1) bit string, where the i-th bit (0-based) is '1' if there is a spaceship that costs exactly i, and '0' otherwise. Help Fred compute this string.

Input Format:
The first line of input will contain two integers n,m.
The next m lines of input will contain three integers a_i, b_i, c_i, which is a description of the i-th product. This means that the a_i-th vendor is selling the b_i-th part for c_i dollars.

Output Format:
A (10n+1) bit string, as described in the statement.

Constraints

For all subtasks:
1 ≤ m ≤ 11 × n²
0 ≤ c_i ≤ 10
1 ≤ a_i,b_i ≤ n

10 pts:
1 ≤ n ≤ 5

20 pts:
1 ≤ n ≤ 12

25 pts:
1 ≤ n ≤ 20

25 pts:
1 ≤ n ≤ 50
There are at most 10 products with nonzero cost.

20 pts:
1 ≤ n ≤ 50