Baby Ehab likes $x o r$, but KEE likes geometry. That's why this next problem is a combination of both!
Given two lines having an integer power-of-2 slope each $s_1$ and $s_2$, and passing through the point $(0, 0)$; along with an interval on the $x -a x i s$, find the value of the following summation:
Where $y_{1 , i}$, $y_{2 , i}$ are the $y -c o o r d i n a t e s$ of the first and second line respectively for the $i_{t h}$ integer $x -c o o r d i n a t e$ in the interval provided.
The first line contains an integer $T$ $(1 <= T <= 1000)$, the number of testcases.
Each testcase consists of one line containing $4$ integers $s_1,$ $s_2,$ $x_l,$ $x_r$ $(1 <= s_1,$ $s_2 <= 2^(20),$ $1 <= x_1,$ $x_r <= 10^(12))$ where $s_1,$ $s_2$ are the slopes of the lines and $x_l,$ $x_r$ are the boundaries of the interval on the x-axis. It's guaranteed that $s_1,$ $s_2$ are an integer powers-of-2 (i.e. $s = 2^k$ for some non-negative integer $k$).
For each testcase, output one line containing the sum of the $x o r$ of the y-coordinates on both lines in the given interval. To avoid large numbers, output the sum modulo $1000000007$. The sum is calculated under the modulo; however, the xor at each individual sum is not.
The first test:
The squares denotes the xor at each point. $(1 plus.circle 2) + (2 plus.circle 4) + (3 plus.circle 6) + (4 plus.circle 8) = 3 + 6 + 5 + 12 = 26$.
It's recommended to use 64-bit integer types to avoid overflow.
## Input
The first line contains an integer $T$ $(1 <= T <= 1000)$, the number of testcases.Each testcase consists of one line containing $4$ integers $s_1,$ $s_2,$ $x_l,$ $x_r$ $(1 <= s_1,$ $s_2 <= 2^(20),$ $1 <= x_1,$ $x_r <= 10^(12))$ where $s_1,$ $s_2$ are the slopes of the lines and $x_l,$ $x_r$ are the boundaries of the interval on the x-axis. It's guaranteed that $s_1,$ $s_2$ are an integer powers-of-2 (i.e. $s = 2^k$ for some non-negative integer $k$).
## Output
For each testcase, output one line containing the sum of the $x o r$ of the y-coordinates on both lines in the given interval. To avoid large numbers, output the sum modulo $1000000007$. The sum is calculated under the modulo; however, the xor at each individual sum is not.
[samples]
## Note
The first test: The squares denotes the xor at each point. $(1 plus.circle 2) + (2 plus.circle 4) + (3 plus.circle 6) + (4 plus.circle 8) = 3 + 6 + 5 + 12 = 26$.It's recommended to use 64-bit integer types to avoid overflow.
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 15 $.
Let $ G \in \{ \text{.}, \text{*}, \text{\#}, \text{@}, \text{s} \}^{n \times m} $ be a grid representing the map, where:
- $ \text{.} $: empty ground,
- $ \text{*} $: obstacle,
- $ \text{\#} $: box,
- $ \text{@} $: target,
- $ \text{s} $: agent (player).
Let $ B = \{ b_1, b_2 \} \subseteq \{1, \dots, n\} \times \{1, \dots, m\} $ be the set of initial box positions.
Let $ T = \{ t_1, t_2 \} \subseteq \{1, \dots, n\} \times \{1, \dots, m\} $ be the set of target positions.
Let $ p_0 \in \{1, \dots, n\} \times \{1, \dots, m\} $ be the initial position of the agent.
**Constraints**
1. $ |B| = |T| = 2 $, and $ B \cap T = \emptyset $, $ p_0 \notin B \cup T $.
2. All positions in $ B \cup T \cup \{p_0\} $ are distinct and lie on empty ground (i.e., not obstacles).
3. The agent can move in 4 directions (up, down, left, right) if the target cell is within bounds and not an obstacle.
4. The agent can push a box if:
- The cell behind the box (in the direction of push) is within bounds,
- Is not an obstacle,
- Does not contain another box.
5. A box is considered "placed" if it occupies any target cell.
6. Boxes may be moved off targets; targets are not consumed.
**Objective**
Find the minimum number of agent moves required to have both boxes simultaneously occupy the two target positions (in any assignment), or return $-1$ if impossible.
Formally, find:
$$
\min \left\{ \text{steps} \mid \exists \text{ sequence of moves leading to } \{ b_1', b_2' \} = T \right\}
$$
where $ b_1', b_2' $ are the final positions of the two boxes, and the agent’s path respects all movement and pushing rules.