vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Cherry has a binary matrix $A$ consisting of $N$ rows and $M$ columns. The rows are numbered from $1$ to $N$, columns are numbered from $1$ to $M$. Element at row $i$ ($1$ ≤ $i$ ≤ $N$) and column $j$ ($1$ ≤ $j$ ≤ $M$) is denoted as $A_{ij}$. All elements of $A$ are either $0$ or $1$.
He performs $Q$ queries on matrix. Each query is provided by four integers $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ which define the rectangle, where ($x_{1}$, $y_{1}$) stands for the coordinates of the top left cell of the rectangle, while ($x_{2}$, $y_{2}$) stands for the coordinates of the bottom right cell. You need to flip all the bits i.e. ($0$ to $1$, $1$ to $0$) that are located fully inside the query rectangle.
Finally, print the matrix after performing all the queries.
Note: $x_{1}$ represents the row number while $y_{1}$ represents the column number.

-----Input:-----
- The first line of the input contains two integers $N$ and $M$ — the number of rows and the number of columns in the matrix.
- Each of the next $N$ lines contains a string of length $M$, where the $j^{th}$ character of $i^{th}$ line denotes the value of $A_{i,j}$. 
- Next line contains an integer $Q$ — the number of queries.
- Then follow $Q$ lines with queries descriptions. Each of them contains four space-seperated integers $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ — coordinates of the up left and bottom right cells of the query rectangle.

-----Output:-----
Print the matrix, in the form of $N$ strings, after performing all the queries.

-----Constraints-----
- $1 \leq N,M \leq 1000$
- $0 \leq  A_{ij}  \leq 1$
- $1 \leq Q \leq 10^6$
- $1 \leq x_{1} \leq x_{2} \leq N$
- $1 \leq y_{1} \leq y_{2} \leq M$

-----Sample Input:-----
2 2
00
00
3
1 1 1 1
2 2 2 2
1 1 2 2 

-----Sample Output:-----
01
10

-----Explanation:-----
Example case 1:
After processing the 1st query 1 1 1 1, matrix becomes:
[1000][1000]\begin{bmatrix} 10 \\ 00  \end{bmatrix}
After processing the 2nd query 2 2 2 2, the matrix becomes:
[1001][1001]\begin{bmatrix} 10 \\ 01  \end{bmatrix}
After processing the 3rd query 1 1 2 2, matrix becomes:
[0110][0110]\begin{bmatrix} 01 \\ 10  \end{bmatrix}
We need to output the matrix after processing all queries.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob has a rectangular chocolate bar of the size W × H. He introduced a cartesian coordinate system so that the point (0, 0) corresponds to the lower-left corner of the bar, and the point (W, H) corresponds to the upper-right corner. Bob decided to split the bar into pieces by breaking it. Each break is a segment parallel to one of the coordinate axes, which connects the edges of the bar. More formally, each break goes along the line x = xc or y = yc, where xc and yc are integers. It should divide one part of the bar into two non-empty parts. After Bob breaks some part into two parts, he breaks the resulting parts separately and independently from each other. Also he doesn't move the parts of the bar. Bob made n breaks and wrote them down in his notebook in arbitrary order. At the end he got n + 1 parts. Now he wants to calculate their areas. Bob is lazy, so he asks you to do this task.

Input

The first line contains 3 integers W, H and n (1 ≤ W, H, n ≤ 100) — width of the bar, height of the bar and amount of breaks. Each of the following n lines contains four integers xi, 1, yi, 1, xi, 2, yi, 2 — coordinates of the endpoints of the i-th break (0 ≤ xi, 1 ≤ xi, 2 ≤ W, 0 ≤ yi, 1 ≤ yi, 2 ≤ H, or xi, 1 = xi, 2, or yi, 1 = yi, 2). Breaks are given in arbitrary order.

It is guaranteed that the set of breaks is correct, i.e. there is some order of the given breaks that each next break divides exactly one part of the bar into two non-empty parts.

Output

Output n + 1 numbers — areas of the resulting parts in the increasing order.

Examples

Input

2 2 2
1 0 1 2
0 1 1 1


Output

1 1 2 

Input

2 2 3
1 0 1 2
0 1 1 1
1 1 2 1


Output

1 1 1 1 

Input

2 4 2
0 1 2 1
0 3 2 3


Output

