vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
We are interested in collecting the triples of positive integers ```(a, b, c)``` that fulfill the following equation:
```python
a² + b² = c³
```
The first triple with the lowest values that satisfies the equation we have above is (2, 2 ,2).
In effect:
```python
2² + 2² = 2³
4  + 4  = 8
```
The first pair of triples that "shares" the same value of ```c``` is: ```(2, 11, 5)``` and ```(5, 10, 5)```. 

Both triples share the same value of ```c```  is ```c = 5```. 
```python
Triple (2, 11, 5)                  Triple(5, 10, 5)
2² + 11² =  5³                      5² +  10²  =  5³
4  + 121 = 125                     25  + 100   = 125
```
So, we say that the value ```c``` has two solutions because there are two triples sharing the same value of ```c```.

There are some values of ```c``` with no solutions.

The first value of ```c``` that have a surprising number of solutions is ```65``` with ```8``` different triples.

In order to avoid duplications you will consider that ```a <= b``` always.

Make the function ```find_abc_sumsqcube()```, that may give us the values of c for an specific number of solutions.

For that purpose the above required function will receive two arguments, ```c_max``` and ```num_sol```. It is understandable that ```c_max``` will give to our function the upper limit of ```c``` and ```num_sol```, the specific number of solutions.

The function will output a sorted list with the values of ```c``` that have a number of solutions equals to ```num_sol```

Let's see some cases: 
```python
find_abc_sumsqcube(5, 1) == [2] # below or equal to c_max = 5 we have triple the (2, 2, 2) (see above)

find_abc_sumsqcube(5, 2) == [5] # now we want the values of ```c ≤ c_max``` with two solutions (see above again)

find_abc_sumsqcube(10, 2) == [5, 10]

find_abc_sumsqcube(20, 8) == [] # There are no values of c equal and bellow 20 having 8 solutions.
```

Our tests will have the following ranges for our two arguments:
```python
5 ≤ c_max ≤ 1000
1 ≤ num_sol ≤ 10
```
Happy coding!!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Farmer Jon has recently bought $n$ tree seedlings that he wants to plant in his yard. It takes $1$ day for Jon to plant a seedling1, and for each tree Jon knows exactly in how many days after planting it grows to full maturity. Jon would also like to throw a party for his farmer friends, but in order to impress them he would like to organize the party only after all the trees have grown. More precisely, the party can be organized at earliest on the next day after the last tree has grown up.

Help Jon to find out when is the earliest day when the party can take place. Jon can choose the order of planting the trees as he likes, so he wants to plant the trees in such a way that the party will be as soon as possible.

-----Input-----
The input consists of two lines. The first line contains a single integer $N$ ($1\leq N \leq 100000$) denoting the number of seedlings. Then a line with $N$ integers $t_ i$ follows ($1\leq t_ i\leq 1000000$), where $t_ i$ denotes the number of days it takes for the $i$th tree to grow.

-----Output-----
You program should output exactly one line containing one integer, denoting the earliest day when the party can be organized. The days are numbered $1,2,3,\ldots $ beginning from the current moment.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The cows have just learned what a primitive root is! Given a prime p, a primitive root $\operatorname{mod} p$ is an integer x (1 ≤ x < p) such that none of integers x - 1, x^2 - 1, ..., x^{p} - 2 - 1 are divisible by p, but x^{p} - 1 - 1 is. 

Unfortunately, computing primitive roots can be time consuming, so the cows need your help. Given a prime p, help the cows find the number of primitive roots $\operatorname{mod} p$.


-----Input-----

The input contains a single line containing an integer p (2 ≤ p < 2000). It is guaranteed that p is a prime.


-----Output-----

Output on a single line the number of primitive roots $\operatorname{mod} p$.


-----Examples-----
Input
3

Output
1

Input
5

Output
2



-----Note-----

The only primitive root $\operatorname{mod} 3$ is 2.

