vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The current programming club president, Norbit, gives speeches at the weekly club meetings. Casual viewers are underwhelmed with the quality of Norbit’s elocution. Specifically, Norbit often hesitates during his speeches with interjections like “umm.”

You, however, are no casual viewer–you are a computer scientist! You have noticed strange patterns in Norbit’s speech. Norbit’s interjections, when arranged together, form a binary code! By substituting $1$’s and $0$’s for u’s and m’s, respectively, you produce 7-bit binary ASCII codes that spell out secret messages.

For example, the letter ‘a’ has an ASCII code of $97$, which translates to a binary value of $1100001$ and an umm code of “uummmmu”. An umm code can be split up in the speech. For example, an encoding of ‘a’ could be stretched across three utterances: “uum”, “mmm”, “u” (possibly with other non-umm code words occurring between them).

Now that you have discovered Norbit’s secret, you go back through transcripts of his previous speeches to decode his cleverly concealed messages.

-----Input-----
There is one line of input of length $S$ ($20 \le S \le 500000$), which ends with a single newline. Before the newline, the input may contain any characters in the ASCII range $32$ – $126$ (that is, space (‘ ’) through tilde (‘~’)).

Let’s define a “word” as a space-delimited sequence of characters. If a word does not contain any letters or digits except lowercase u’s and/or m’s, then it is part of the umm-coded message. If a word contains digits or letters other than lowercase u and m, then it is not part of the umm-coded message (even if it does contain u or m). Note that a word that is part of the umm-coded message may contain punctuation (which is defined as anything other than letters, digits, or space). Naturally, you should only consider the u and m characters (and not punctuation) when decoding the umm-coded message. Let $M$ be the length of the entire umm-coded message (counting only its u and m characters). It is guaranteed that $M \ge 7$ and $M$ is evenly divisible by $7$.

-----Output-----
Print the de-umm-coded message. Note that for this problem, the judging is case-sensitive. It is guaranteed that each character that should be output is in the same ASCII range as the input.

-----Examples-----
Sample Input:
uu Friends m Romans ummuuummmuuuuumm countrymen mmuummmuu
Sample Output:
icpc

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
write me a function `stringy` that takes a `size` and returns a `string` of alternating `'1s'` and `'0s'`.

the string should start with a `1`.

a string with `size` 6 should return :`'101010'`.

with `size` 4 should return : `'1010'`.

with `size` 12 should return : `'101010101010'`.

The size will always be positive and will only use whole numbers.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A bicycle race is being organized in a country. The transport network of the country consists of $N$ cities numbered $1$ through $N$, with $M$ bidirectional roads connecting them. We will use the following terms:
 - A path is a sequence of roads in which each road starts in the city the preceding road ended in.
 - A simple path is a path which never visits a city more than once.
 - A ring is a simple path ending in the same city it started in.

The network is such that there is at least one path between every pair of cities. Additionally, every road in the network is part of at most one ring.

Your task is to find the longest path for the race satisfying two constraints:
 - The path may begin in any city, but must end in city $1$.
 - The path may visit a city more than once, but it must not contain any road more than once.

-----Input-----
The first line of input contains two integers $N$ and $M$ ($2 \le N \le 10000$, $1 \le M \le 2N-2$) – the numbers of cities and roads in the network.

Each of the following $M$ lines contains two different integers $A$ and $B$ ($1 \le A, B \le N$). These numbers indicate that there is a bidirectional road between cities $A$ and $B$. No two cities will be directly connected by more than one road.

-----Output-----
Output the length of the longest race path on a single line.

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

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree with N vertices and N-1 edges. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and b_i.
You have coloring materials of K colors.
For each vertex in the tree, you will choose one of the K colors to paint it, so that the following condition is satisfied:
 - If the distance between two different vertices x and y is less than or equal to two, x and y have different colors.
How many ways are there to paint the tree? Find the count modulo 1\ 000\ 000\ 007.
What is tree?
A tree is a kind of graph. For detail, please see: Wikipedia "Tree (graph theory)"