2 2 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya decided to pass a very large integer n to Kate. First, he wrote that number as a string, then he appended to the right integer k — the number of digits in n. 

Magically, all the numbers were shuffled in arbitrary order while this note was passed to Kate. The only thing that Vasya remembers, is a non-empty substring of n (a substring of n is a sequence of consecutive digits of the number n).

Vasya knows that there may be more than one way to restore the number n. Your task is to find the smallest possible initial integer n. Note that decimal representation of number n contained no leading zeroes, except the case the integer n was equal to zero itself (in this case a single digit 0 was used).


-----Input-----

The first line of the input contains the string received by Kate. The number of digits in this string does not exceed 1 000 000.

The second line contains the substring of n which Vasya remembers. This string can contain leading zeroes. 

It is guaranteed that the input data is correct, and the answer always exists.


-----Output-----

Print the smalles integer n which Vasya could pass to Kate.


-----Examples-----
Input
003512
021

Output
30021

Input
199966633300
63

Output
3036366999

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iahub wants to enhance his multitasking abilities. In order to do this, he wants to sort n arrays simultaneously, each array consisting of m integers.

Iahub can choose a pair of distinct indices i and j (1 ≤ i, j ≤ m, i ≠ j). Then in each array the values at positions i and j are swapped only if the value at position i is strictly greater than the value at position j.

Iahub wants to find an array of pairs of distinct indices that, chosen in order, sort all of the n arrays in ascending or descending order (the particular order is given in input). The size of the array can be at most $\frac{m(m - 1)}{2}$ (at most $\frac{m(m - 1)}{2}$ pairs). Help Iahub, find any suitable array.


-----Input-----

The first line contains three integers n (1 ≤  n ≤ 1000), m (1 ≤ m ≤  100) and k. Integer k is 0 if the arrays must be sorted in ascending order, and 1 if the arrays must be sorted in descending order. Each line i of the next n lines contains m integers separated by a space, representing the i-th array. For each element x of the array i, 1 ≤ x ≤ 10^6 holds.


-----Output-----

On the first line of the output print an integer p, the size of the array (p can be at most $\frac{m(m - 1)}{2}$). Each of the next p lines must contain two distinct integers i and j (1 ≤ i, j ≤ m, i ≠ j), representing the chosen indices.

If there are multiple correct answers, you can print any.


-----Examples-----
Input
2 5 0
1 3 2 5 4
1 4 3 2 5

Output
3
2 4
2 3
4 5

Input
3 2 1
1 2
2 3
3 4

Output
1
2 1



-----Note-----

