409606: GYM103643 I Late Midnight Assignment

As a student of U.A., it's important for you to conduct villain threat analysis. So, your sadistic teacher, Midnight, assigned you a painful homework assignment.

She gives you an $$$N$$$ by $$$M$$$ $$$(1\leq N \leq 500,$$$ $$$1 \leq M \leq 500)$$$ city $$$A$$$ describing villains. The danger of the villain in the $$$i$$$th row and $$$j$$$th column is given by $$$A_{ij}$$$ $$$(1 \leq A_{ij} \leq 10^9)$$$.

The threat level of $$$k$$$ villains with danger $$$d_1, d_2, \dots, d_k$$$ is $$$d_1 \mid d_2 \mid \dots \mid d_k$$$, where $$$\mid$$$ is the bitwise OR operator.

Your late (Mid)night assignment is to answer $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$ questions of the form $$$X_1$$$, $$$Y_1$$$, $$$X_2$$$, $$$Y_2$$$ $$$(1 \leq X_1 \leq X_2 \leq N,\, 1 \leq Y_1 \leq Y_2 \leq M)$$$. For each question, find the threat level of the villains in the rectangular region of the city with top left corner at row $$$X_1$$$ and column $$$Y_1$$$ and bottom right corner at row $$$X_2$$$ and column $$$Y_2$$$.

The first line contains $$$3$$$ integers, $$$N$$$, $$$M$$$, $$$Q$$$.

The next $$$N$$$ lines describe the rows of the city. The $$$i$$$th of which contains $$$M$$$ integers, $$$A_{i1}, A_{i2}, \dots, A_{iM}$$$.

The next $$$Q$$$ lines describe the questions. The $$$i$$$th of which contains $$$4$$$ integers, $$$X_{1i}$$$, $$$Y_{1i}$$$, $$$X_{2i}$$$, $$$Y_{2i}$$$.

For each question, print the threat level on a separate line.

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

3
7

For the first question of the example, the threat level is $$$1 \mid 3 = 3$$$.

For the second question of the example, the threat level is $$$1 \mid 2 \mid 3 \mid 4 = 7$$$.

$$$---------------------------------------------$$$

Problem Idea: codicon

Problem Preparation: codicon

Occurrences: Novice 10, Intermediate 5