vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ishaan has bought a new gun. He is practicing his shooting, but he has to reload his gun again and again.
You are given his shooting a bullet and reloading activity in the form of a string s.
String s consists of 2 type of distinct characters: 'S' stands for shooting one bullet whereas 'R' stands for reloading the gun.
You are also given an integer n, which is the bullet capacity of the gun. Each time Ishaan reloads the gun, it is filled up to n bullets.
Given the string s and integer n, find out whether the activities are valid or not.
Assume that the gun is loaded upto its full capacity in the beginning of each test case.
Example 1:
Input:
s = "SSSRSRSS", n = 3
Output: 1
Explanation: He has 3 bullets at the start,
fires 3, reloades 3 bullets again, fires 1,
reloades 3 and then fires 2.
Ã¢â¬â¹Example 2:
Input: 
s = "SSSSR", n = 3
Output: 0
Explanation: He has 3 bullets at the start
and tries to fire 4 without reloading. 
Hence, not a valid activity.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isValid() which takes the string s and the integer n as inputs and returns true if the string denotes a valid activity. Else, it returns false.
Expected Time Complexity: O(|s|).
Expected Auxiliary Space: O(1).
Constraints:
1<=|s|<=10^{5}
1<=n<=10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a_1, a_2, \dots , a_n$, which is sorted in non-decreasing order ($a_i \le a_{i + 1})$. 

Find three indices $i$, $j$, $k$ such that $1 \le i < j < k \le n$ and it is impossible to construct a non-degenerate triangle (a triangle with nonzero area) having sides equal to $a_i$, $a_j$ and $a_k$ (for example it is possible to construct a non-degenerate triangle with sides $3$, $4$ and $5$ but impossible with sides $3$, $4$ and $7$). If it is impossible to find such triple, report it.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains one integer $n$ ($3 \le n \le 5 \cdot 10^4$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le 10^9$; $a_{i - 1} \le a_i$) — the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print the answer to it in one line.

If there is a triple of indices $i$, $j$, $k$ ($i < j < k$) such that it is impossible to construct a non-degenerate triangle having sides equal to $a_i$, $a_j$ and $a_k$, print that three indices in ascending order. If there are multiple answers, print any of them.

Otherwise, print -1.


-----Example-----
Input
3
7
4 6 11 11 15 18 20
4
10 10 10 11
3
1 1 1000000000

Output
2 3 6
-1
1 2 3



-----Note-----

In the first test case it is impossible with sides $6$, $11$ and $18$. Note, that this is not the only correct answer.

In the second test case you always can construct a non-degenerate triangle.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasily the bear has two favorite integers n and k and a pencil. Besides, he's got k jars with different water color paints. All jars are numbered in some manner from 1 to k, inclusive. The jar number i contains the paint of the i-th color. 

Initially the bear took a pencil and drew four segments on the coordinate plane. All of them end at point (0, 0). They begin at: (0, 2n), (0, - 2n), (2n, 0), ( - 2n, 0). Then for each i = 1, 2, ..., n, the bear drew two squares. The first square has the following vertex coordinates: (2i, 0), ( - 2i, 0), (0, - 2i), (0, 2i). The second square has the following vertex coordinates: ( - 2i - 1, - 2i - 1), ( - 2i - 1, 2i - 1), (2i - 1, - 2i - 1), (2i - 1, 2i - 1). After that, the bear drew another square: (1, 0), ( - 1, 0), (0, - 1), (0, 1). All points mentioned above form the set of points A.

<image>

The sample of the final picture at n = 0

<image>

The sample of the final picture at n = 2

The bear decided to paint the resulting picture in k moves. The i-th move consists of the following stages: 

  1. The bear chooses 3 distinct points in set А so that any pair of the chosen points has a segment on the picture between them. The chosen points and segments mark the area that mustn't contain any previously painted points. 
  2. The bear paints the area bounded by the chosen points and segments the i-th color. 



Note that after the k-th move some parts of the picture can stay unpainted.

The bear asked you to calculate, how many distinct ways there are to paint his picture. A way to paint the picture is a sequence of three-element sets of points he chose on each step. Two sequences are considered distinct if there is such number i (1 ≤ i ≤ k), that the i-th members of these sequences do not coincide as sets. As the sought number can be rather large, you only need to calculate the remainder after dividing it by number 1000000007 (109 + 7).