Consider the first sample. After the first operation, the arrays become [1, 3, 2, 5, 4] and [1, 2, 3, 4, 5]. After the second operation, the arrays become [1, 2, 3, 5, 4] and [1, 2, 3, 4, 5]. After the third operation they become [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a rooted tree on N vertices. The nodes are numbered from 1 to N, and Node 1 is the root. Each node u has an associated value attached to it: Au.
For each vertex v, we consider the path going upwards from v to the root. Suppose that path is v1, v2, .., vk, where v1 = v and vk = 1. The cost of any node on this path is equal to the minimum value among all the nodes to its left in the path sequence, including itself. That is, cost(vi) = min1 <= j <= i{Avj}. And the cost of the path is the sum of costs of all the nodes in it.
For every node in the tree, find the cost of the path from that node to the root.

-----Input-----
- The first line of the input contains a single integer, N, denoting the number of nodes in the tree.
- The next line contains N-1 integers, the i-th of which denotes the parent of node i+1.
- The next line contains N integers, the i-th of which denotes Ai.

-----Output-----
Output a single line containing N integers, the i-th of which should be the cost of the path from node i to the root.

-----Constraints-----
- 1 ≤ N ≤ 100,000
- -1,000,000,000 ≤ Av ≤ 1,000,000,000

-----Subtasks-----
- Subtask #1 (30 points): 1 ≤ N ≤ 2000
- Subtask #2 (70 points): Original constraints.

-----Example-----
Input:
8
1 1 1 1 5 8 6
1 2 3 4 5 15 70 10

Output: 
1 3 4 5 6 21 96 26

-----Explanation-----
For example, take a look at the path from vertex 7: The path is 7 -> 8 -> 6 -> 5 -> 1.
Cost(7) has no choice but to be A7. So Cost(7) = 70.
Cost(8) will be minimum of A7 and A8, which turns out to be A8. So Cost(8) = 10.
Cost(6) = minimum {A7, A8, A6} = minimum {70, 10, 15} = 10.
Cost(5) = minimum {70, 10, 15, 5} = 5.
Cost(1) = minimum {70, 10, 15, 5, 1} = 1. 
So, the cost of the path from 7 to the root is 70 + 10 + 10 + 5 + 1 = 96.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In order to keep up with the rapid technological advancements, Mr. Panda needs to backup all the data on his computer to allow him to do a full upgrade of his computer. Since the upgrade will take some time, he will peruse the services of the company ACM (Association of Computer Maintenance) that provides storage servers for him to temporarily store his data.

Although ACM offers storage servers of any size, ACM wants to encourage more bulk purchases of servers of the same size as this saves cost. The cost of purchasing a set of storage servers that can each store $M$ bytes consists of a base cost of $M$ dollars plus $1$ dollar for every server of that size purchased.

Mr. Panda wants to store a total of $K$ bytes of data and in order to easily track the servers, he wants to purchase a set of storage servers of the same size to store the $K$ bytes of data using the least cost. However, Mr. Panda feels compelled not to waste any space. Thus, he requires that the total storage space of the servers purchased must be exactly $K$ bytes.

As storage space of technology increases exponentially with time, $K$ can be very large. You are given the prime factorization of $K$. Help Mr. Panda calculate the minimum cost required to store his data. As the minimum cost can be quite large, print the minimum cost modulo a prime number $10^9+7$.

-----Input-----
The input consists of one line with a string of even length consisting of at most $700$ representing the prime factorization of $K$. Every pair of two consecutive digits, starting from the first two digits, represents one prime factor. So input of length $N$ will have $N/2$ prime factors.

It is guaranteed that all the prime factors given are prime and that $K$ has at most $10^{10}$ divisors. Each prime factor will appear at most $100$ times.

-----Output-----
Output the minimum cost in one line as a single integer.Sample Data Explanation

In the first example, $K = 2 \cdot 3 \cdot 2 = 12$, so buy three servers with $M = 4$ bytes. Mr. Panda pays $4$ dollars base cost plus $3$ dollars for three servers purchased, or a total of $4+3 = 7$ dollars. Mr. Panda can also buy four servers with $M = 3$ bytes with the same cost of $7$ dollars.

In the second example, $K = 13 \cdot 11 = 143$, so buy eleven servers with $M = 13$ bytes. Mr. Panda pays $13$ dollars base cost plus $11$ dollars for eleven servers purchased, or a total $13+11 = 24$ dollars. Mr. Panda can also buy thirteen servers with $M = 11$ bytes with the same cost of $24$ dollars.

In the third example, $K = 11$, so buy one server with $M = 11$ bytes. Mr. Panda pays $11$ dollars base cost plus $1$ dollar for one server purchased, or a total $11+1 = 12$ dollars. Note that although he can get a cheaper cost if he were able to purchase storage servers of different sizes, he cannot do so.

-----Examples-----
Sample Input 1:
020302
Sample Output 1:
7

Sample Input 2:
1311
Sample Output 2:
24

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

The Tunisian Coal Mining company uses a train to ferry out coal blocks from its coal mines. The train has N containers numbered from 1 to N which need to

be filled with blocks of coal. Assume there are infinite coal blocks. The containers are arranged in increasing order of capacity, and the ith container

has capacity i. Every container has a specific loading cost ci. The workers fill the containers in rounds. In every round, they choose a subset of

containers and load them with coal blocks. This subset should be such that each subsequent container chosen in a round should be more spacious than the

previous one. Also, the difference in loading cost of consecutive containers should be at least K.



What is the least number of rounds in which all containers can be filled?



-----
Input
-----

The first line contains the number of test cases T. T test cases follow.

Each case contains an integer N and K on the first line, followed by integers c1,...,cn on the second line.



1 <= T <= 100

1 <= N <= 300

1 <= ci <= 1000

1 <= K <= 1000



-----
Output
-----

Output T lines, one for each test case, containing the minimum number of rounds in which all containers could be filled.

-----
Example
-----

Input:

2

3 2

5 4 7

5 1

5 3 4 5 6



Output:

2

1







Explanation:

For the first example, workers can fill the containers of cost 5 and 7 in the first round and the container with cost 4 in the next round. Note that the

containers with cost 5 and 4 cannot be filled consecutively because the loading costs should differ by at least K (which is 2). Also, the containers cannot

be filled in order 5, 7, 4 in one round because the containers filled in a round should be in increasing capacity.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Byteland is a beautiful land known because of its beautiful trees.

Misha has found a binary tree with $n$ vertices, numbered from $1$ to $n$. A binary tree is an acyclic connected bidirectional graph containing $n$ vertices and $n - 1$ edges. Each vertex has a degree at most $3$, whereas the root is the vertex with the number $1$ and it has a degree at most $2$.

Unfortunately, the root got infected.

The following process happens $n$ times:

Misha either chooses a non-infected (and not deleted) vertex and deletes it with all edges which have an end in this vertex or just does nothing.

Then, the infection spreads to each vertex that is connected by an edge to an already infected vertex (all already infected vertices remain infected).

As Misha does not have much time to think, please tell him what is the maximum number of vertices he can save from the infection (note that deleted vertices are not counted as saved).


-----Input-----

There are several test cases in the input data. The first line contains a single integer $t$ ($1\leq t\leq 5000$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $n$ ($2\leq n\leq 3\cdot 10^5$) — the number of vertices of the tree.

The $i$-th of the following $n-1$ lines in the test case contains two positive integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), meaning that there exists an edge between them in the graph.

It is guaranteed that the graph is a binary tree rooted at $1$. It is also guaranteed that the sum of $n$ over all test cases won't exceed $3\cdot 10^5$.


-----Output-----

For each test case, output the maximum number of vertices Misha can save.


-----Examples-----

Input
4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15
Output
0
2
2
10


-----Note-----

In the first test case, the only possible action is to delete vertex $2$, after which we save $0$ vertices in total.

In the second test case, if we delete vertex $2$, we can save vertices $3$ and $4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has three baskets and two of them have multiple balls(Natural numbers written on them). The first basket has N balls, the second basket has M balls and the third basket is empty. Chef starts choosing all the unique balls(only occurring once in both the baskets) and puts into the third basket and throw the repetitive ones. Print numbers on the balls of the third basket in ascending order. 

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains three lines of input.
- First-line has two integers $N, M$. 
- Second-line with N space-separated numbers.
- Third-line with M space-separated numbers.

-----Output:-----
For each testcase, output in a single line answer.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $1 \leq M \leq 10^5$

-----Sample Input:-----
1
4 5
1 2 3 4
2 3 4 5 6

-----Sample Output:-----
1 5 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to validate rhythm with a meter.

_________________________________________________
Rules:

1. Rhythmic division requires that in one whole note (1) there are two half notes (2) or four quarter notes (4) or eight eighth notes (8). 
Examples: 1 = 2 + 2, 1 = 4 + 4 + 4 + 4 ... 
Note that: 2 = 4 + 4, 4 = 8 + 8, 2 = 8 + 8 + 4 ... 

2. Meter gives an information how many rhythmic types of notes should be in one bar. Bar is the the primary section of a musical score.
Examples: 
          4/4 -> 4 quarter notes in a bar
          5/2 -> 5 half notes in a bar
          3/8 -> 3 eighth notes in a bar
Note that: 
for 4/4 valid bars are: '4444', '88888888', '2488' ...
for 5/2 valid bars are: '22222', '2244244', '8888244888844' ...
for 3/8 valid bars are: '888', '48' ...

3. Anacrusis occurs when all bars but the first and last are valid, and the notes in the first and last bars when combined would also make a valid bar.

Examples: 
for 4/4 valid anacrusis is -> 44|...|44 or 88|...|888888 or 2|...|488 
for 5/2 valid anacrusis is -> 22|...|222 or 222|...|22 or  2244|...|244
for 3/8 valid anacrusis is -> 8|...|88 or 4|...|8 or 8|...|4
Note:
When anacrusis is valid but other bars in score are not -> return 'Invalid rhythm'
________________________________________________

Input:
meter - array: eg. [4, 4],
score - string, bars separated with '|': eg. '4444|8484842|888'

Output:
string message: 'Valid rhythm', 'Valid rhythm with anacrusis' or 'Invalid rhythm'

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A family of kookaburras are in my backyard.

I can't see them all, but I can hear them!

# How many kookaburras are there?




## Hint 

The trick to counting kookaburras is to listen carefully

* The males go ```HaHaHa```...

* The females go ```hahaha```...

* And they always alternate male/female



^ Kata Note : No validation is necessary; only valid input will be passed :-)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree with N nodes with every node being colored. A color is represented by an integer ranging from 1 to 10^{9}. Can you find the number of distinct colors available in a subtree rooted at the node s? 

