fleet-funding

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 ai, bi, ci, which is a description of the i-th product. This means that the ai-th vendor is selling the bi-th part for ci dollars. 

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

Constraints

For all subtasks: 
1 ≤ m ≤ 11 × n^2
0 ≤ ci ≤ 10
1 ≤ ai,bi ≤ 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

SAMPLE INPUT
3 9
1 1 1
1 2 3
1 3 9
2 1 2
2 2 5
2 2 6
3 1 4
3 2 10
3 3 0

SAMPLE OUTPUT
0000011100000000001101000000000

Explanation

Fred can make a spaceship of cost 5 by taking part 1 from vendor 2, part 2 from vendor 1, and part 3 from vendor 3. The spaceship of cost 6 can be made from taking part 1 from vendor 1, part 2 from vendor 2, and part 3 from vendor 3.

Source: hackerearth | Difficulty: HARD
Tags: Mathematics


Solutions: