## Back to School '16: Textbooks

View as PDF

Points: 20 (partial)
Time limit: 4.5s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

bobhob314 has applied some super sticky substance to his textbooks. This mysterious substance is so sticky that it prevents textbooks from falling off ledges in a tetris-like manner. The th textbook is placed starting at and is units long and wide. The textbooks are given in the order in which they are placed.

The sun is shining directly above and bobhob314 wants to protect more books from the sun. Find the total area unoccupied by a textbook in the shade (has at least one part of a textbook above). Print this modulo .

#### Input Specification

The first line contains a single integer .

The next lines contain space separated integers, , and .

Note: fast input may be required.

#### Output Specification

Output a single integer, the number of empty spaces under at least one textbook modulo .

#### Sample Input 1

3
1 3 1
3 3 1
5 3 1

#### Sample Output 1

6

#### Sample Input 2

5
1 2 1
3 1 1
3 4 1
6 3 2
5 2 1

#### Sample Output 2

9

#### Explanation for Sample Output 2

The textbooks are represented with a digit . A period represents a unit in the shade.

    55
.444
.444
3333..
112.....

#### Sample Input 3

4
5 1 2
3 1 2
5 1 1
3 3 1

#### Sample Output 3

4

#### Explanation for Sample Output 3

  444
..3
2.1
2.1

• commented on Sept. 17, 2016, 11:46 p.m.

If I'm not mistaken, test case 9 in subtask 1 has s>100 000 or l>100 000.

• commented on Sept. 18, 2016, 10:34 a.m. edit 2

The test cases have been fixed

• commented on Sept. 16, 2016, 9:08 p.m. edit 2

bobhob314 and his super sticky substance ( ͡° ͜ʖ ͡°)---->Suspicious.

• commented on Sept. 17, 2016, 4:27 p.m.

:(