Input Format 

The first line contains three space separated integers representing the number of nodes in the tree (N), number of queries to answer (M) and the root of the tree. 

In each of the next N-1 lines, there are two space separated integers(a b) representing an edge from node a to Node b and vice-versa.   

N lines follow: N+$i^{th} $line contains the color of the$ i^{th} $node.

M lines follow: Each line containg a single integer s.

Output Format 

Output exactly M lines, each line containing the output of the i_{th} query.

Constraints 

0 <= M <= $10^{5}$

1 <= N <= $10^{5}$

1 <= root <= N

1 <= color of the Node <=$ 10^{9}$

Example

Sample Input

4 2 1
1 2
2 4
2 3
10
20
20
30
1
2

Sample Output

3
2

Explanation

Query 1-Subtree rooted at 1 is the entire tree and colors used are 10 20 20 30 , so the answer is 3(10,20 and 30)

Query 2-Subtree rooted at 2 contains color 20 20 30, so the answer is 2(20 and 30)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, we are going to reverse a string while maintaining the spaces (if any) in their original place.

For example:
```
solve("our code") = "edo cruo"
-- Normal reversal without spaces is "edocruo". 
-- However, there is a space at index 3, so the string becomes "edo cruo"

solve("your code rocks") = "skco redo cruoy". 
solve("codewars") = "srawedoc"
```
More examples in the test cases. All input will be lower case letters and in some cases spaces.