The primitive roots $\operatorname{mod} 5$ are 2 and 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:


Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:


Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
-----Problem Statement-----
A classroom has several students, half of whom are boys and half of whom are girls. You need to arrange all of them in a line for the morning assembly such that the following conditions are satisfied:
- The students must be in order of non-decreasing height.
- Two boys or two girls must not be adjacent to each other.
You have been given the heights of the boys in the array $b$ and the heights of the girls in the array $g$. Find out whether you can arrange them in an order which satisfies the given conditions. Print "YES" if it is possible, or "NO" if it is not.
For example, let's say there are $n = 3$ boys and $n = 3$ girls, where the boys' heights are $b = [5, 3, 8]$ and the girls' heights are $g = [2, 4, 6]$. These students can be arranged in the order $[g_0, b_1, g_1, b_0, g_2, b_2]$, which is $[2, 3, 4, 5, 6, 8]$. Because this is in order of non-decreasing height, and no two boys or two girls are adjacent to each other, this satisfies the conditions. Therefore, the answer is "YES".

-----Input-----
- The first line contains an integer, $t$, denoting the number of test cases.
- The first line of each test case contains an integer, $n$, denoting the number of boys and girls in the classroom.
- The second line of each test case contains $n$ space separated integers, $b_1,b_2, ... b_n$, denoting the heights of the boys.
- The second line of each test case contains $n$ space separated integers, $g_1,g_2,... g_n$, denoting the heights of the girls.

-----Output-----
Print exactly $t$ lines. In the $i^{th}$ of them, print a single line containing "$YES$" without quotes if it is possible to arrange the students in the $i^{th}$ test case, or "$NO$" without quotes if it is not.

-----Constraints-----
- $1 \leq t \leq 10$
- $1 \leq n \leq 100$
- $1 \leq b_i, g_i \leq 100$

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

-----Sample Output-----
YES

-----EXPLANATION-----
The following arrangement would satisfy the given conditions: $[b_1, g_1, b_2, g_2]$. This is because the boys and girls and separated, and the height is in non-decreasing order.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once, during a lesson, Sasha got bored and decided to talk with his friends. Suddenly, he saw Kefa. Since we can talk endlessly about Kefa, we won't even start doing that. The conversation turned to graphs. Kefa promised Sasha to tell him about one interesting fact from graph theory if Sasha helps Kefa to count the number of beautiful trees. 

In this task, a tree is a weighted connected graph, consisting of n vertices and n-1 edges, and weights of edges are integers from 1 to m. Kefa determines the beauty of a tree as follows: he finds in the tree his two favorite vertices — vertices with numbers a and b, and counts the distance between them. The distance between two vertices x and y is the sum of weights of edges on the simple path from x to y. If the distance between two vertices a and b is equal to m, then the tree is beautiful.

Sasha likes graph theory, and even more, Sasha likes interesting facts, that's why he agreed to help Kefa. Luckily, Sasha is familiar with you the best programmer in Byteland. Help Sasha to count the number of beautiful trees for Kefa. Two trees are considered to be distinct if there is an edge that occurs in one of them and doesn't occur in the other one. Edge's weight matters.

Kefa warned Sasha, that there can be too many beautiful trees, so it will be enough to count the number modulo 10^9 + 7.

Input

The first line contains four integers n, m, a, b (2 ≤ n ≤ 10^6, 1 ≤ m ≤ 10^6, 1 ≤ a, b ≤ n, a ≠ b) — the number of vertices in the tree, the maximum weight of an edge and two Kefa's favorite vertices.

Output

Print one integer — the number of beautiful trees modulo 10^9+7.

Examples

Input


3 2 1 3


Output


5


Input


3 1 1 2


Output


2


Input


5 15 1 5


Output


345444

Note

There are 5 beautiful trees in the first example:

<image>

In the second example the following trees are beautiful:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cities in Berland. Each city has its index — an integer number from 1 to n. The capital has index r1. All the roads in Berland are two-way. The road system is such that there is exactly one path from the capital to each city, i.e. the road map looks like a tree. In Berland's chronicles the road map is kept in the following way: for each city i, different from the capital, there is kept number pi — index of the last city on the way from the capital to i.

Once the king of Berland Berl XXXIV decided to move the capital from city r1 to city r2. Naturally, after this the old representation of the road map in Berland's chronicles became incorrect. Please, help the king find out a new representation of the road map in the way described above.

Input

