apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A median in an array with the length of n is an element which occupies position number $$\left\lfloor \frac{n+1}{2} \right\rfloor$$ after we sort the elements in the non-decreasing order (the array elements are numbered starting with 1). A median of an array (2, 6, 1, 2, 3) is the number 2, and a median of array (0, 96, 17, 23) — the number 17.

We define an expression $$\left[\frac{a}{b}\right]$$ as the integer part of dividing number a by number b.

One day Vasya showed Petya an array consisting of n integers and suggested finding the array's median. Petya didn't even look at the array and said that it equals x. Petya is a very honest boy, so he decided to add several numbers to the given array so that the median of the resulting array would be equal to x.

Petya can add any integers from 1 to 105 to the array, including the same numbers. Of course, he can add nothing to the array. If a number is added multiple times, then we should consider it the number of times it occurs. It is not allowed to delete of change initial numbers of the array.

While Petya is busy distracting Vasya, your task is to find the minimum number of elements he will need.

## Input Format
The first input line contains two space-separated integers n and x (1 ≤ n ≤ 500, 1 ≤ x ≤ 105) — the initial array's length and the required median's value. The second line contains n space-separated numbers — the initial array. The elements of the array are integers from 1 to 105. The array elements are not necessarily different.

## Output Format
Print the only integer — the minimum number of elements Petya needs to add to the array so that its median equals x.

## Examples
```input
3 10
10 20 30
```
```output
1
```
-----
```input
3 4
1 2 3
```
```output
4
```

## Note
In the first sample we can add number 9 to array (10, 20, 30). The resulting array (9, 10, 20, 30) will have a median in position $$\left\lfloor \frac{4+1}{2} \right\rfloor = 2$$, that is, 10.

In the second sample you should add numbers 4, 5, 5, 5. The resulting array has median equal to 4.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The warehouse in your shop has n shoe pairs. Each pair is characterized by two integers: its price ci and its size si. We know that on this very day all numbers si are different, that is, there is no more than one pair of each size.

The shop has m customers who came at the same time. The customer number i has di money and the size of his feet equals li. The customer number i can buy the pair number j, if cj ≤ di, and also if li = sj or li = sj - 1; that is, it is necessary that he has enough money to pay for the shoes. It is also necessary that the size of his feet equals to or is less by 1 than the size of the shoes he chooses.

Your task is to sell some customers pairs of shoes (a pair per person) so as to maximize the sum of the sold pairs cj that is, the profit. It is guaranteed that each customer buys no more than one pair and each pair will be bought by no more than one customer.

## Input Format
The first input line contains the only integer n (1 ≤ n ≤ 105) — the number of shoe pairs in the warehouse. Then n lines contain the descriptions of pairs of shoes as two integers ci and si (1 ≤ ci, si ≤ 109), the numbers are separated by a space. It is guaranteed that all numbers si are different.

The next line contains an integer m (1 ≤ m ≤ 105) — the number of customers in the shop. Next m lines contain the customers' descriptions as two integers di and li (1 ≤ di, li ≤ 109), the numbers are separated by a space.

## Output Format
In the first line print the only integer — the maximum profit you can get from selling shoes. In the second line print an integer k — the number of shoe pairs you will sell. In the following k lines print the descriptions of the sold pairs — two space-separated integers where the first number is the customer's number and the second number is the number of the shoes the customer will buy.

You can print pairs of numbers "the customer's number and the shoes' number" in any order, the customers and the pairs of shoes are numbered starting from 1 in the order in which they are given in the input. If there are several optimal answers, you are allowed to print any of them.

Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use the cin, cout streams or the %I64d specificator instead.

