vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are $n$ robbers at coordinates $(a_1, b_1)$, $(a_2, b_2)$, ..., $(a_n, b_n)$ and $m$ searchlight at coordinates $(c_1, d_1)$, $(c_2, d_2)$, ..., $(c_m, d_m)$. 

In one move you can move each robber to the right (increase $a_i$ of each robber by one) or move each robber up (increase $b_i$ of each robber by one). Note that you should either increase all $a_i$ or all $b_i$, you can't increase $a_i$ for some points and $b_i$ for some other points.

Searchlight $j$ can see a robber $i$ if $a_i \leq c_j$ and $b_i \leq d_j$. 

A configuration of robbers is safe if no searchlight can see a robber (i.e. if there is no pair $i,j$ such that searchlight $j$ can see a robber $i$).

What is the minimum number of moves you need to perform to reach a safe configuration?


-----Input-----

The first line of input contains two integers $n$ and $m$ ($1 \leq n, m \leq 2000$): the number of robbers and the number of searchlight.

Each of the next $n$ lines contains two integers $a_i$, $b_i$ ($0 \leq a_i, b_i \leq 10^6$), coordinates of robbers.

Each of the next $m$ lines contains two integers $c_i$, $d_i$ ($0 \leq c_i, d_i \leq 10^6$), coordinates of searchlights.


-----Output-----

Print one integer: the minimum number of moves you need to perform to reach a safe configuration.


-----Examples-----
Input
1 1
0 0
2 3

Output
3

Input
2 3
1 6
6 1
10 1
1 10
7 7

Output
4

Input
1 2
0 0
0 0
0 0

Output
1

Input
7 3
0 8
3 8
2 7
0 10
5 5
7 0
3 5
6 6
3 11
11 5

Output
6



-----Note-----

In the first test, you can move each robber to the right three times. After that there will be one robber in the coordinates $(3, 0)$.

The configuration of the robbers is safe, because the only searchlight can't see the robber, because it is in the coordinates $(2, 3)$ and $3 > 2$.

In the second test, you can move each robber to the right two times and two times up. After that robbers will be in the coordinates $(3, 8)$, $(8, 3)$.

It's easy the see that the configuration of the robbers is safe.

It can be proved that you can't reach a safe configuration using no more than $3$ moves.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A multinational company is asking you to help them genetically modify an apple. In order for the apples to grow faster, to get more of them, to make them bigger and make them look nicer and more symmetrical, the apple’s DNA requires an insertion of a certain swine gene.

The apple’s DNA is represented by a series of characters from the set $\{ A, C, G, T\} $. The required swine gene is also comprised of charaters from this set. The apple’s DNA should be injected with some characters into some places, so that the resulting sequence contains a swine gene somewhere (in successive locations). To make things a bit more complicated, inserting each of the characters $A, C, G, T$ has its own cost.

Help this multinational company in achieving their goal with the lowest possible total cost. As a reward, you get a ton of their apples.

-----Input-----
The first line of input contains a sequence of $N$ ($1 \le N \le 10000$) characters which represent the apple’s DNA.

The second line of input contains a sequence of $M$ ($1 \le M \le 5000$) characters which represent the swine gene that we want to insert into the apple’s DNA.

Both the sequences are comprised only of characters from the set $\{ A, C, G, T\} $.

The third line of input contains four integers from the interval $[0, 1000]$: the cost of inserting one character $A, C, G, T$, in that order.

-----Output-----
The first and only line of output must contain the minimal total cost.

-----Examples-----
Sample Input 1:
GTA
CAT
5 7 1 3
Sample Output 1:
10

Sample Input 2:
TATA
CACA
3 0 3 0
Sample Output 2:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi loves numbers divisible by 2.
You are given a positive integer N. Among the integers between 1 and N (inclusive), find the one that can be divisible by 2 for the most number of times. The solution is always unique.
Here, the number of times an integer can be divisible by 2, is how many times the integer can be divided by 2 without remainder.
For example,
 - 6 can be divided by 2 once: 6 -> 3.
 - 8 can be divided by 2 three times: 8 -> 4 -> 2 -> 1.
 - 3 can be divided by 2 zero times.