The first line contains three space-separated integers n, r1, r2 (2 ≤ n ≤ 5·104, 1 ≤ r1 ≠ r2 ≤ n) — amount of cities in Berland, index of the old capital and index of the new one, correspondingly.

The following line contains n - 1 space-separated integers — the old representation of the road map. For each city, apart from r1, there is given integer pi — index of the last city on the way from the capital to city i. All the cities are described in order of increasing indexes.

Output

Output n - 1 numbers — new representation of the road map in the same format.

Examples

Input

3 2 3
2 2


Output

2 3 

Input

6 2 4
6 1 2 4 2


Output

6 4 1 4 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kshitij has recently started solving problems on codechef. As he is real problem solving enthusiast, he wants continuous growth in number of problems solved per day.
He started with $a$  problems on first day. 
He solves $d$ problems more than previous day. But after every $k$ days , he increases $d$ by
$inc$ .
Can you guess how many questions he will solve on $nth $ day ?

-----Input:-----
- First line  contains $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input,five integers $a, d, k, n, inc$. 

-----Output:-----
For each testcase, output in a single line number of questions solved on $nth$ day.

-----Constraints-----
- $1 \leq T \leq 15$
- $1 \leq a \leq 99$
- $1 \leq d \leq 100$
- $1 \leq n \leq 10000$
- $1 \leq k \leq n$
- $0 \leq inc \leq 99$

-----Sample Input:-----
1
1 4 3 8 2

-----Sample Output:-----
43

-----EXPLANATION:-----
The number of questions solved in first 8 days is :
$1$ $5$ $9$ $15$ $21$ $27$ $35$ $43$ .
On first day he solved 1 problem . Here $d$ is  4 for first 3 days.
Then after 3 days $d$ increases by 2 (that is 6).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Innopolis University scientists continue to investigate the periodic table. There are n·m known elements and they form a periodic table: a rectangle with n rows and m columns. Each element can be described by its coordinates (r, c) (1 ≤ r ≤ n, 1 ≤ c ≤ m) in the table.

Recently scientists discovered that for every four different elements in this table that form a rectangle with sides parallel to the sides of the table, if they have samples of three of the four elements, they can produce a sample of the fourth element using nuclear fusion. So if we have elements in positions (r_1, c_1), (r_1, c_2), (r_2, c_1), where r_1 ≠ r_2 and c_1 ≠ c_2, then we can produce element (r_2, c_2).

 [Image] 

Samples used in fusion are not wasted and can be used again in future fusions. Newly crafted elements also can be used in future fusions.

Innopolis University scientists already have samples of q elements. They want to obtain samples of all n·m elements. To achieve that, they will purchase some samples from other laboratories and then produce all remaining elements using an arbitrary number of nuclear fusions in some order. Help them to find the minimal number of elements they need to purchase.


-----Input-----

The first line contains three integers n, m, q (1 ≤ n, m ≤ 200 000; 0 ≤ q ≤ min(n·m, 200 000)), the chemical table dimensions and the number of elements scientists already have.

The following q lines contain two integers r_{i}, c_{i} (1 ≤ r_{i} ≤ n, 1 ≤ c_{i} ≤ m), each describes an element that scientists already have. All elements in the input are different.


-----Output-----

Print the minimal number of elements to be purchased.


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

Output
0

Input
1 5 3
1 3
1 1
1 5

Output
2

Input
4 3 6
1 2
1 3
2 2
2 3
3 1
3 3

Output
1



-----Note-----

For each example you have a picture which illustrates it.

The first picture for each example describes the initial set of element samples available. Black crosses represent elements available in the lab initially.

The second picture describes how remaining samples can be obtained. Red dashed circles denote elements that should be purchased from other labs (the optimal solution should minimize the number of red circles). Blue dashed circles are elements that can be produced with nuclear fusion. They are numbered in order in which they can be produced.

Test 1

We can use nuclear fusion and get the element from three other samples, so we don't need to purchase anything.

 [Image] 

Test 2

We cannot use any nuclear fusion at all as there is only one row, so we have to purchase all missing elements.

 [Image] 

Test 3

There are several possible solutions. One of them is illustrated below.

