vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given a binary matrix of dimensions  with R rows and C columns. Start from cell(0, 0), moving in the right direction. Perform the following operations: 
	If the value of matrix[i][j] is 0, then traverse in the same direction and check the next value.
	If the value of matrix[i][j] is 1, then update matrix[i][j] to 0 and change the current direction clockwise. ie - up, right, down, or left directions change to right, down, left, and up respectively.
Find the index of the cell where you will be forced to exit the matrix while performing the given traversal. 
Example 1:
Input:
matrix[][] = {{0,1},
              {1,0}}
R=2
C=2
Output: (1,1)
Explanation:
Example 2:
Input: 
matrix[][] = {{0, 1, 1, 1, 0},
                   {1, 0, 1, 0, 1},
              {1, 1, 1, 0, 0}}
R=3
C=5
Output: (2,0)
Explanation: We will leave the grid after visiting the index (2,0).
 
Your Task:
You don't need to read input or print anything. Complete the function endPoints() which take a 2D matrix[][] , an integer R and an integer C as input parameters and returns the index of the last cell before exiting the matrix. 
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)
Constraints:
1<= R,C<=1000
0<= matrix[i][j] <=1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are going out for a walk, when you suddenly encounter a monster. Fortunately, you have N katana (swords), Katana 1, Katana 2, …, Katana N, and can perform the following two kinds of attacks in any order:
 - Wield one of the katana you have. When you wield Katana i (1 ≤ i ≤ N), the monster receives a_i points of damage. The same katana can be wielded any number of times.
 - Throw one of the katana you have. When you throw Katana i (1 ≤ i ≤ N) at the monster, it receives b_i points of damage, and you lose the katana. That is, you can no longer wield or throw that katana.
The monster will vanish when the total damage it has received is H points or more. At least how many attacks do you need in order to vanish it in total?

-----Constraints-----
 - 1 ≤ N ≤ 10^5
 - 1 ≤ H ≤ 10^9
 - 1 ≤ a_i ≤ b_i ≤ 10^9
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N H
a_1 b_1
:
a_N b_N

-----Output-----
Print the minimum total number of attacks required to vanish the monster.

-----Sample Input-----
1 10
3 5

-----Sample Output-----
3

You have one katana. Wielding it deals 3 points of damage, and throwing it deals 5 points of damage. By wielding it twice and then throwing it, you will deal 3 + 3 + 5 = 11 points of damage in a total of three attacks, vanishing the monster.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
To help Lavanya learn all about binary numbers and binary sequences, her father has bought her a collection of square tiles, each of which has either a 0 or a 1 written on it. Her brother Nikhil has played a rather nasty prank. He has glued together pairs of tiles with 0 written on them. Lavanya now has square tiles with 1 on them and rectangular tiles with two 0's on them, made up of two square tiles with 0 stuck together). Thus, she can no longer make all possible binary sequences using these tiles.
To amuse herself, Lavanya has decided to pick a number $N$ and try and construct as many binary sequences of length $N$ as possible using her collection of tiles. For example if $N$ = 1, she can only make the sequence 1. For $N$=2, she can make 11 and 00. For $N$=4, there are 5 possibilities: 0011, 0000, 1001, 1100 and 1111.
Lavanya would like you to write a program to compute the number of arrangements possible with $N$ tiles so that she can verify that she has generated all of them. Since she cannot count beyond 15746, it is sufficient to report this number modulo 15746.

-----Input:-----
A single line with a single integer $N$.

-----Output:-----
A single integer indicating the number of binary sequences of length $N$, modulo 15746, that Lavanya can make using her tiles.

-----Constraints:-----
You may assume that $N \leq$ 1000000.

-----Sample Input:-----
4

-----Sample Output:-----
5

-----Explanation:-----
This corresponds to the example discussed above.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Task:
Make a function that converts a word to pig latin. The rules of pig latin are:

```
If the word has more than 3 letters:
  1. Take the first letter of a word and move it to the end
  2. Add -ay to the word
Otherwise leave the word alone.
```

Example: `hello` = `ellohay`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's consider some integer X. We will call the following sequence S a sequence generated by X:
for i = 1: S[i] = X 
for i > 1: S[i] equals to the minimal positive integer such that S[i] is not a divisor of S[i - 1]. If there is no such integer than S[i - 1] is the last element of S.

For example S = (10, 3, 2) is a sequence generated by 10.

Can you find the total sum of lengths of the sequnces generated by all the integers from A  to B inclusive.

Input
The only line contains two integers: A and B. (A ≤ B)

Output 
Output the only integer - answer to the question. It's guaranteed that this value can be stored in 64-bit integer.

