Field Photography
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2100
Tags: bitmasks, data structures, sortings

Pak Chanek is traveling to Manado. It turns out that OSN (Indonesian National Scientific Olympiad) 2019 is being held. The contestants of OSN 2019 are currently lining up in a field to be photographed. The field is shaped like a grid of size $$$N \times 10^{100}$$$ with $$$N$$$ rows and $$$10^{100}$$$ columns. The rows are numbered from $$$1$$$ to $$$N$$$ from north to south, the columns are numbered from $$$1$$$ to $$$10^{100}$$$ from west to east. The tile in row $$$r$$$ and column $$$c$$$ is denoted as $$$(r,c)$$$.

There are $$$N$$$ provinces that participate in OSN 2019. Initially, each contestant who represents province $$$i$$$ stands in tile $$$(i, p)$$$ for each $$$p$$$ satisfying $$$L_i \leq p \leq R_i$$$. So, we can see that there are $$$R_i-L_i+1$$$ contestants who represent province $$$i$$$.

Pak Chanek has a variable $$$Z$$$ that is initially equal to $$$0$$$. In one operation, Pak Chanek can choose a row $$$i$$$ and a positive integer $$$k$$$. Then, Pak Chanek will do one of the two following possibilities:

- Move all contestants in row $$$i$$$ exactly $$$k$$$ tiles to the west. In other words, a contestant who is in $$$(i, p)$$$ is moved to $$$(i, p-k)$$$.
- Move all contestants in row $$$i$$$ exactly $$$k$$$ tiles to the east. In other words, a contestant who is in $$$(i, p)$$$ is moved to $$$(i, p+k)$$$.

After each operation, the value of $$$Z$$$ will change into $$$Z \text{ OR } k$$$, with $$$\text{OR}$$$ being the bitwise OR operation. Note that Pak Chanek can do operations to the same row more than once. Also note that Pak Chanek is not allowed to move contestants out of the grid.

There are $$$Q$$$ questions. For the $$$j$$$-th question, you are given a positive integer $$$W_j$$$, Pak Chanek must do zero or more operations so that the final value of $$$Z$$$ is exactly $$$W_j$$$. Define $$$M$$$ as the biggest number such that after all operations, there is at least one column that contains exactly $$$M$$$ contestants. For each question, you must find the biggest possible $$$M$$$ for all sequences of operations that can be done by Pak Chanek. Note that the operations done by Pak Chanek for one question do not carry over to other questions.

Input format:
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$) — the number of rows in the grid and also the number of provinces that participate in OSN 2019.

The $$$i$$$-th of the next $$$N$$$ lines contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq 10^9$$$) describing the positions of the contestants who represent province $$$i$$$.

The next line contains a single integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$) — the number of questions.

The $$$j$$$-th of the next $$$Q$$$ lines contains a single integer $$$W_j$$$ ($$$1 \leq W_j \leq 10^9$$$) — the required final value of $$$Z$$$ for the $$$j$$$-th question.

Output format:
Output $$$Q$$$ lines, with the $$$j$$$-th line containing an integer that is the answer to the $$$j$$$-th question.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the $$$1$$$-st question, Pak Chanek can do the following operations to get $$$M=2$$$:

- Move all contestants in row $$$2$$$ to the east by $$$4$$$ tiles. $$$Z$$$ changes into $$$0 \text{ OR } 4 = 4$$$.
- Move all contestants in row $$$1$$$ to the east by $$$12$$$ tiles. $$$Z$$$ changes into $$$4 \text{ OR } 12 = 12$$$.

Now, columns $$$14$$$ and $$$15$$$ each contains exactly $$$2$$$ contestants.

For the $$$2$$$-nd question, Pak Chanek can do the following operations to get $$$M=3$$$:

- Move all contestants in row $$$3$$$ to the east by $$$4$$$ tiles. $$$Z$$$ changes into $$$0 \text{ OR } 4 = 4$$$.
- Move all contestants in row $$$3$$$ to the west by $$$1$$$ tiles. $$$Z$$$ changes into $$$4 \text{ OR } 1 = 5$$$.
- Move all contestants in row $$$1$$$ to the east by $$$5$$$ tiles. $$$Z$$$ changes into $$$5 \text{ OR } 5 = 5$$$.
- Move all contestants in row $$$1$$$ to the east by $$$5$$$ tiles. $$$Z$$$ changes into $$$5 \text{ OR } 5 = 5$$$.

Now, column $$$11$$$ contains exactly $$$3$$$ contestants.

The following is an illustration of the example operations for the $$$2$$$-nd question.

Example input:
3
1 5
10 11
8 8
2
12
5

Example output:
2
3

Editorial:
Let's consider some value of $$$W_j$$$. Let $$$b$$$ be the LSB (Least Significant Bit) of $$$W_j$$$. Which means $$$b$$$ is the minimum number such that the bit in index $$$b$$$ in the binary representation of $$$W_j$$$ is active. Note: the bits are indexed from $$$0$$$ from the right.
For a sequence of operations, define $$$\text{dis}(i)$$$ as how many tiles to the east the final positions of the contestants in row $$$i$$$ compared to their initial position. Specifically, if their final positions are more to the west, then $$$\text{dis}(i)$$$ is negative.
Notice that each move we make must be a distance that is a multiple of $$$2^b$$$. Because if we move a distance that is not a multiple of $$$2^b$$$, at least one of the bits with indices smaller than $$$b$$$ will be activated, which we do not want. This means $$$\text{dis}(i)$$$ must be a multiple of $$$2^b$$$.
However, we can make each $$$\text{dis}(i)$$$ to be any integer that is a multiple of $$$2^b$$$ while making $$$Z = W_j$$$ by doing the following strategy:
1. Only do moves with distances of exactly $$$2^b$$$ to move the contestants in each row to their final positions.
2. Move one row with a distance of $$$W_j$$$ to the east, then to the west.
Using the knowledge above, we can see that for each row $$$i$$$, there are three cases:
• If $$$R_i-L_i+1 \geq 2^b$$$, then each column can be occupied.
• Else, if $$$(L_i \mod 2^b) \leq (R_i \mod 2^b)$$$, then only each column $$$c$$$ such that $$$(L_i \mod 2^b) \leq (c \mod 2^b) \leq (R_i \mod 2^b)$$$ can be occupied.
• Else, then only each column $$$c$$$ such that $$$(L_i \mod 2^b) \leq (c \mod 2^b)$$$ or $$$(c \mod 2^b) \leq (R_i \mod 2^b)$$$ can be occupied.
We can see that each row has at most two subsegments of the segment $$$[0, 2^b-1]$$$ denoting the occupiable columns modulo $$$2^b$$$. Now we just need to find the position that intersects the most subsegments. To solve this, we can use line sweep.
To handle the $$$Q$$$ queries, notice that the number of possible distinct values for the LSB of $$$W_j$$$ are only $$$\lfloor \log_2 10^9 \rfloor + 1 = 30$$$. So we can precompute the answer for each of the $$$30$$$ possible LSB, then answer the queries using the precomputed answers.
Time complexity: $$$O(N\log N \log \max(W) + Q \log \max(W))$$$