-----Constraints-----
 - 1 ≤ N ≤ 100

-----Input-----
Input is given from Standard Input in the following format:
N

-----Output-----
Print the answer.

-----Sample Input-----
7

-----Sample Output-----
4

4 can be divided by 2 twice, which is the most number of times among 1, 2, ..., 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Xenny reverse-engineered all the binaries released by the International Security Agency (ISA)
during summer vacation just to pass time. As a reward, the ISA gave him infinite ByteCoins.

Out of sheer boredom and a sense of purposelessness in life, Xenny decided to arrange the Coins on a 2-Dimensional Euclidean Plane.
The boredom was so strong that he arranged these coins in a specific pattern, as opposed to the usual, monotonous way of storing coins in a Piggy Bank.

On each integer co-ordinate (x, y) where x ≥ 0 and y ≥ 0, a single coin was placed. And each coin was assigned a rank. The following pattern was followed in the arrangement:

Let's denote the co-ordinates of the k^{th} coin by (x_{k}, y_{k}) and its rank by R_{k}.

For any 2 coins i, j:

if (x_{i} + y_{i}) < (x_{j} + y_{j}) or ( (x_{i} + y_{i}) == (x_{j} + y_{j}) and x_{i} < x_{j})

then R_{i} < R_{j}. We sort all the coins by this comparison.

The index of the coin (C) in this sorted list of coins (1-indexed) is its rank.

Each query is as follows: Given (U, V). Among the coins that are lying on or inside the rectangle with
its diagonal end-points being (0, 0) and (U, V),
which is the coin that has the maximum rank?

------ Input ------ 

The first line contains an integer, T - the number of testcases.

Each testcase contains 2 space-separated integers: U, V.

------ Output ------ 

For each testcase, print the rank of the maximum ranked coin, on a new line.

------ Constraints ------ 

Subtask 1: (40 points)
$1 ≤ T ≤ 100$
$1 ≤ U, V ≤ 100$
  
Subtask 2: (60 points)
$1 ≤ T ≤ 100$
$1 ≤ U, V ≤ 10^{9}$
  
----- Sample Input 1 ------ 
1
1 2
----- Sample Output 1 ------ 
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice is a queen bee living in Beeland (a honeycomb structure described by $R$, the number of cells of the side of honeycomb). The cells in Beeland are numbered from $1$ to $R^3 - (R-1)^3$ in row major order. For example for $R = 3$, the Beeland that Alice lives in looks like this:

Now Alice lives in a house that occupies $K$ adjacent cells in Beeland. You are Bob, the knight bee. You need to protect Alice’s house, but first you need to know the length of its outer perimeter (the number of outermost sides of Alice’s house). The illustration below shows the visualizations of Sample Inputs/Outputs $2$ and $3$.

-----Input-----
The first line of input consists of two integers: $R$ and $K$. ($1 \leq R \leq 50$, $1 \leq K \leq R^3 - (R-1)^3$). The second line contains $K$ unique integers that describe the indices of Alice’s house, where each integer is in the range $[1,R^3-(R-1)^3]$.

-----Output-----
Print an integer in one line: The perimeter of Alice’s house.

-----Examples-----
Sample Input 1:
3 1
7
Sample Output 1:
6

Sample Input 2:
3 6
5 6 7 11 15 18
Sample Output 2:
24

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Problem

Gaccho is enthusiastic about the popular game Zombie Hunter. In this game, there are 5 types of armor dedicated to the head, torso, arms, hips, and legs, and the player character (PC) operated by Gaccho can have up to 1 armor for each part of the body. Can be equipped.
In addition, the weight and defense power are set for each armor, and when the total weight of the armor equipped on the PC is A or more and B or less, and the total defense power is also A or more and B or less. The PC can activate the skill.

Gaccho has N pieces of armor. Find out if your PC can activate your skills by choosing the right armor to equip.

Constraints

The input satisfies the following conditions.

* 1 ≤ N ≤ 500
* 1 ≤ A ≤ B ≤ 1012
* 1 ≤ ti ≤ 5
* −1012 ≤ xi, yi ≤ 1012

Input

The input is given in the following format.


N A B
t1 x1 y1
t2 x2 y2
...
tN xN yN