Note that after purchasing one element marked as red it's still not possible to immidiately produce the middle element in the bottom row (marked as 4). So we produce the element in the left-top corner first (marked as 1), and then use it in future fusions.

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tira would like to join a multiplayer game with $n$ other players. Each player has a character with some features. There are a total of $k$ features, and each character has some subset of them. 

The similarity between two characters $A$ and $B$ is calculated as follows: for each feature $f$, if both $A$ and $B$ have feature $f$ or if none of them have feature $f$, the similarity increases by one.

Tira does not have a character yet. She would like to create a new, very original character so that the maximum similarity between Tira’s character and any other character is as low as possible.

Given the characters of the other players, your task is to create a character for Tira that fulfils the above requirement. If there are many possible characters, you can choose any of them.

-----Input-----
The first line of input contains two integers $n$ and $k$, where $1 \le n \le 10^5$ is the number of players (excluding Tira) and $1 \le k \le 20$ is the number of features.

Then follow $n$ lines describing the existing characters. Each of these $n$ lines contains a string of $k$ digits which are either $0$ or $1$. A $1$ in position $j$ means the character has the $j$’th feature, and a $0$ means that it does not have the $j$’th feature.

-----Output-----
Output a single line describing the features of Tira’s character in the same format as in the input. If there are multiple possible characters with the same smallest maximum similarity, any one of them will be accepted.

-----Examples-----
Sample Input:
3 5
01001
11100
10111
Sample Output:
00010

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You need to write a function, that returns the first non-repeated character in the given string.

For example for string `"test"` function should return `'e'`.  
For string `"teeter"` function should return `'r'`.  
  
If a string contains all unique characters, then return just the first character of the string.  
Example: for input `"trend"` function should return `'t'`  
  
You can assume, that the input string has always non-zero length.

If there is no repeating character, return `null` in JS or Java, and `None` in Python.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The closing ceremony of Squanch Code Cup is held in the big hall with *n*<=×<=*m* seats, arranged in *n* rows, *m* seats in a row. Each seat has two coordinates (*x*,<=*y*) (1<=≤<=*x*<=≤<=*n*, 1<=≤<=*y*<=≤<=*m*). 

There are two queues of people waiting to enter the hall: *k* people are standing at (0,<=0) and *n*·*m*<=-<=*k* people are standing at (0,<=*m*<=+<=1). Each person should have a ticket for a specific seat. If person *p* at (*x*,<=*y*) has ticket for seat (*x**p*,<=*y**p*) then he should walk |*x*<=-<=*x**p*|<=+<=|*y*<=-<=*y**p*| to get to his seat.

Each person has a stamina — the maximum distance, that the person agrees to walk. You should find out if this is possible to distribute all *n*·*m* tickets in such a way that each person has enough stamina to get to their seat.

Input Specification:
The first line of input contains two integers *n* and *m* (1<=≤<=*n*·*m*<=≤<=104) — the size of the hall.

The second line contains several integers. The first integer *k* (0<=≤<=*k*<=≤<=*n*·*m*) — the number of people at (0,<=0). The following *k* integers indicate stamina of each person there.

The third line also contains several integers. The first integer *l* (*l*<==<=*n*·*m*<=-<=*k*) — the number of people at (0,<=*m*<=+<=1). The following *l* integers indicate stamina of each person there.

The stamina of the person is a positive integer less that or equal to *n*<=+<=*m*.

Output Specification:
If it is possible to distribute tickets between people in the described manner print "YES", otherwise print "NO".

Demo Input:
['2 2\n3 3 3 2\n1 3\n', '2 2\n3 2 3 3\n1 2\n']

