## Falling Snowflakes

View as PDF

Points: 15 (partial)
Time limit: 1.2s
Java 8 2.5s
PyPy 2 2.5s
PyPy 3 2.5s
Memory limit: 256M
PyPy 2 512M
PyPy 3 512M

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

Violet is an active comfort seeker and wishes to know the conditions required in order to achieve maximum comfort.

She has already determined the three conditions required in order to achieve a state of maximum comfiness, firstly a peaceful winter night, secondly a cup of hot chocolate and lastly a large window to observe the falling snow.

Violet's window is an matrix with rows and columns numbered from to . There are different snowflakes that she observes. Unfortunately snowflakes don't last forever and will eventually melt. Luckily for you, for each snowflake, she has written down and , the row and column the snowflake lands on respectively and and , the time when the snowflake lands and disappears from the window respectively.

In order for Violet to maximize her enjoyment in the future, she has queries for you to answer. Queries come in three possible forms:

• R a b t: The number of snowflakes there are located between row to , inclusive at time .
• C a b t: The number of snowflakes there are located between column to , inclusive at time .
• V a b c d t: The number of snowflakes there are located between row to , inclusive or column to , inclusive at time .

A snowflake that melts at time is not included in the answer to queries that have the same .

Conversely, a snowflake that lands on the window at time is included in the answer to queries that have the same , given that it falls within the constraints of the query.

Note: There may be multiple snowflakes within the same grid at a given time but since all snowflakes are unique, they are to be counted separately.

#### Input

First line: Three integers, , the size of the window, , the number of snowflakes observed and , the number of queries.

Next lines: , the row and column the snowflake lands on, , the time when it lands, , the time when it disappears.

Next lines: valid queries.

For all queries: , ,

The following additional constraints will apply.

• At least 20% of the marks will have test cases where , , , ,
• At least 40% of the marks will have test cases where , , , ,
• The remaining marks will have test cases where , , , ,

#### Output

Output the answer to each query on its own line.

#### Sample Input

6 7 3
2 3 3 9
2 4 4 5
4 4 5 10
4 4 2 8
2 3 1 5
4 5 9 10
2 4 7 9
V 2 3 5 5 7
R 3 4 4
C 4 5 4

#### Sample Output

2
1
2