All inputs are given as integers.
The first line gives you the number of armor N you own and the two integers A and B used to activate the skill.
Information on N pieces of armor is given to the N lines that continue from the second line. ti, xi, yi represent the type, weight, and defense of the i-th armor, respectively.

Armor type The ti value indicates that 1 is head armor, 2 is torso armor, 3 is arm armor, 4 is waist armor, and 5 is foot armor.

Output

Output "Yes" if the skill can be activated, and "No" if it cannot be activated on one line.

Examples

Input

7 10 11
1 1 0
1 0 1
2 2 2
3 3 5
4 1 3
5 1 3
5 5 -1


Output

Yes


Input

7 10 10
1 1 0
1 0 1
2 2 2
3 3 5
4 1 3
5 1 3
5 5 -1


Output

No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Mice

Time Limit: 0 seconds

Memory Limit: 256 megabytes

Problem Description:
Modern researches has shown that a flock of hungry mice searching for a piece of cheese acts as follows: if there are several pieces of cheese then each mouse chooses the closest one. After that all mice start moving towards the chosen piece of cheese. When a mouse or several mice achieve the destination point and there is still a piece of cheese in it, they eat it and become well-fed. Each mice that reaches this point after that remains hungry. Moving speeds of all mice are equal.

If there are several ways to choose closest pieces then mice will choose it in a way that would minimize the number of hungry mice. To check this theory scientists decided to conduct an experiment. They located *N* mice and *M* pieces of cheese on a cartesian plane where all mice are located on the line *y*<==<=*Y*0 and all pieces of cheese — on another line *y*<==<=*Y*1. To check the results of the experiment the scientists need a program which simulates the behavior of a flock of hungry mice.

Write a program that computes the minimal number of mice which will remain hungry, i.e. without cheese.

Input Specification:
The first line of the input contains four integer numbers *N* (1<=≤<=*N*<=≤<=105), *M* (0<=≤<=*M*<=≤<=105), *Y*0 (0<=≤<=*Y*0<=≤<=107), *Y*1 (0<=≤<=*Y*1<=≤<=107, *Y*0<=≠<=*Y*1). The second line contains a strictly increasing sequence of *N* numbers — *x* coordinates of mice. Third line contains a strictly increasing sequence of *M* numbers — *x* coordinates of cheese. All coordinates are integers and do not exceed 107 by absolute value.

Output Specification:
The only line of output should contain one number — the minimal number of mice which will remain without cheese.

Demo Input:
['3 2 0 2\n0 1 3\n2 5\n']

Demo Output:
['1\n']

Note:
All the three mice will choose the first piece of cheese. Second and third mice will eat this piece. The first one will remain hungry, because it was running towards the same piece, but it was late. The second piece of cheese will remain uneaten.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a grid with H rows and W columns of squares. Snuke is painting these squares in colors 1, 2, ..., N. Here, the following conditions should be satisfied:

* For each i (1 ≤ i ≤ N), there are exactly a_i squares painted in Color i. Here, a_1 + a_2 + ... + a_N = H W.
* For each i (1 ≤ i ≤ N), the squares painted in Color i are 4-connected. That is, every square painted in Color i can be reached from every square painted in Color i by repeatedly traveling to a horizontally or vertically adjacent square painted in Color i.



Find a way to paint the squares so that the conditions are satisfied. It can be shown that a solution always exists.

Constraints

* 1 ≤ H, W ≤ 100
* 1 ≤ N ≤ H W
* a_i ≥ 1
* a_1 + a_2 + ... + a_N = H W

Input

Input is given from Standard Input in the following format:


H W
N
a_1 a_2 ... a_N


Output

Print one way to paint the squares that satisfies the conditions. Output in the following format:


c_{1 1} ... c_{1 W}
:
c_{H 1} ... c_{H W}


Here, c_{i j} is the color of the square at the i-th row from the top and j-th column from the left.

Examples

Input

2 2
3
2 1 1


Output

1 1
2 3


Input

3 5
5
1 2 3 4 5


Output

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


Input

1 1
1
1


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Panda has become a scientist recently. In his laboratory, there are infinite number of chambers where a chamber number K is connected to a chamber number K-1.  