Input

The first line contains two integers n and k, separated by a space (0 ≤ n, k ≤ 200).

Output

Print exactly one integer — the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

0 0


Output

1


Input

0 1


Output

8


Input

0 2


Output

32


Input

1 1


Output

32

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today Peter has got an additional homework for tomorrow. The teacher has given three integers to him: n, m and k, and asked him to mark one or more squares on a square grid of size n × m. 

The marked squares must form a connected figure, and there must be exactly k triples of marked squares that form an L-shaped tromino — all three squares are inside a 2 × 2 square.

The set of squares forms a connected figure if it is possible to get from any square to any other one if you are allowed to move from a square to any adjacent by a common side square.

Peter cannot fulfill the task, so he asks you for help. Help him to create such figure.

Input

Input data contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 100).

Each of the following t test cases is described by a line that contains three integers: n, m and k (3 ≤ n, m, n × m ≤ 105, 0 ≤ k ≤ 109).

The sum of values of n × m for all tests in one input data doesn't exceed 105.

Output

For each test case print the answer.

If it is possible to create such figure, print n lines, m characters each, use asterisk '*' to denote the marked square, and dot '.' to denote the unmarked one.

If there is no solution, print -1.

Print empty line between test cases.

Example

Input

3
3 3 4
3 3 5
3 3 3


Output

.*.
***
.*.

**.
**.
*..

.*.
***
*..

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
HDD hard drives group data by sectors. All files are split to fragments and each of them are written in some sector of hard drive. Note the fragments can be written in sectors in arbitrary order.

One of the problems of HDD hard drives is the following: the magnetic head should move from one sector to another to read some file.

Find the time need to read file split to n fragments. The i-th sector contains the f_{i}-th fragment of the file (1 ≤ f_{i} ≤ n). Note different sectors contains the different fragments. At the start the magnetic head is in the position that contains the first fragment. The file are reading in the following manner: at first the first fragment is read, then the magnetic head moves to the sector that contains the second fragment, then the second fragment is read and so on until the n-th fragment is read. The fragments are read in the order from the first to the n-th.

It takes |a - b| time units to move the magnetic head from the sector a to the sector b. Reading a fragment takes no time.


-----Input-----

The first line contains a positive integer n (1 ≤ n ≤ 2·10^5) — the number of fragments.

The second line contains n different integers f_{i} (1 ≤ f_{i} ≤ n) — the number of the fragment written in the i-th sector.


-----Output-----

Print the only integer — the number of time units needed to read the file.


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

Output
3

Input
5
1 3 5 4 2

Output
10



-----Note-----

In the second example the head moves in the following way:  1->2 means movement from the sector 1 to the sector 5, i.e. it takes 4 time units  2->3 means movement from the sector 5 to the sector 2, i.e. it takes 3 time units  3->4 means movement from the sector 2 to the sector 4, i.e. it takes 2 time units  4->5 means movement from the sector 4 to the sector 3, i.e. it takes 1 time units 

So the answer to the second example is 4 + 3 + 2 + 1 = 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Longest Palindromic Substring (Linear)

A palindrome is a word, phrase, or sequence that reads the same backward as forward, e.g.,
'madam' or 'racecar'. Even the letter 'x' is considered a palindrome. 

For this Kata, you are given a string ```s```. Write a function that returns the longest _contiguous_ palindromic substring in ```s``` (it could be the entire string). In the event that there are multiple longest palindromic substrings, return the first to occur.

I'm not trying to trick you here:
- You can assume that all inputs are valid strings.
- Only the letters a-z will be used, all lowercase (your solution should, in theory, extend to more than just the letters a-z though). 

**NOTE:** Quadratic asymptotic complexity _(O(N^2))_ or above will __NOT__ work here.

-----

## Examples

### Basic Tests

```
Input: "babad"
Output: "bab"
(Note: "bab" occurs before "aba")
```
```
Input: "abababa"
Output: "abababa"
```
```
Input: "cbbd"
Output: "bb"
```

### Edge Cases

