### 2017 Canadian Computing Olympiad

## Day 1, Problem 3 - Vera and Modern Art

After being inspired by the great painter Picowso, Vera decided to make her own masterpiece. She has an empty painting surface which can be modeled as an infinite 2D coordinate plane. Vera likes powers of two (1, 2, 4, 8, 16, …) and will paint some points in a repeated manner using step sizes which are a power of two.

Vera will paint `N` times. The `i`-th time can be described by three integers `x _{i}`,

`y`,

_{i}`v`. Let

_{i}`a`be the largest power of two not greater than

_{i}`x`and let

_{i}`b`be the largest power of two not greater than

_{i}`y`. Vera will add a paint drop with colour

_{i}`v`to all points that are of the form (

_{i}`x`+

_{i}`a`,

_{i}p`y`+

_{i}`b`), where

_{i}q`p`,

`q`are non-negative integers. A point may have multiple paint drops on it or have multiple drops of the same colour.

Then, Vera will ask `Q` questions. For the `j`-th question, she wants to know the colour at the point (`r _{j}`,

`c`). The colour at a point is equal to the sum of the colours of all paint drops at that point. If there are no paint drops at a point, the colour of that point is 0.

_{j}Since you are forced to be her art assistant, you will have to answer Vera's questions.

### Input Format

The first line contains two integers, `N`, `Q`, separated by one space (1 ≤ `N`, `Q` ≤ 2 · 10^{5}).

The next `N` lines each contain three space-separated integers, `x _{i}`,

`y`,

_{i}`v`, representing the paint drops of colour

_{i}`v`(1 ≤

_{i}`i`≤

`N`; 1 ≤

`v`≤ 10 000; 1 ≤

_{i}`x`,

_{i}`y`≤ 10

_{i}^{18}).

The next `Q` lines each contain two space-separated integers, `r _{j}` and

`c`, representing the

_{j}`Q`questions about the point (

`r`,

_{j}`c`) (1 ≤

_{j}`j`≤

`Q`; 1 ≤

`r`≤ 10

_{j}^{18}; 1 ≤

`c`≤ 10

_{j}^{18}).

For 5 of the 25 available marks, `N`, `Q` ≤ 2000.

For an additional 5 of the 25 available marks, `y _{i}` = 1 (1 ≤

`i`≤

`N`).

For an additional 5 of the 25 available marks,

`N`,

`Q`≤ 10

^{5}and 1 ≤

`r`,

_{j}`c`≤ 10

_{j}^{9}(1 ≤

`j`≤

`Q`).

### Output Format

The output will be `Q` lines. The `j`-th line (1 ≤ `j` ≤ `Q`) should have one integer, which is the colour of point (`r _{j}`,

`c`).

_{j}### Sample Input

5 6 1 2 1 3 4 2 4 5 3 6 3 4 7 1 5 2 6 7 8 5 9 11 2 10 7 4 5

### Sample Output

1 8 0 6 4 3

### Explanation

Let colour 1, 2, 3, 4, 5 be red, blue, green, orange, purple respectively.

Let `p`, `q` be non-negative integers, then:

- Points (1 +
`p`, 2 + 2`q`) have a red paint drop. - Points (3 + 2
`p`, 4 + 4`q`) have a blue paint drop. - Points (4 + 4
`p`, 5 + 4`q`) have a green paint drop. - Points (6 + 4
`p`, 3 + 2`q`) have a orange paint drop. - Points (7 + 4
`p`, 1 +`q`) have a purple paint drop.

The painting from (0, 0) to (11, 11) is shown below. We can see that:

- (2, 6) has a red paint drop, so it has colour 1.
- (7, 8) has a red, blue and purple paint drop, so it has colour 1 + 2 + 5 = 8.
- (5, 9) has no paint drops, so it has colour 0.
- (11, 2) has a red and purple paint drop, so it has colour 1 + 5 = 6.
- (10, 7) has a orange paint drop, so it has colour 4.
- (4, 5) has a green paint drop, so it has colour 3.

All Submissions

Best Solutions

**Point Value:** 30 (partial)

**Time Limit:** 4.00s

**Memory Limit:** 512M

**Added:** Aug 09, 2017

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...