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¹⁸ × 10¹⁸ grid (rows are numbered from top to bottom and columns from left to right with number 0, ..., 10¹⁸-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¹⁸ × 10¹⁸ 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 a₀, a₁, ..., a_k-1 is good iff for each 2 ≤ i < k, a_i = (a_i-2 + a_i-1) modulo M. For example Fibonacci sequence is good.

M is a contant equal to 1000 000 007 (10⁹+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⁵).

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¹⁸, 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).