```
Input: "ab"
Output: "a"
```
```
Input: ""
Output: ""
```
-----

## Testing

Along with the example tests given:

 - There are **500** tests using strings of length in range [1 - 1,000]
 - There are **50** tests using strings of length in range [1,000 - 10,000]
 - There are **5** tests using strings of length in range [10,000 - 100,000]
 
All test cases can be passed within 10 seconds, but non-linear solutions will time out every time. _Linear performance is essential_. 

## Good Luck!

-----

This problem was inspired by [this](https://leetcode.com/problems/longest-palindromic-substring/) challenge on LeetCode. Except this is the performance version :^)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During the lesson small girl Alyona works with one famous spreadsheet computer program and learns how to edit tables.

Now she has a table filled with integers. The table consists of n rows and m columns. By a_{i}, j we will denote the integer located at the i-th row and the j-th column. We say that the table is sorted in non-decreasing order in the column j if a_{i}, j ≤ a_{i} + 1, j for all i from 1 to n - 1.

Teacher gave Alyona k tasks. For each of the tasks two integers l and r are given and Alyona has to answer the following question: if one keeps the rows from l to r inclusive and deletes all others, will the table be sorted in non-decreasing order in at least one column? Formally, does there exist such j that a_{i}, j ≤ a_{i} + 1, j for all i from l to r - 1 inclusive.

Alyona is too small to deal with this task and asks you to help!


-----Input-----

The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 100 000) — the number of rows and the number of columns in the table respectively. Note that your are given a constraint that bound the product of these two integers, i.e. the number of elements in the table.

Each of the following n lines contains m integers. The j-th integers in the i of these lines stands for a_{i}, j (1 ≤ a_{i}, j ≤ 10^9).

The next line of the input contains an integer k (1 ≤ k ≤ 100 000) — the number of task that teacher gave to Alyona.

The i-th of the next k lines contains two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n).


-----Output-----

Print "Yes" to the i-th line of the output if the table consisting of rows from l_{i} to r_{i} inclusive is sorted in non-decreasing order in at least one column. Otherwise, print "No".


-----Example-----
Input
5 4
1 2 3 5
3 1 3 2
4 5 2 3
5 5 3 2
4 4 3 4
6
1 1
2 5
4 5
3 5
1 3
1 5

Output
Yes
No
Yes
Yes
Yes
No



-----Note-----

In the sample, the whole table is not sorted in any column. However, rows 1–3 are sorted in column 1, while rows 4–5 are sorted in column 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Function Descriptions=====
group()

A group() expression returns one or more subgroups of the match.
Code

>>> import re
>>> m = re.match(r'(\w+)@(\w+)\.(\w+)','username@hackerrank.com')
>>> m.group(0)       # The entire match 
'username@hackerrank.com'
>>> m.group(1)       # The first parenthesized subgroup.
'username'
>>> m.group(2)       # The second parenthesized subgroup.
'hackerrank'
>>> m.group(3)       # The third parenthesized subgroup.
'com'
>>> m.group(1,2,3)   # Multiple arguments give us a tuple.
('username', 'hackerrank', 'com')

groups()

A groups() expression returns a tuple containing all the subgroups of the match.
Code

>>> import re
>>> m = re.match(r'(\w+)@(\w+)\.(\w+)','username@hackerrank.com')
>>> m.groups()
('username', 'hackerrank', 'com')

groupdict()

A groupdict() expression returns a dictionary containing all the named subgroups of the match, keyed by the subgroup name.
Code

>>> m = re.match(r'(?P<user>\w+)@(?P<website>\w+)\.(?P<extension>\w+)','myname@hackerrank.com')
>>> m.groupdict()
{'website': 'hackerrank', 'user': 'myname', 'extension': 'com'}

=====Problem Statement=====
You are given a string S.
Your task is to find the first occurrence of an alphanumeric character in (read from left to right) that has consecutive repetitions. 

=====Input Format=====
A single line of input containing the string S.

=====Constraints=====
0<len(S)<100

=====Output Format=====
Print the first occurrence of the repeating character. If there are no repeating characters, print -1.

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

Chef likes inequalities. Please help him to solve next one.
Given four integers a, b, c, d. Find number of solutions x < y, where a ≤ x ≤ b and c ≤ y ≤ d and x, y integers.

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