Constraints 
1 < A ≤ B ≤ 10^17

SAMPLE INPUT
2 6

SAMPLE OUTPUT
12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.

For each i and j (1 \leq i \leq H, 1 \leq j \leq W), Square (i, j) is described by a character a_{i, j}. If a_{i, j} is `.`, Square (i, j) is an empty square; if a_{i, j} is `#`, Square (i, j) is a wall square. It is guaranteed that Squares (1, 1) and (H, W) are empty squares.

Taro will start from Square (1, 1) and reach (H, W) by repeatedly moving right or down to an adjacent empty square.

Find the number of Taro's paths from Square (1, 1) to (H, W). As the answer can be extremely large, find the count modulo 10^9 + 7.

Constraints

* H and W are integers.
* 2 \leq H, W \leq 1000
* a_{i, j} is `.` or `#`.
* Squares (1, 1) and (H, W) are empty squares.

Input

Input is given from Standard Input in the following format:


H W
a_{1, 1}\ldotsa_{1, W}
:
a_{H, 1}\ldotsa_{H, W}


Output

Print the number of Taro's paths from Square (1, 1) to (H, W), modulo 10^9 + 7.

Examples

Input

3 4
...#
.#..
....


Output

3


Input

5 2
..
.
..
.#
..


Output

0


Input

5 5
..#..
.....
...#
.....
..#..


Output

24


Input

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................


Output

345263555

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Our good friend Mole is trying to code a big message. He is typing on an unusual keyboard with characters arranged in following way:

Unfortunately Mole is blind, so sometimes it is problem for him to put his hands accurately. He accidentally moved both his hands with one position to the left or to the right. That means that now he presses not a button he wants, but one neighboring button (left or right, as specified in input).

We have a sequence of characters he has typed and we want to find the original message.

Input Specification:
First line of the input contains one letter describing direction of shifting ('L' or 'R' respectively for left or right).

Second line contains a sequence of characters written by Mole. The size of this sequence will be no more than 100. Sequence contains only symbols that appear on Mole's keyboard. It doesn't contain spaces as there is no space on Mole's keyboard.

It is guaranteed that even though Mole hands are moved, he is still pressing buttons on keyboard and not hitting outside it.

Output Specification:
Print a line that contains the original message.

Demo Input:
['R\ns;;upimrrfod;pbr\n']