The numbering of chambers start from 0. Initially, X number of particles are present in the chamber number 0. The number of particles present in chamber K is K times the number of particles present in chamber K-1.   You are supposed to help Panda in finding out the number of particles in a given chamber number N.  

Note: The number of particles in chamber K cannot be calculated until the number of particles in chamber K-1 are calculated.  

Input Format:

The first line will contain the integer T, the number of test cases. Each test case consists of two space separated integers N and X.   

Output Format:

For each test case, output the answer to Panda's query. Since the output can be very large, output the answer modulo 10^6+3.  

Constraints:

1 ≤ T ≤ 10^5

Subtask 1: (20 points)
1 ≤ N, X ≤ 10^5

Subtask 2: (80 points)
1 ≤ N, X ≤ 10^18SAMPLE INPUT
2
1 3
2 1

SAMPLE OUTPUT
3
2

Explanation

Case 1: For first test case, initially there were 3 particles. 
In Chamber K=1, the number of particles became 1*3 = 3.

Case 2: Initially, there is only 1 particle.
In Chamber K=1, the number of particle became 1*1 = 1.
In Chamber K=2, the number of particle became 2*1 = 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N cities on a number line. The i-th city is located at coordinate x_i.
Your objective is to visit all these cities at least once.
In order to do so, you will first set a positive integer D.
Then, you will depart from coordinate X and perform Move 1 and Move 2 below, as many times as you like:
 - Move 1: travel from coordinate y to coordinate y + D.
 - Move 2: travel from coordinate y to coordinate y - D.
Find the maximum value of D that enables you to visit all the cities.
Here, to visit a city is to travel to the coordinate where that city is located.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 10^5
 - 1 \leq X \leq 10^9
 - 1 \leq x_i \leq 10^9
 - x_i are all different.
 - x_1, x_2, ..., x_N \neq X

-----Input-----
Input is given from Standard Input in the following format:
N X
x_1 x_2 ... x_N

-----Output-----
Print the maximum value of D that enables you to visit all the cities.

-----Sample Input-----
3 3
1 7 11

-----Sample Output-----
2

Setting D = 2 enables you to visit all the cities as follows, and this is the maximum value of such D.
 - Perform Move 2 to travel to coordinate 1.
 - Perform Move 1 to travel to coordinate 3.
 - Perform Move 1 to travel to coordinate 5.
 - Perform Move 1 to travel to coordinate 7.
 - Perform Move 1 to travel to coordinate 9.
 - Perform Move 1 to travel to coordinate 11.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A of N integers. Find total number of pairs such that i < j and A[i] > A[j].

Constraints

1 ≤ N ≤ 2*10^3

1 ≤ Ai ≤ 10^9

SAMPLE INPUT
5
5 1 2 4 3

SAMPLE OUTPUT
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: BerSU Ball

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Berland State University is hosting a ballroom dance in celebration of its 100500-th anniversary! *n* boys and *m* girls are already busy rehearsing waltz, minuet, polonaise and quadrille moves.

We know that several boy&amp;girl pairs are going to be invited to the ball. However, the partners' dancing skill in each pair must differ by at most one.

For each boy, we know his dancing skills. Similarly, for each girl we know her dancing skills. Write a code that can determine the largest possible number of pairs that can be formed from *n* boys and *m* girls.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=100) — the number of boys. The second line contains sequence *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=100), where *a**i* is the *i*-th boy's dancing skill.

Similarly, the third line contains an integer *m* (1<=≤<=*m*<=≤<=100) — the number of girls. The fourth line contains sequence *b*1,<=*b*2,<=...,<=*b**m* (1<=≤<=*b**j*<=≤<=100), where *b**j* is the *j*-th girl's dancing skill.

Output Specification:
Print a single number — the required maximum possible number of pairs.

Demo Input:
['4\n1 4 6 2\n5\n5 1 5 7 9\n', '4\n1 2 3 4\n4\n10 11 12 13\n', '5\n1 1 1 1 1\n3\n1 2 3\n']