What is distance?
The distance between two vertices x and y is the minimum number of edges one has to traverse to get from x to y.

-----Constraints-----
 - 1 \leq N,K \leq 10^5
 - 1 \leq a_i,b_i \leq N
 - The given graph is a tree.

-----Input-----
Input is given from Standard Input in the following format:
N K
a_1 b_1
a_2 b_2
.
.
.
a_{N-1} b_{N-1}

-----Output-----
Print the number of ways to paint the tree, modulo 1\ 000\ 000\ 007.

-----Sample Input-----
4 3
1 2
2 3
3 4

-----Sample Output-----
6


There are six ways to paint the tree.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are M chairs arranged in a line. The coordinate of the i-th chair (1 ≤ i ≤ M) is i.

N people of the Takahashi clan played too much games, and they are all suffering from backaches. They need to sit in chairs and rest, but they are particular about which chairs they sit in. Specifically, the i-th person wishes to sit in a chair whose coordinate is not greater than L_i, or not less than R_i. Naturally, only one person can sit in the same chair.

It may not be possible for all of them to sit in their favorite chairs, if nothing is done. Aoki, who cares for the health of the people of the Takahashi clan, decides to provide additional chairs so that all of them can sit in chairs at their favorite positions.

Additional chairs can be placed at arbitrary real coordinates. Find the minimum required number of additional chairs.

Constraints

* 1 ≤ N,M ≤ 2 × 10^5
* 0 ≤ L_i < R_i ≤ M + 1(1 ≤ i ≤ N)
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N M
L_1 R_1
:
L_N R_N


Output

Print the minimum required number of additional chairs.

Examples

Input

4 4
0 3
2 3
1 3
3 4


Output

0


Input

7 6
0 7
1 5
3 6
2 7
1 6
2 6
3 7


Output

2


Input

3 1
1 2
1 2
1 2


Output

2


Input

6 6
1 6
1 6
1 5
1 5
2 6
2 6


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a sequence a with n elements 1, 2, 3, ..., k - 1, k, k - 1, k - 2, ..., k - (n - k) (k ≤ n < 2k).

Let's call as inversion in a a pair of indices i < j such that a[i] > a[j].

Suppose, you have some permutation p of size k and you build a sequence b of size n in the following manner: b[i] = p[a[i]].

Your goal is to find such permutation p that the total number of inversions in b doesn't exceed the total number of inversions in a, and b is lexicographically maximum.

Small reminder: the sequence of k integers is called a permutation if it contains all integers from 1 to k exactly once.

Another small reminder: a sequence s is lexicographically smaller than another sequence t, if either s is a prefix of t, or for the first i such that s_i ≠ t_i, s_i < t_i holds (in the first position that these sequences are different, s has smaller number than t).

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first and only line of each test case contains two integers n and k (k ≤ n < 2k; 1 ≤ k ≤ 10^5) — the length of the sequence a and its maximum.

It's guaranteed that the total sum of k over test cases doesn't exceed 10^5.

Output

For each test case, print k integers — the permutation p which maximizes b lexicographically without increasing the total number of inversions.

It can be proven that p exists and is unique.

Example

Input


4
1 1
2 2
3 2
4 3


Output


1 
1 2 
2 1 
1 3 2 

Note

In the first test case, the sequence a = [1], there is only one permutation p = [1].

In the second test case, the sequence a = [1, 2]. There is no inversion in a, so there is only one permutation p = [1, 2] which doesn't increase the number of inversions.

In the third test case, a = [1, 2, 1] and has 1 inversion. If we use p = [2, 1], then b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2] and also has 1 inversion.