The first line contains an integer T denoting number of tests.
First line of each test case contains four positive integer numbers a, b, c and d.

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

For each test case, output a single number each in separate line denoting number of integer solutions as asked in the problem.

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

$1 ≤ T ≤ 20 $
$1 ≤ a, b, c, d ≤ 10^{6}$

------ Subtasks ------ 

$Subtask #1: (30 points)  1 ≤ a, b, c, d ≤ 10^{3}.$
$Subtask #2: (70 points)  Original constraints.$

----- Sample Input 1 ------ 
1
2 3 3 4
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 

----- Sample Input 2 ------ 
1
2 999999 1 1000000
----- Sample Output 2 ------ 
499998500001
----- explanation 2 ------

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Our Tanya is Crying Out Loud

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Right now she actually isn't. But she will be, if you don't solve this problem.

You are given integers *n*, *k*, *A* and *B*. There is a number *x*, which is initially equal to *n*. You are allowed to perform two types of operations: 
 1.  Subtract 1 from *x*. This operation costs you *A* coins. 1.  Divide *x* by *k*. Can be performed only if *x* is divisible by *k*. This operation costs you *B* coins.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=2·109).

The second line contains a single integer *k* (1<=≤<=*k*<=≤<=2·109).

The third line contains a single integer *A* (1<=≤<=*A*<=≤<=2·109).

The fourth line contains a single integer *B* (1<=≤<=*B*<=≤<=2·109).

Output Specification:
Output a single integer — the minimum amount of coins you have to pay to make *x* equal to 1.

Demo Input:
['9\n2\n3\n1\n', '5\n5\n2\n20\n', '19\n3\n4\n2\n']

Demo Output:
['6\n', '8\n', '12\n']

Note:
In the first testcase, the optimal strategy is as follows: 
 -  Subtract 1 from *x* (9 → 8) paying 3 coins. -  Divide *x* by 2 (8 → 4) paying 1 coin. -  Divide *x* by 2 (4 → 2) paying 1 coin. -  Divide *x* by 2 (2 → 1) paying 1 coin. 
The total cost is 6 coins.

In the second test case the optimal strategy is to subtract 1 from *x* 4 times paying 8 coins in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr[] of n integers containing only 0 and 1. Write a program to find the minimum toggles (switch from 0 to 1 or vice-versa) required such the array the array become partitioned, i.e., it has first 0s then 1s. There should be at least one 0 in the beginning, and there can be zero or more 1s in the end.
Example 1:
Input: n = 5
arr = {1, 0, 1, 1, 0}
Output: 2
Explaination: The changed array will be 
{0, 0, 1, 1, 1}. So the number of toggles 
here required is 2.
Example 2:
Input: n = 7
arr = {0, 1, 0, 0, 1, 1, 1}
Output: 1
Explaination: The changed array will be 
{0, 0, 0, 0, 1, 1, 1}. Required toggles are 1.
Your Task:
You do not need to read input or print output. Your task is to complete the function minToggle() which takes n and arr as input parameters and returns the minimum number of toggles required to modify the array. 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ n ≤ 10^{5}
1 ≤ arr[i] ≤ 100

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
Little Petya likes to play a lot. Most of all he likes to play a game «Holes». This is a game for one person with following rules:

There are *N* holes located in a single row and numbered from left to right with numbers from 1 to *N*. Each hole has it's own power (hole number *i* has the power *a**i*). If you throw a ball into hole *i* it will immediately jump to hole *i*<=+<=*a**i*, then it will jump out of it and so on. If there is no hole with such number, the ball will just jump out of the row. On each of the *M* moves the player can perform one of two actions: 
 -  Set the power of the hole *a* to value *b*. -  Throw a ball into the hole *a* and count the number of jumps of a ball before it jump out of the row and also write down the number of the hole from which it jumped out just before leaving the row. 
Petya is not good at math, so, as you have already guessed, you are to perform all computations.

