The link to the Russian translation.

The evil vault is open again. This time Damon is looking for the last "Everlasting".

The vault is unstable again. In order to enter the vault Damon needs to solve the a puzzle. It's ironic since the puzzle is the vault itself!

The vault is a 10^18 × 10^18 grid (rows are numbered from top to bottom and columns from left to right with number 0, ..., 10^18-1).

Initially Damon knows nothing about the grid. In n steps, each step the evil monster inside the vault gives him some information about the grid (she gives him the value written in a cell) and asks her if there is a pretty grid satisfying the information so far (all informations given so far are true about that grid). A 10^18 × 10^18 grid is pretty iff each cell in it contains a non-negative integer less than M and the sequence of each row (from left to right) and each column (from top to bottom) is a good sequence.

A sequence a0, a1, ..., ak-1 is good iff for each 2 ≤ i < k, ai = (ai-2 + ai-1) modulo M. For example Fibonacci sequence is good.

M is a contant equal to 1000 000 007 (10^9+7).

Your task is to answer the monster (since you love Damon and don't want him to get hurt).

Input
The first line of input contains a single integer n (1 ≤ n ≤ 10^5).

The next n lines contain the informations monster has given Damon. i-th line contains the information she's gave Damon in i-th step, three integers r, c, x meaning the cell in c-th column of r-th row contains integer x (0 ≤ r, c < 10^18, 0 ≤ x < M).

Output
Print a binary string of length n. It's i-th character should be equal to 1 if and only iff there is a pretty grid satisfying the first i informations (monster's answer in i-th step).

SAMPLE INPUT
10
3 5 300
8 3 1281
1 2 24
4 5 506
9 1 45
0 2 28
7 4 17
9 5 43
6 6 33
9 5 5548

SAMPLE OUTPUT
1111000000

见题面

见题面