In the fourth test case, a = [1, 2, 3, 2], and since p = [1, 3, 2] then b = [1, 3, 2, 3]. Both a and b have 1 inversion and b is the lexicographically maximum.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Gerald and Giant Chess

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Giant chess is quite common in Geraldion. We will not delve into the rules of the game, we'll just say that the game takes place on an *h*<=×<=*w* field, and it is painted in two colors, but not like in chess. Almost all cells of the field are white and only some of them are black. Currently Gerald is finishing a game of giant chess against his friend Pollard. Gerald has almost won, and the only thing he needs to win is to bring the pawn from the upper left corner of the board, where it is now standing, to the lower right corner. Gerald is so confident of victory that he became interested, in how many ways can he win?

The pawn, which Gerald has got left can go in two ways: one cell down or one cell to the right. In addition, it can not go to the black cells, otherwise the Gerald still loses. There are no other pawns or pieces left on the field, so that, according to the rules of giant chess Gerald moves his pawn until the game is over, and Pollard is just watching this process.

Input Specification:
The first line of the input contains three integers: *h*,<=*w*,<=*n* — the sides of the board and the number of black cells (1<=≤<=*h*,<=*w*<=≤<=105,<=1<=≤<=*n*<=≤<=2000). 

Next *n* lines contain the description of black cells. The *i*-th of these lines contains numbers *r**i*,<=*c**i* (1<=≤<=*r**i*<=≤<=*h*,<=1<=≤<=*c**i*<=≤<=*w*) — the number of the row and column of the *i*-th cell.

It is guaranteed that the upper left and lower right cell are white and all cells in the description are distinct.

Output Specification:
Print a single line — the remainder of the number of ways to move Gerald's pawn from the upper left to the lower right corner modulo 109<=+<=7.

Demo Input:
['3 4 2\n2 2\n2 3\n', '100 100 3\n15 16\n16 15\n99 88\n']