Input Specification:
The first line contains two integers *N* and *M* (1<=≤<=*N*<=≤<=105, 1<=≤<=*M*<=≤<=105) — the number of holes in a row and the number of moves. The second line contains *N* positive integers not exceeding *N* — initial values of holes power. The following *M* lines describe moves made by Petya. Each of these line can be one of the two types: 
 -  0 *a* *b* -  1 *a*

Output Specification:
For each move of the type 1 output two space-separated numbers on a separate line — the number of the last hole the ball visited before leaving the row and the number of jumps it made.

Demo Input:
['8 5\n1 1 1 1 1 2 8 2\n1 1\n0 1 3\n1 1\n0 3 4\n1 2\n']

Demo Output:
['8 7\n8 5\n7 3\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya has a sequence of cubes and exactly one integer is written on each cube. Vasya exhibited all his cubes in a row. So the sequence of numbers written on the cubes in the order from the left to the right equals to *a*1,<=*a*2,<=...,<=*a**n*.

While Vasya was walking, his little brother Stepan played with Vasya's cubes and changed their order, so now the sequence of numbers written on the cubes became equal to *b*1,<=*b*2,<=...,<=*b**n*. 

Stepan said that he swapped only cubes which where on the positions between *l* and *r*, inclusive, and did not remove or add any other cubes (i. e. he said that he reordered cubes between positions *l* and *r*, inclusive, in some way).

Your task is to determine if it is possible that Stepan said the truth, or it is guaranteed that Stepan deceived his brother.

Input Specification:
The first line contains three integers *n*, *l*, *r* (1<=≤<=*n*<=≤<=105, 1<=≤<=*l*<=≤<=*r*<=≤<=*n*) — the number of Vasya's cubes and the positions told by Stepan.

The second line contains the sequence *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=*n*) — the sequence of integers written on cubes in the Vasya's order.

The third line contains the sequence *b*1,<=*b*2,<=...,<=*b**n* (1<=≤<=*b**i*<=≤<=*n*) — the sequence of integers written on cubes after Stepan rearranged their order.

It is guaranteed that Stepan did not remove or add other cubes, he only rearranged Vasya's cubes.

Output Specification:
Print "LIE" (without quotes) if it is guaranteed that Stepan deceived his brother. In the other case, print "TRUTH" (without quotes).

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

Demo Output:
['TRUTH\n', 'LIE\n', 'TRUTH\n']

Note:
In the first example there is a situation when Stepan said the truth. Initially the sequence of integers on the cubes was equal to [3, 4, 2, 3, 1]. Stepan could at first swap cubes on positions 2 and 3 (after that the sequence of integers on cubes became equal to [3, 2, 4, 3, 1]), and then swap cubes in positions 3 and 4 (after that the sequence of integers on cubes became equal to [3, 2, 3, 4, 1]).

In the second example it is not possible that Stepan said truth because he said that he swapped cubes only between positions 1 and 2, but we can see that it is guaranteed that he changed the position of the cube which was on the position 3 at first. So it is guaranteed that Stepan deceived his brother.

In the third example for any values *l* and *r* there is a situation when Stepan said the truth.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S that contains only digits (0-9) and an integer target, return all possible strings to insert the binary operator ' + ', ' - ', or ' * ' between the digits of S so that the resultant expression evaluates to the target value.
Note:
 Operands in the returned expressions should not contain leading zeros. For example, 2 + 03 is not allowed whereas 20 + 3 is fine. It is allowed to not insert any of the operators.
If no solution is found, return an empty string array.
Example 1:
Input:
S = "123"
target = 6
Output: { "1*2*3", "1+2+3"}
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.
Example 2:
Input:
S = "3456237490"
target = 9191
Output: { } 
Explanation: There are no expressions that can be created from "3456237490"  to evaluate to 9191.
Example 3:
Input:
S = "12"
target = 12
Output: { "12"} 
Explanation: S itself matches the target. No other strings are possible.
Your Task:
You don't need to read input or print anything. Your task is to complete the function addOperators() which takes string S and integer target as parameters and returns a list of strings that contains all valid possibilities.
Expected Time Complexity: O(|S|*4^{|}^{S|})
Expected Auxiliary Space: O(|s|*3^{|S|})
Constraints:
1 ≤ |S| ≤ 10
S consists of only digits.
-2^{31 }≤ target ≤ 2^{31}-1

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