Demo Output:
['3\n', '0\n', '2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sleazy Bob has happened upon a vending machine. After watching enough people buy tasty snacks, Bob has realized that the vending machine is broken!

Here’s what Sleazy Bob observes:
 - A person tries to buy a snack
 - The vending machine then checks to see if there are any left of that snack
 - If there are any left, the machine charges the person for that snack
 - If the machine successfully charges the person, it then gives the person a different snack! Possibly no snack at all, if the machine is out of the different snack!

Sleazy Bob notices that, although the machine is broken, it is at least consistent. Whenever a customer buys a snack from position $i$, the machine vends from position $f(i)$, where $f$ is some predictable function.

Now, Bob wants to make a profit from the machine. He wants to buy some snacks from the machine, and then turn around and sell the snacks he gets for the market price of the snack. This may be different from the vending price. If a cheap snack is at $i$, and an expensive snack is at $f(i)$, he could rake in the cash! Assuming Bob can always find buyers for his snacks, what is the maximum net gain that Bob can obtain by buying some number, possibly zero, of snacks and turning around and selling them later? You may assume that Bob has enough money from other shady activities to cover the cost of buying any number of snacks from the vending machine.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each input begins with a line with a single integer $n$ ($1 \le n \le 100000$), which is the number of snack positions in the machine. Each of the next $n$ lines contains 4 space-separated integers, $f$ $p$ $m$ $s$, which describe a snack position in the machine, in order from 1 to $n$, where:
 - $f$ ($1\le f \le n$) is the value of $f(i)$. That is, it is the position from which the machine will vend when Bob buys from this position
 - $p$ ($1\le p \le 1000000$) is the price Bob must pay to buy from this position
 - $m$ ($1\le m \le 1000000$) is the market price of the snack at this position
 - $s$ ($1\le s \le 1000000$) is the number of snacks at this position

-----Output-----
Output a single line with a single integer, indicating the maximum profit Sleazy Bob can get from his nefarious abuse of the broken vending machine.

-----Examples-----
Sample Input 1:
3
1 2 3 1
2 3 4 1
3 4 5 1
Sample Output 1:
3

Sample Input 2:
3
2 2 3 8
3 1 5 6
1 9 4 7
Sample Output 2:
39

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Cormen --- The Best Friend Of a Man

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Recently a dog was bought for Polycarp. The dog's name is Cormen. Now Polycarp has a lot of troubles. For example, Cormen likes going for a walk. 

Empirically Polycarp learned that the dog needs at least *k* walks for any two consecutive days in order to feel good. For example, if *k*<==<=5 and yesterday Polycarp went for a walk with Cormen 2 times, today he has to go for a walk at least 3 times. 

Polycarp analysed all his affairs over the next *n* days and made a sequence of *n* integers *a*1,<=*a*2,<=...,<=*a**n*, where *a**i* is the number of times Polycarp will walk with the dog on the *i*-th day while doing all his affairs (for example, he has to go to a shop, throw out the trash, etc.).

Help Polycarp determine the minimum number of walks he needs to do additionaly in the next *n* days so that Cormen will feel good during all the *n* days. You can assume that on the day before the first day and on the day after the *n*-th day Polycarp will go for a walk with Cormen exactly *k* times. 

Write a program that will find the minumum number of additional walks and the appropriate schedule — the sequence of integers *b*1,<=*b*2,<=...,<=*b**n* (*b**i*<=≥<=*a**i*), where *b**i* means the total number of walks with the dog on the *i*-th day.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*,<=*k*<=≤<=500) — the number of days and the minimum number of walks with Cormen for any two consecutive days. 

The second line contains integers *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=500) — the number of walks with Cormen on the *i*-th day which Polycarp has already planned.

Output Specification:
In the first line print the smallest number of additional walks that Polycarp should do during the next *n* days so that Cormen will feel good during all days. 

In the second line print *n* integers *b*1,<=*b*2,<=...,<=*b**n*, where *b**i* — the total number of walks on the *i*-th day according to the found solutions (*a**i*<=≤<=*b**i* for all *i* from 1 to *n*). If there are multiple solutions, print any of them.

Demo Input:
['3 5\n2 0 1\n', '3 1\n0 0 0\n', '4 6\n2 4 3 5\n']

Demo Output:
['4\n2 3 2\n', '1\n0 1 0\n', '0\n2 4 3 5\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.