## Examples
```input
3
10 1
30 2
20 3
2
20 1
20 2
```
```output
30
2
2 3
1 1
```
-----
```input
3
10 4
20 5
30 6
2
70 4
50 5
```
```output
50
2
2 3
1 2
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a tetrahedron. Let's mark its vertices with letters A, B, C and D correspondingly.

An ant is standing in the vertex D of the tetrahedron. The ant is quite active and he wouldn't stay idle. At each moment of time he makes a step from one vertex to another one along some edge of the tetrahedron. The ant just can't stand on one place.

You do not have to do much to solve the problem: your task is to count the number of ways in which the ant can go from the initial vertex D to itself in exactly n steps. In other words, you are asked to find out the number of different cyclic paths with the length of n from vertex D to itself. As the number can be quite large, you should print it modulo 1000000007 (109 + 7).

## Input Format
The first line contains the only integer n (1 ≤ n ≤ 107) — the required length of the cyclic path.

## Output Format
Print the only integer — the required number of ways modulo 1000000007 (109 + 7).

## Examples
```input
2
```
```output
3
```
-----
```input
4
```
```output
21
```

## Note
The required paths in the first sample are:

- D - A - D
- D - B - D
- D - C - D

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a grid with $$$n$$$ rows and $$$m$$$ columns. Rows and columns are numbered from $$$1$$$ to $$$n$$$, and from $$$1$$$ to $$$m$$$. The intersection of the $$$a$$$-th row and $$$b$$$-th column is denoted by $$$(a, b)$$$.

Initially, you are standing in the top left corner $$$(1, 1)$$$. Your goal is to reach the bottom right corner $$$(n, m)$$$.

You can move in four directions from $$$(a, b)$$$: up to $$$(a-1, b)$$$, down to $$$(a+1, b)$$$, left to $$$(a, b-1)$$$ or right to $$$(a, b+1)$$$.

You cannot move in the same direction in two consecutive moves, and you cannot leave the grid. What is the minimum number of moves to reach $$$(n, m)$$$?

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of the test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — the size of the grid.

## Output Format
For each test case, print a single integer: $$$-1$$$ if it is impossible to reach $$$(n, m)$$$ under the given conditions, otherwise the minimum number of moves.

## Examples
```input
6
1 1
2 1
1 3
4 2
4 6
10 5
```
```output
0
1
-1
6
10
17
```

## Note
Test case $$$1$$$: $$$n=1$$$, $$$m=1$$$, and initially you are standing in $$$(1, 1)$$$ so $$$0$$$ move is required to reach $$$(n, m) = (1, 1)$$$.

Test case $$$2$$$: you should go down to reach $$$(2, 1)$$$.

Test case $$$3$$$: it is impossible to reach $$$(1, 3)$$$ without moving right two consecutive times, or without leaving the grid.

Test case $$$4$$$: an optimal moving sequence could be: $$$(1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2) \to (4, 2)$$$. It can be proved that this is the optimal solution. So the answer is $$$6$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.5 seconds
Memory limit: 256.0 MB

# Problem
$$$m$$$ chairs are arranged in a circle sequentially. The chairs are numbered from $$$0$$$ to $$$m-1$$$. $$$n$$$ people want to sit in these chairs. The $$$i$$$-th of them wants at least $$$a[i]$$$ empty chairs both on his right and left side.

More formally, if the $$$i$$$-th person sits in the $$$j$$$-th chair, then no one else should sit in the following chairs: $$$(j-a[i]) \bmod m$$$, $$$(j-a[i]+1) \bmod m$$$, ... $$$(j+a[i]-1) \bmod m$$$, $$$(j+a[i]) \bmod m$$$.

Decide if it is possible to sit down for all of them, under the given limitations.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^9$$$) — the number of people and the number of chairs.

The next line contains $$$n$$$ integers, $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the minimum number of empty chairs, on both sides of the $$$i$$$-th person.

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$10^5$$$.

## Output Format
For each test case print "YES" (without quotes) if it is possible for everyone to sit down and fulfil the restrictions, and "NO" (without quotes) otherwise.

You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).

## Examples
```input
6
3 2
1 1 1
2 4
1 1
2 5
2 1
3 8
1 2 1
4 12
1 2 1 3
4 19
1 2 1 3
```
```output
NO
YES
NO
YES
NO
YES
```

## Note
Test case $$$1$$$: $$$n>m$$$, so they can not sit down.

Test case $$$2$$$: the first person can sit $$$2$$$-nd and the second person can sit in the $$$0$$$-th chair. Both of them want at least $$$1$$$ empty chair on both sides, chairs $$$1$$$ and $$$3$$$ are free, so this is a good solution.

Test case $$$3$$$: if the second person sits down somewhere, he needs $$$2$$$ empty chairs, both on his right and on his left side, so it is impossible to find a place for the first person, because there are only $$$5$$$ chairs.

Test case $$$4$$$: they can sit in the $$$1$$$-st, $$$4$$$-th, $$$7$$$-th chairs respectively.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
One day Prof. Slim decided to leave the kingdom of the GUC to join the kingdom of the GIU. He was given an easy online assessment to solve before joining the GIU. Citizens of the GUC were happy sad to see the prof leaving, so they decided to hack into the system and change the online assessment into a harder one so that he stays at the GUC. After a long argument, they decided to change it into the following problem.

Given an array of $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$, where $$$a_{i} \neq 0$$$, check if you can make this array sorted by using the following operation any number of times (possibly zero). An array is sorted if its elements are arranged in a non-decreasing order.

1. select two indices $$$i$$$ and $$$j$$$ ($$$1 \le i,j \le n$$$) such that $$$a_i$$$ and $$$a_j$$$ have different signs. In other words, one must be positive and one must be negative.
2. swap the signs of $$$a_{i}$$$ and $$$a_{j}$$$. For example if you select $$$a_i=3$$$ and $$$a_j=-2$$$, then they will change to $$$a_i=-3$$$ and $$$a_j=2$$$.

Prof. Slim saw that the problem is still too easy and isn't worth his time, so he decided to give it to you to solve.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — the length of the array $$$a$$$.

The next line contain $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_{i} \le 10^9$$$, $$$a_{i} \neq 0$$$) separated by spaces describing elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, print "YES" if the array can be sorted in the non-decreasing order, otherwise print "NO". You can print each letter in any case (upper or lower).

## Examples
```input
4
7
7 3 2 -11 -13 -17 -23
6
4 10 25 47 71 96
6
71 -35 7 -4 -11 -25
6
-45 9 -48 -67 -55 7
```
```output
NO
YES
YES
NO
```

## Note
In the first test case, there is no way to make the array sorted using the operation any number of times.

In the second test case, the array is already sorted.

In the third test case, we can swap the sign of the $$$1$$$-st element with the sign of the $$$5$$$-th element, and the sign of the $$$3$$$-rd element with the sign of the $$$6$$$-th element, this way the array will be sorted.

In the fourth test case, there is no way to make the array sorted using the operation any number of times.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Sehr Sus is an infinite hexagonal grid as pictured below, controlled by MennaFadali, ZerooCool and Hosssam.

They love equilateral triangles and want to create $$$n$$$ equilateral triangles on the grid by adding some straight lines. The triangles must all be empty from the inside (in other words, no straight line or hexagon edge should pass through any of the triangles).

You are allowed to add straight lines parallel to the edges of the hexagons. Given $$$n$$$, what is the minimum number of lines you need to add to create at least $$$n$$$ equilateral triangles as described?

Adding two red lines results in two new yellow equilateral triangles.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{9}$$$) — the required number of equilateral triangles.

## Output Format
For each test case, print the minimum number of lines needed to have $$$n$$$ or more equilateral triangles.

## Examples
```input
4
1
2
3
4567
```
```output
2
2
3
83
```

## Note
In the first and second test cases only 2 lines are needed. After adding the first line, no equilateral triangles will be created no matter where it is added. But after adding the second line, two more triangles will be created at once.

In the third test case, the minimum needed is 3 lines as shown below.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
During their training for the ICPC competitions, team "Jee You See" stumbled upon a very basic counting problem. After many "Wrong answer" verdicts, they finally decided to give up and destroy turn-off the PC. Now they want your help in up-solving the problem.

You are given 4 integers $$$n$$$, $$$l$$$, $$$r$$$, and $$$z$$$. Count the number of arrays $$$a$$$ of length $$$n$$$ containing non-negative integers such that:

- $$$l\le a_1+a_2+\ldots+a_n\le r$$$, and
- $$$a_1\oplus a_2 \oplus \ldots\oplus a_n=z$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

Since the answer can be large, print it modulo $$$10^9+7$$$.

## Input Format
The only line contains four integers $$$n$$$, $$$l$$$, $$$r$$$, $$$z$$$ ($$$1 \le n \le 1000$$$, $$$1\le l\le r\le 10^{18}$$$, $$$1\le z\le 10^{18}$$$).

## Output Format
Print the number of arrays $$$a$$$ satisfying all requirements modulo $$$10^9+7$$$.

## Examples
```input
3 1 5 1
```
```output
13
```
-----
```input
4 1 3 2
```
```output
4
```
-----
```input
2 1 100000 15629
```
```output
49152
```
-----
```input
100 56 89 66
```
```output
981727503
```

## Note
The following arrays satisfy the conditions for the first sample:

- $$$[1, 0, 0]$$$;
- $$$[0, 1, 0]$$$;
- $$$[3, 2, 0]$$$;
- $$$[2, 3, 0]$$$;
- $$$[0, 0, 1]$$$;
- $$$[1, 1, 1]$$$;
- $$$[2, 2, 1]$$$;
- $$$[3, 0, 2]$$$;
- $$$[2, 1, 2]$$$;
- $$$[1, 2, 2]$$$;
- $$$[0, 3, 2]$$$;
- $$$[2, 0, 3]$$$;
- $$$[0, 2, 3]$$$.

The following arrays satisfy the conditions for the second sample:

- $$$[2, 0, 0, 0]$$$;
- $$$[0, 2, 0, 0]$$$;
- $$$[0, 0, 2, 0]$$$;
- $$$[0, 0, 0, 2]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given two integers $$$x$$$ and $$$y$$$. You want to choose two strictly positive (greater than zero) integers $$$a$$$ and $$$b$$$, and then apply the following operation to $$$x$$$ exactly $$$a$$$ times: replace $$$x$$$ with $$$b \cdot x$$$.

You want to find two positive integers $$$a$$$ and $$$b$$$ such that $$$x$$$ becomes equal to $$$y$$$ after this process. If there are multiple possible pairs, you can choose any of them. If there is no such pair, report it.

For example:

- if $$$x = 3$$$ and $$$y = 75$$$, you may choose $$$a = 2$$$ and $$$b = 5$$$, so that $$$x$$$ becomes equal to $$$3 \cdot 5 \cdot 5 = 75$$$;
- if $$$x = 100$$$ and $$$y = 100$$$, you may choose $$$a = 3$$$ and $$$b = 1$$$, so that $$$x$$$ becomes equal to $$$100 \cdot 1 \cdot 1 \cdot 1 = 100$$$;
- if $$$x = 42$$$ and $$$y = 13$$$, there is no answer since you cannot decrease $$$x$$$ with the given operations.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of one line containing two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 100$$$).

## Output Format
If it is possible to choose a pair of positive integers $$$a$$$ and $$$b$$$ so that $$$x$$$ becomes $$$y$$$ after the aforementioned process, print these two integers. The integers you print should be not less than $$$1$$$ and not greater than $$$10^9$$$ (it can be shown that if the answer exists, there is a pair of integers $$$a$$$ and $$$b$$$ meeting these constraints). If there are multiple such pairs, print any of them.

If it is impossible to choose a pair of integers $$$a$$$ and $$$b$$$ so that $$$x$$$ becomes $$$y$$$, print the integer $$$0$$$ twice.

## Examples
```input
3
3 75
100 100
42 13
```
```output
2 5
3 1
0 0
```

Now solve the problem and return the code.