All Tracks Problem

Gods & Monsters

Hard, Math, Matrix Exponentiation, Modular arithmetic, Modular exponentiation, Number Theory


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 1018 × 1018 grid (rows are numbered from top to bottom and columns from left to right with number 0, ..., 1018-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 1018 × 1018 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 (109+7).

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


The first line of input contains a single integer n (1 ≤ n ≤ 105).

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 < 1018, 0 ≤ x < M).


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).

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
Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

June Clash '16

View All Notifications