Demo Output:
['allyouneedislove\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string that represents the postfix form of a valid mathematical expression. Convert it to its infix form.
Example:
Input:
ab*c+ 
Output: 
((a*b)+c)
Explanation: 
The above output is its valid infix form.
Your Task:
Complete the function string postToInfix(string post_exp), which takes a postfix string as input and returns its infix form.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
3<=post_exp.length()<=10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has created a special dividing machine that supports the below given operations on an array of positive integers.
There are two operations that Chef implemented on the machine.
Type 0 Operation

Update(L,R):
	for i = L to R:
		a[i] = a[i] / LeastPrimeDivisor(a[i])

Type 1 Operation

Get(L,R):
	result = 1
	for i = L to R:
		result = max(result, LeastPrimeDivisor(a[i]))
	return result;

The function LeastPrimeDivisor(x) finds the smallest prime divisor of a number. If the number does not have any prime divisors, then it returns 1.
Chef has provided you an array of size N, on which you have to apply M operations using the special machine. Each operation will be one of the above given two types. Your task is to implement the special dividing machine operations designed by Chef. Chef finds this task quite easy using his machine, do you too?

-----Input-----

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 
The first line of each test case contains two space-separated integers N, M, denoting the size of array A and the number of queries correspondingly.

The second line of each test case contains N space-separated integers A1, A2, ..., AN denoting the initial array for dividing machine.
Each of following M lines contain three space-separated integers  type, L, R - the type of operation (0 - Update operation, 1 - Get operation), and the arguments of function, respectively

-----Output-----
For each test case, output answer of each query of type 1 (Get query) separated by space. Each test case from the same file should start from the new line.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ Ai ≤ 106
- 1 ≤ L ≤ R ≤ N
- 0 ≤ type ≤ 1
-  Sum of M over all test cases in a single test file does not exceed 106

-----Subtasks-----
Subtask #1: (10 points) 
- 1 ≤ N, M ≤ 103

Subtask #2: (25 points)
- 1 ≤ N, M ≤ 105
-  Ai is a prime number. 

Subtask #3: (65 points)
- 1 ≤ N, M ≤ 105

-----Example-----
Input:
2
6 7
2 5 8 10 3 44
1 2 6
0 2 3
1 2 6
0 4 6
1 1 6
0 1 6
1 4 6
2 2
1 3
0 2 2
1 1 2
Output:
5 3 5 11
1

-----Explanation-----
Example case 1.The states of array A after each Update-operation:
A: = [2 1 4 10 3 44]
A: = [2 1 4 5 1 22]
A: = [1 1 2 1 1 11]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Implement a function called makeAcronym that returns the first letters of each word in a passed in string.

Make sure the letters returned are uppercase.

If the value passed in is not a string return 'Not a string'.

If the value passed in is a string which contains characters other than spaces and alphabet letters, return 'Not letters'.

If the string is empty, just return the string itself: "".

**EXAMPLES:**
```
'Hello codewarrior' -> 'HC'

'a42' -> 'Not letters'

42 -> 'Not a string'

[2,12] -> 'Not a string'

{name: 'Abraham'} -> 'Not a string'
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given N points of the form (x_{i}, y_{i}) on a 2-D plane.

From each point, you draw 2 lines one horizontal and one vertical. Now some of the lines may overlap each other, therefore you are required to print the number of distinct lines you can see on the plane.

Note:
Two horizontal lines are distinct if they pass through different y coordinates.
Two vertical lines are distinct if they pass through different x coordinates.

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains a single integer N, the number of points.
- The next N lines contain two space separated integers x_{i}, y_{i}, the coordinate of the i^{th} point.

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

For each testcase, output in a single line the number of distinct lines that can be seen on the plane.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$0 ≤ X_{i}, Y_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases is atmost $10^{5}$.

----- Sample Input 1 ------ 
3
4
1 1
1 0
0 1
0 0
5
0 0
0 1
0 2
0 3
0 4
1
10 10
----- Sample Output 1 ------ 
4
6
2
----- explanation 1 ------ 
Test Case $1$: There are $2$ horizontal lines passing through $Y = 0$ and $Y = 1$, and $2$  vertical lines passing through $X = 0$ and $X = 1$.

.png =500x500)

Test Case $2$: There are $5$ horizontal lines passing through $Y = 0, Y = 1, Y = 2, Y = 3$ and $Y = 4$ and $1$ vertical line passing through $X = 0$.

Test Case $3$: There is $1$ horizontal line passing through $Y = 10$ and $1$ vertical line passing through $X = 10$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n soldiers standing in a line. Each soldier is assigned a unique rating value.
You have to form a team of 3 soldiers amongst them under the following rules:

Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
A team is valid if:  (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).
 
Example 1:
Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

Example 2:
Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:
Input: rating = [1,2,3,4]
Output: 4

 
Constraints:

n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Teacher thinks that we make a lot of progress. Now we are even allowed to use decimal notation instead of counting sticks. After the test the teacher promised to show us a "very beautiful number". But the problem is, he's left his paper with the number in the teachers' office.

The teacher remembers that the "very beautiful number" was strictly positive, didn't contain any leading zeroes, had the length of exactly *p* decimal digits, and if we move the last digit of the number to the beginning, it grows exactly *x* times. Besides, the teacher is sure that among all such numbers the "very beautiful number" is minimal possible.

The teachers' office isn't near and the teacher isn't young. But we've passed the test and we deserved the right to see the "very beautiful number". Help to restore the justice, find the "very beautiful number" for us!

Input Specification:
The single line contains integers *p*, *x* (1<=≤<=*p*<=≤<=106,<=1<=≤<=*x*<=≤<=9).

Output Specification:
If the teacher's made a mistake and such number doesn't exist, then print on a single line "Impossible" (without the quotes). Otherwise, print the "very beautiful number" without leading zeroes.

Demo Input:
['6 5\n', '1 2\n', '6 4\n']

Demo Output:
['142857', 'Impossible\n', '102564']

Note:
Sample 1: 142857·5 = 714285.

Sample 2: The number that consists of a single digit cannot stay what it is when multiplied by 2, thus, the answer to the test sample is "Impossible".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alex studied well and won the trip to student camp Alushta, located on the seashore. 

Unfortunately, it's the period of the strong winds now and there is a chance the camp will be destroyed! Camp building can be represented as the rectangle of n + 2 concrete blocks height and m blocks width.

Every day there is a breeze blowing from the sea. Each block, except for the blocks of the upper and lower levers, such that there is no block to the left of it is destroyed with the probability <image>. Similarly, each night the breeze blows in the direction to the sea. Thus, each block (again, except for the blocks of the upper and lower levers) such that there is no block to the right of it is destroyed with the same probability p. Note, that blocks of the upper and lower level are indestructible, so there are only n·m blocks that can be destroyed.

The period of the strong winds will last for k days and k nights. If during this period the building will split in at least two connected components, it will collapse and Alex will have to find another place to spend summer.

Find the probability that Alex won't have to look for other opportunities and will be able to spend the summer in this camp.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 1500) that define the size of the destructible part of building.

The second line of the input contains two integers a and b (1 ≤ a ≤ b ≤ 109) that define the probability p. It's guaranteed that integers a and b are coprime. 

The third line contains a single integer k (0 ≤ k ≤ 100 000) — the number of days and nights strong wind will blow for.

Output

Consider the answer as an irreducible fraction is equal to <image>. Print one integer equal to <image>. It's guaranteed that within the given constraints <image>.

Examples

Input

2 2
1 2
1


Output

937500007


Input

5 1
3 10
1


Output

95964640


Input

3 3
1 10
5


Output

927188454

Note

In the first sample, each of the four blocks is destroyed with the probability <image>. There are 7 scenarios that result in building not collapsing, and the probability we are looking for is equal to <image>, so you should print <image>

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sorting arrays is traditionally associated with high-level languages. How hard can it be in Roco? Sort the given array in non-descending order.

Input

The first line of input contains an integer n (1 ≤ n ≤ 100) — the size of the array. The following n lines contain the elements of the array, one per line. Each element of the array is an integer between 1 and 100, inclusive. The array might contain duplicate elements.

Output

Output space-separated elements of the sorted array.

Examples

Input

5
7
1
9
7
3


Output

1 3 7 7 9 


Input

10
100
1
100
1
100
1
100
1
100
1


Output

1 1 1 1 1 100 100 100 100 100 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:


       Only one letter can be changed at a time.
       Each transformed word must exist in the word list. Note that beginWord is not a transformed word.


Note:


       Return 0 if there is no such transformation sequence.
       All words have the same length.
       All words contain only lowercase alphabetic characters.
       You may assume no duplicates in the word list.
       You may assume beginWord and endWord are non-empty and are not the same.


Example 1:


Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.


Example 2:


Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.



A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.



The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.


Example 1:

Input: "aba", "cdc", "eae"
Output: 3



Note:

All the given strings' lengths will not exceed 10.
The length of the given list will be in the range of [2, 50].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Department of economic development of IT City created a model of city development till year 2100.

To prepare report about growth perspectives it is required to get growth estimates from the model.

To get the growth estimates it is required to solve a quadratic equation. Since the Department of economic development of IT City creates realistic models only, that quadratic equation has a solution, moreover there are exactly two different real roots.

The greater of these roots corresponds to the optimistic scenario, the smaller one corresponds to the pessimistic one. Help to get these estimates, first the optimistic, then the pessimistic one.


-----Input-----

The only line of the input contains three integers a, b, c ( - 1000 ≤ a, b, c ≤ 1000) — the coefficients of ax^2 + bx + c = 0 equation.


-----Output-----

In the first line output the greater of the equation roots, in the second line output the smaller one. Absolute or relative error should not be greater than 10^{ - 6}.


-----Examples-----
Input
1 30 200

Output
-10.000000000000000
-20.000000000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We all are aware of Gaurav and his love for "weird" recurrences.
Recently, he came up with another of his wierd recurrence namely the "12321" recurrence.
F(n)= 1 * F(n-1) + 2 * F(n-2) + 3 * F(n-3) + 2 * F(n-4) + 1 * F(n-5)
He intends to make the use of his new "weird" recurrence for his latest encryption technique. 
Rajat, an ethical hacker and a friend of Gaurav claimed that his encryption technique has loopholes and can be broken in no time.
To prove his claim, Rajat needs to find the Nth number of the sequence formed using the recursion as fast as possible.   

Using his knowledge of hacking, he was able to get some seed values of the recurrence that Gaurav intends to use in his encryption.
F(1)=1 
F(2)=2 
F(3)=3 
F(4)=2 
F(5)=1

Help Rajat hack Gaurav's recurrence by your programming skills. Your hack will decide the future of "Cryptography".
Input Format:
First line will contain T, the number of test cases.
Following T lines contain a single integer n.

Output Format: 
Output a single line for each test case, denoting the value of F(n)%(10000007).

Scoring Criteria:
20 Points: T ≤ 10 and 1 ≤ N ≤ 25
50 Points: T ≤ 1000 and 2 ≤ N ≤ 100000
90 Points: T ≤ 10000 and 2 ≤ N ≤ 10^(18)

SAMPLE INPUT
2
10
29

SAMPLE OUTPUT
524
8647330

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