Good luck!

Please also try:

[Simple time difference](https://www.codewars.com/kata/5b76a34ff71e5de9db0000f2)

[Simple remove duplicates](https://www.codewars.com/kata/5ba38ba180824a86850000f7)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A parking lot in the City consists of n parking spaces, standing in a line. The parking spaces are numbered from 1 to n from left to right. 

When a car arrives at the lot, the operator determines an empty parking space for it. For the safety's sake the chosen place should be located as far from the already occupied places as possible. That is, the closest occupied parking space must be as far away as possible. If there are several such places, then the operator chooses the place with the minimum index from them. If all parking lot places are empty, then the car gets place number 1.

We consider the distance between the i-th and the j-th parking spaces equal to 4·|i - j| meters.

You are given the parking lot records of arriving and departing cars in the chronological order. For each record of an arriving car print the number of the parking lot that was given to this car.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 2·105) — the number of parking places and the number of records correspondingly. 

Next m lines contain the descriptions of the records, one per line. The i-th line contains numbers ti, idi (1 ≤ ti ≤ 2; 1 ≤ idi ≤ 106). If ti equals 1, then the corresponding record says that the car number idi arrived at the parking lot. If ti equals 2, then the corresponding record says that the car number idi departed from the parking lot. 

Records about arriving to the parking lot and departing from the parking lot are given chronologically. All events occurred consecutively, no two events occurred simultaneously.

It is guaranteed that all entries are correct: 

  * each car arrived at the parking lot at most once and departed from the parking lot at most once, 
  * there is no record of a departing car if it didn't arrive at the parking lot earlier, 
  * there are no more than n cars on the parking lot at any moment. 



You can consider the cars arbitrarily numbered from 1 to 106, all numbers are distinct. Initially all places in the parking lot are empty.

Output

For each entry of an arriving car print the number of its parking space. Print the numbers of the spaces in the order, in which the cars arrive to the parking lot.

Examples

Input

7 11
1 15
1 123123
1 3
1 5
2 123123
2 15
1 21
2 3
1 6
1 7
1 8


Output

1
7
4
2
7
4
1
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have invented a time-machine which has taken you back to ancient Rome. Caeser is impressed with your programming skills and has appointed you to be the new information security officer.

Caeser has ordered you to write a Caeser cipher to prevent Asterix and Obelix from reading his emails.

A Caeser cipher shifts the letters in a message by the value dictated by the encryption key. Since Caeser's emails are very important, he wants all encryptions to have upper-case output, for example:

If key = 3
"hello" -> KHOOR
If key = 7
"hello" -> OLSSV

Input will consist of the message to be encrypted and the encryption key.

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