Demo Output:
['YES\n', 'NO\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Having read half of the book called "Storm and Calm" on the IT lesson, Innocentius was absolutely determined to finish the book on the maths lessons. All was fine until the math teacher Ms. Watkins saw Innocentius reading fiction books instead of solving equations of the fifth degree. As during the last maths class Innocentius suggested the algorithm of solving equations of the fifth degree in the general case, Ms. Watkins had no other choice but to give him a new task.

The teacher asked to write consecutively (without spaces) all words from the "Storm and Calm" in one long string *s*. She thought that a string is good if the number of vowels in the string is no more than twice more than the number of consonants. That is, the string with *v* vowels and *c* consonants is good if and only if *v*<=≤<=2*c*.

The task Innocentius had to solve turned out to be rather simple: he should find the number of the longest good substrings of the string *s*.

Input Specification:
The only input line contains a non-empty string *s* consisting of no more than 2·105 uppercase and lowercase Latin letters. We shall regard letters "a", "e", "i", "o", "u" and their uppercase variants as vowels.

Output Specification:
Print on a single line two numbers without a space: the maximum length of a good substring and the number of good substrings with this length. If no good substring exists, print "No solution" without the quotes.

Two substrings are considered different if their positions of occurrence are different. So if some string occurs more than once, then it should be counted more than once.

Demo Input:
['Abo\n', 'OEIS\n', 'auBAAbeelii\n', 'AaaBRAaaCAaaDAaaBRAaa\n', 'EA\n']

Demo Output:
['3 1\n', '3 1\n', '9 3\n', '18 4\n', 'No solution\n']

Note:
In the first sample there is only one longest good substring: "Abo" itself. The other good substrings are "b", "Ab", "bo", but these substrings have shorter length.

In the second sample there is only one longest good substring: "EIS". The other good substrings are: "S", "IS".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a string, $S$, of $n$ lowercase English letters where each character, $s_i$ ($0\leq i<n)$, denotes the letter at index $\boldsymbol{i}$ in $S$. We define an $(a,b,c,d)$ palindromic tuple of $S$ to be a sequence of indices in $S$ satisfying the following criteria:

$\boldsymbol{s_{a}}=\boldsymbol{s_{d}}$, meaning the characters located at indices $a$ and $d$ are the same.
$s_b=s_c$, meaning the characters located at indices $b$ and $c$ are the same.
$0\leq a\lt b\lt c\lt d\lt|s|$, meaning that $a$, $b$, $c$, and $d$ are ascending in value and are valid indices within string $S$.

Given $S$, find and print the number of $(a,b,c,d)$ tuples satisfying the above conditions. As this value can be quite large, print it modulo $(10^9+7)$.  

Function Description 

Complete the function shortPalindrome in the editor below.  

shortPalindrome has the following paramter(s): 

- string s: a string  

Returns 

- int: the number of tuples, modulo $(10^9+7)$  

Input Format

A single string, $S$. 

Constraints

$1\leq|s|\leq10^6$
It is guaranteed that $S$ only contains lowercase English letters.  

Sample Input 0

kkkkkkz

Sample Output 0

15

Explanation 0

The letter z will not be part of a valid tuple because you need at least two of the same character to satisfy the conditions defined above. Because all tuples consisting of four k's are valid, we just need to find the number of ways that we can choose four of the six k's. This means our answer is $\binom{6}{4}\mod(10^9+7)=15$.

Sample Input 1

ghhggh

Sample Output 1

4

Explanation 1

The valid tuples are:

$(0,1,2,3)$
$(0,1,2,4)$
$(1,3,4,5)$
$(2,3,4,5)$

Thus, our answer is $4\:\:\:\text{mod}\:(10^9+7)=4$.

Sample Input 0

kkkkkkz

Sample Output 0

15

Sample Input 1

abbaab

Sample Output 1

4

Sample Input 2
akakak

Sample Output 2
2

Explanation 2

Tuples possible are $(1,2,4,5)~and~(0,1,3,4)$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are batting at the pitch and all eyes are on you, the best player in all of IPL!
The opposing team will relentlessly bowl at you an infinite number of balls!

You notice that you only ever score a boundary on the M^{th} ball, if N mod M ≤ N/2, where N is the lucky number of your T-shirt. Now you wanna know how many boundaries will you hit in total? 

Formally, you are given a positive integer N and you need to find the number of positive integers M such that N mod M ≤ N/2.

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

- The first line contains a single integer T, which denotes the number of test cases. The description of each test case follows.
- The first and the only line of each test case contains a single integer N.

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

For each test case, print in a new line, the number of integers M which follow the above condition.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 2\cdot 10^{9}$

----- Sample Input 1 ------ 
1
3
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
For $ N = 3 $, $N$ $mod$ $M ≤ N/2 $ only for $M={1, 2, 3}$. Hence, the number of possible values of $M$ are 3.

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