Demo Output:
['2\n', '545732279\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vitya is studying in the third grade. During the last math lesson all the pupils wrote on arithmetic quiz. Vitya is a clever boy, so he managed to finish all the tasks pretty fast and Oksana Fillipovna gave him a new one, that is much harder.

Let's denote a flip operation of an integer as follows: number is considered in decimal notation and then reverted. If there are any leading zeroes afterwards, they are thrown away. For example, if we flip 123 the result is the integer 321, but flipping 130 we obtain 31, and by flipping 31 we come to 13.

Oksana Fillipovna picked some number *a* without leading zeroes, and flipped it to get number *a**r*. Then she summed *a* and *a**r*, and told Vitya the resulting value *n*. His goal is to find any valid *a*.

As Oksana Fillipovna picked some small integers as *a* and *a**r*, Vitya managed to find the answer pretty fast and became interested in finding some general algorithm to deal with this problem. Now, he wants you to write the program that for given *n* finds any *a* without leading zeroes, such that *a*<=+<=*a**r*<==<=*n* or determine that such *a* doesn't exist.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=10100<=000).

Output Specification:
If there is no such positive integer *a* without leading zeroes that *a*<=+<=*a**r*<==<=*n* then print 0. Otherwise, print any valid *a*. If there are many possible answers, you are allowed to pick any.

Demo Input:
['4\n', '11\n', '5\n', '33\n']

Demo Output:
['2\n', '10\n', '0\n', '21\n']

Note:
In the first sample 4 = 2 + 2, *a* = 2 is the only possibility.

In the second sample 11 = 10 + 1, *a* = 10 — the only valid solution. Note, that *a* = 01 is incorrect, because *a* can't have leading zeroes.

It's easy to check that there is no suitable *a* in the third sample.

In the fourth sample 33 = 30 + 3 = 12 + 21, so there are three possibilities for *a*: *a* = 30, *a* = 12, *a* = 21. Any of these is considered to be correct answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
CBI agents are investigating a case in which they came across certain names of the culprits. They decided to encode the names into the number format.
"Riya" is encoded as "729611390","Sumitha" as "73108101981109993" ,"Anandita" as "55101891039410011294" and so on. Given a String S denoting a name, Encode the name.
 
Example 1:
Input:
S = "Soni"
Output:
7310210298
Explanation:
The name when encoded gives the given Output.
Example 2:
Input:
S = " Pawan"
Output:
708811190104 
Explanation:
The name when encoded gives the given Output.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function encodeTheName() which takes a String S as input and returns a String as the encoded format.
 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
 
Constraints:
1 <= |S| <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hu the Tomb Raider has entered a new tomb! It is full of gargoyles, mirrors, and obstacles. There is a door, with treasure beyond. Hu must unlock the door guarding the treasure. On that door is written, in an ancient tongue, the secret to opening the door:Every face of every gargoyle shall see a face of a gargoyle.

This means that the gargoyles must be rotated in such a way that there is a path for a beam of light to connect each gargoyle’s face to another gargoyle’s face (possibly its own). The beam of light is reflected by mirrors.

The floorplan of the tomb can be described as a rectangular $n \! \times \! m$ grid of cells:
 - A dot (‘.’) represents an empty cell.
 - A hash (‘#’) represents an obstacle.
 - A slash (‘/’) represents a double-sided mirror, as does a Backslash (‘\’) .
 - A character ‘V’ represents a gargoyle with two faces facing top and bottom.
 - A character ‘H’ represents a gargoyle with two faces facing left and right.

In addition to the ‘\’ and ‘/’ mirrors, the tomb is surrounded by walls of mirrors. The following common sense about light is assumed:
 - Light travels in a straight line through empty cells.
 - Two beams of light can intersect without interfering with each other.
 - A ‘\’ mirror reflects light coming from the top/bottom/left/right to the right/left/bottom/top. A ‘/’ mirror reflects light coming from the top/bottom/left/right to the left/right/top/bottom.
 - Light is reflected by $180$ degrees when it hits a wall (walls are all mirrors).
 - Light is blocked by obstacles and gargoyles.

Hu may rotate any gargoyle by $90$ degrees. As time is running short, he wants to know the minimum number of gargoyles that have to be rotated in order to unlock the treasure door.

-----Input-----
The first line of input contains two space-separated integers $n$ and $m$ ($1 \leq n, m \leq 500$), which are the dimensions of the tomb.

Each of the next $n$ lines contains a string $s$ ($|s|=m$) with the characters described above. This is the floorplan of the tomb.

-----Output-----
Output a single integer, which is the minimum number of gargoyles that have to be rotated in order to unlock the treasure door. If the puzzle has no solution, output $-1$.

-----Sample Explanation-----


The above are illustrations of Sample Input/Output $1$ with the initial configuration on the left and the solution of the puzzle on the right. Three gargoyles are rotated to solve the puzzle.

-----Examples-----
Sample Input 1:
5 5
/.V.\
./.V.
..#..
.V.#.
\.V./
Sample Output 1:
3

Sample Input 2:
2 5
V...\
H...V
Sample Output 2:
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is only little time left until the New Year! For that reason, Chef decided to make a present for his best friend. He made a connected and undirected simple graph with N$N$ vertices and M$M$ edges.
Since Chef does not like odd numbers and his friend does not like undirected graphs, Chef decided to direct each edge in one of two possible directions in such a way that the indegrees of all vertices of the resulting graph are even. The indegree of a vertex is the number of edges directed to that vertex from another vertex. As usual, Chef is busy in the kitchen, so you need to help him with directing the edges. Find one possible way to direct them or determine that it is impossible under the given conditions, so that Chef could bake a cake as a present instead.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains two space-separated integers N$N$ and M$M$.
- M$M$ lines follow. For each i$i$ (1≤i≤M$1 \le i \le M$), the i$i$-th of these lines contains two space-separated integers ui$u_i$ and vi$v_i$ denoting an edge between vertices ui$u_i$ and vi$v_i$.

-----Output-----
For each test case:
- If a valid way to direct the edges does not exist, print a single line containing one integer −1$-1$.
- Otherwise, print a single line containing M$M$ space-separated integers. For each valid i$i$, the i$i$-th of these integers should be 0$0$ if edge i$i$ is directed from ui$u_i$ to vi$v_i$ or 1$1$ if it is directed from vi$v_i$ to ui$u_i$.

-----Constraints-----
- 1≤T≤5$1 \le T \le 5$
- 1≤N,M≤105$1 \le N, M \le 10^5$
- 1≤ui,vi≤N$1 \le u_i, v_i \le N$ for each valid i$i$
- the graph on the input is connected, does not contain multiple edges or self-loops

-----Subtasks-----
Subtask #1 (30 points): 1≤N,M≤1,000$1 \le N, M \le 1,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
2
4 4
1 2
1 3
2 4
3 4
3 3
1 2
2 3
1 3

-----Example Output-----
0 0 1 1
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Cman doesn't love math anymore. He loves Alisha. Alisha is cute. :)
Cman goes on a date with her. They go to a candy shop. Alisha loves candies. 
The shop has n number of jars, each jar having a different type of candy.

Alisha wants to taste all type of candies so she asks Cman to buy candies for her.
She also asks Cman to buy at least X[i] candies of type i. 
Cost of each candy is $1.
Cman has forgotten to bring his wallet so the poor guy has no money.

Cman has to anyhow buy these candies for Alisha. So, he asks the shopkeeper for help and looking at the condition of Cman, the shopkeeper agrees to help Cman but on a condition. Shopkeeper puts the condition that he will give Cman candies of $R for free if Cman can tell him the total number of ways to select the candies such that it fulfills Alisha's condition of getting at least X[i] candies of type i and also the sum of candies result in total cost of exactly $R.

As things are awkward between Cman and math currently, he asks you for help. So, your task is to help Cman to find the resulting number of ways modulo 10^9 +7 so that he can get candies for free and can make Alisha happy.

P.S. : Alisha will give a kiss to Cman if he buys the required number of candies for her. So, your task is to help Cman to get a kiss. :’) 
Input :

First line of input will contain an integer T representing number of test cases.
First line of each test case will contain two space separated integer N and R representing number of jars and amount in dollar which shopkeeper is going to give cman if he completes the required task.
Second line of test case contain N space separated integer X[i] representing the minimum number of candies required of type i.
Output :

Print T lines each contain a single integer representing the number of ways modulo 10^9 + 7.
Constraints :

1 ≤ T ≤ 10

1 ≤ N ≤ 100000

1 ≤ X[i] ≤ 3

X[1]+X[2]+...+X[N] < R < 400000

SAMPLE INPUT
1
3 4
1 1 1

SAMPLE OUTPUT
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an N \times M grid consisting of N rows numbered 1 to N from top to bottom and M columns numbered 1 to M from left to right. Each cell of the grid is initially white.

You can perform the following operation any number of times (possibly zero):
Select a row i (1 ≤ i ≤ N) and paint all the cells in row i black.
Or select a column i (1 ≤ i ≤ M) and paint all the cells in column i black.

Note that cells which are already black remain black if they are painted over again.

Determine if it is possible to paint exactly K cells of the grid black after performing some operations.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line containing N, M and K — the number of rows, the number of columns and the number of cells to paint black.

------ Output Format ------ 

For each test case, output the string YES if it is possible to paint exactly K cells black, and NO if it is not.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

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

$1 ≤ T ≤ 2000$
$3 ≤ N, M ≤ 10^{9}$
$0 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------ 
2
3 5 13
3627 17424 27008005
----- Sample Output 1 ------ 
YES
NO
----- explanation 1 ------ 
Test case 1: One possible sequence of operations is as follows:
- Select column $2$ and paint it black.
- Select row $1$ and paint it black.
- Select column $4$ and paint it black.
- Select column $5$ and paint it black.
- Select row $3$ and paint it black.

After performing these operations, the grid contains exactly $13$ black cells. Hence the answer is YES.

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