[Solution] Field Photography Codeforces Solution

F. Field Photography

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 𝑁×10100$N\times {10}^{100}$ with 𝑁$N$ rows and 10100${10}^{100}$ columns. The rows are numbered from 1$1$ to 𝑁$N$ from north to south, the columns are numbered from 1$1$ to 10100${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\le p\le R_i$. So, we can see that there are 𝑅𝑖−𝐿𝑖+1$R_i-L_i+1$ contestants who represent province 𝑖$i$.

Pak Chanek has a variable 𝑍$Z$ that is initially equal to 0$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 𝑍 OR 𝑘$Z\text{ OR }k$, with OR$\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.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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

The first line contains a single integer 𝑁$N$ (1≤𝑁≤105$1\le N\le {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≤𝐿𝑖≤𝑅𝑖≤109$1\le L_i\le R_i\le {10}^9$) describing the positions of the contestants who represent province 𝑖$i$.

The next line contains a single integer 𝑄$Q$ (1≤𝑄≤105$1\le Q\le {10}^5$) — the number of questions.

The 𝑗$j$-th of the next 𝑄$Q$ lines contains a single integer 𝑊𝑗$W_j$ (1≤𝑊𝑗≤109$1\le W_j\le {10}^9$) — the required final value of 𝑍$Z$ for the 𝑗$j$-th question.

Output

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