vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Jzzhu and Sequences

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Jzzhu has invented a kind of sequences, they meet the following property:

You are given *x* and *y*, please calculate *f**n* modulo 1000000007 (109<=+<=7).

Input Specification:
The first line contains two integers *x* and *y* (|*x*|,<=|*y*|<=≤<=109). The second line contains a single integer *n* (1<=≤<=*n*<=≤<=2·109).

Output Specification:
Output a single integer representing *f**n* modulo 1000000007 (109<=+<=7).

Demo Input:
['2 3\n3\n', '0 -1\n2\n']

Demo Output:
['1\n', '1000000006\n']

Note:
In the first sample, *f*<sub class="lower-index">2</sub> = *f*<sub class="lower-index">1</sub> + *f*<sub class="lower-index">3</sub>, 3 = 2 + *f*<sub class="lower-index">3</sub>, *f*<sub class="lower-index">3</sub> = 1.

In the second sample, *f*<sub class="lower-index">2</sub> =  - 1;  - 1 modulo (10<sup class="upper-index">9</sup> + 7) equals (10<sup class="upper-index">9</sup> + 6).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a grid G containing R rows (numbered from 1 to R, top to bottom) and C columns (numbered from 1 to C, left to right) of uppercase characters. The character in the r^{th} row and the c^{th} column is denoted by G_{r, c}. You also have Q strings containing uppercase characters. For each of the string, you want to find the number of occurrences of the string in the grid.

An occurrence of string S in the grid is counted if S can be constructed by starting at one of the cells in the grid, going right 0 or more times, and then going down 0 or more times. Two occurrences are different if the set of cells used to construct the string is different. Formally, for each string S, you would like to count the number of tuples ⟨ r, c, Δ r, Δ c ⟩ such that: 

  * 1 ≤ r ≤ R and r ≤ r + Δ r ≤ R 
  * 1 ≤ c ≤ C and c ≤ c + Δ c ≤ C 
  * S = G_{r, c} G_{r, c + 1} ... G_{r, c + Δ c} G_{r + 1, c + Δ c} ... G_{r + Δ r, c + Δ c} 

Input

Input begins with a line containing three integers: R C Q (1 ≤ R, C ≤ 500; 1 ≤ Q ≤ 200 000) representing the size of the grid and the number of strings, respectively. The next R lines each contains C uppercase characters representing the grid. The c^{th} character on the r^{th} line is G_{r, c}. The next Q lines each contains a string S containing uppercase characters. The length of this string is a positive integer not more than 200 000. The sum of the length of all Q strings combined is not more than 200 000.

Output

For each query in the same order as input, output in a line an integer representing the number of occurrences of the string in the grid.

Examples

Input


3 3 5
ABC
BCD
DAB
ABC
BC
BD
AC
A


Output


2
3
1
0
2


Input


2 3 3
AAA
AAA
A
AAA
AAAAA


Output


6
4
0

Note

Explanation for the sample input/output #1

  * There are 2 occurrences of "ABC", represented by the tuples ⟨ 1, 1, 1, 1 ⟩ and ⟨ 1, 1, 0, 2 ⟩. 
  * There are 3 occurrences of "BC", represented by the tuples ⟨ 1, 2, 0, 1 ⟩, ⟨ 1, 2, 1, 0 ⟩, and ⟨ 2, 1, 0, 1 ⟩. 
  * There is 1 occurrence of "BD", represented by the tuple ⟨ 2, 1, 1, 0 ⟩. 
  * There is no occurrence of "AC". 
  * There are 2 occurrences of "A", represented by the tuples ⟨ 1, 1, 0, 0 ⟩ and ⟨ 3, 2, 0, 0 ⟩.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s. Can you make it a palindrome by deleting exactly one character? Note that size of the string after deletion would be one less than it was before. 

-----Input-----
First line of the input contains a single integer T denoting number of test cases.
For each test case, you are given a single line containing string  s. 

-----Output-----
For each test case, print YES or NO depending on the answer of the problem. 

-----Constraints-----
Subtask 1, 35 points 
-  1 ≤ T ≤ 100
- 2 ≤  size of string s ≤ 1000
-  String s contains lowercase English alphabets (ie. from 'a' to 'z').

Subtask 2, 65 points 
- 2 ≤  size of string s ≤ 10^5
-  Sum of size of string s over all the input test cases won't exceed 10^6
-  String s contains lowercase English alphabets (ie. from 'a' to 'z').

-----Example-----
Input:
4
aaa
abc
abdbca
abba

Output:
YES
NO
YES
YES

-----Explanation-----
Example case 1. Delete any one 'a', resulting string is "aa" which is a palindrome.
Example case 2. It is not possible to delete exactly one character and having a palindrome.
Example case 3. Delete 'c', resulting string is "abdba" which is a palindrome. 
Example case 4. Delete 'b', resulting string is "aba" which is a palindrome.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Do you like summer? Residents of Berland do. They especially love eating ice cream in the hot summer. So this summer day a large queue of n Berland residents lined up in front of the ice cream stall. We know that each of them has a certain amount of berland dollars with them. The residents of Berland are nice people, so each person agrees to swap places with the person right behind him for just 1 dollar. More formally, if person a stands just behind person b, then person a can pay person b 1 dollar, then a and b get swapped. Of course, if person a has zero dollars, he can not swap places with person b.

Residents of Berland are strange people. In particular, they get upset when there is someone with a strictly smaller sum of money in the line in front of them.

Can you help the residents of Berland form such order in the line so that they were all happy? A happy resident is the one who stands first in the line or the one in front of who another resident stands with not less number of dollars. Note that the people of Berland are people of honor and they agree to swap places only in the manner described above.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 200 000) — the number of residents who stand in the line.

The second line contains n space-separated integers a_{i} (0 ≤ a_{i} ≤ 10^9), where a_{i} is the number of Berland dollars of a man standing on the i-th position in the line. The positions are numbered starting from the end of the line. 


-----Output-----

If it is impossible to make all the residents happy, print ":(" without the quotes. Otherwise, print in the single line n space-separated integers, the i-th of them must be equal to the number of money of the person on position i in the new line. If there are multiple answers, print any of them.


-----Examples-----
Input
2
11 8

Output
9 10 
Input
5
10 9 7 10 6

Output
:(

Input
3
12 3 3

Output
4 4 10 


-----Note-----

In the first sample two residents should swap places, after that the first resident has 10 dollars and he is at the head of the line and the second resident will have 9 coins and he will be at the end of the line. 

In the second sample it is impossible to achieve the desired result.

In the third sample the first person can swap with the second one, then they will have the following numbers of dollars: 4 11 3, then the second person (in the new line) swaps with the third one, and the resulting numbers of dollars will equal to: 4 4 10. In this line everybody will be happy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kundu is true tree lover. Tree is a connected graph having N vertices and N-1  edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that (a,b,c), (b,a,c) and all such permutations will be considered as the same triplet. 

If the answer is greater than $10^{9}$ + 7, print the answer modulo (%) $10^{9}$ + 7.

Input Format 

The first line contains an integer N, i.e., the number of vertices in tree. 

The next N-1 lines represent edges:  2 space separated integers denoting an edge followed by a color of the edge. A color of an edge is denoted by a small letter of English alphabet, and it can be either red(r) or black(b).  

Output Format 

Print a single number i.e. the number of triplets.  

Constraints 

1 ≤ N ≤ $10^{5}$
 
A node is numbered between 1 to N.  

Sample Input  

5
1 2 b
2 3 r
3 4 r
4 5 b

Sample Output  

4

Explanation

Given tree is something like this.

(2,3,4) is one such triplet because on all paths i.e 2 to 3, 3 to 4 and 2 to 4 there is atleast one edge having red color.

(2,3,5), (1,3,4) and (1,3,5) are other such triplets. 

Note that (1,2,3) is NOT a triplet, because the path from 1 to 2 does not have an edge with red color.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Welcome to the exciting class of Professor Manasa. In each lecture she used to play some game while teaching a new concept. Today's topic is Set Theory. For today's game, she had given a set A = {a_{1}, a_{2}, ...a_{N}} of N integers to her students and asked them to play the game as follows.  

At each step of the game she calls a random student and asks him/her to select a non-empty subset from set A such that this subset had not been selected earlier and the sum of subset should be even. This game ends when all possible subsets had been selected. Manasa needs your help in counting the total number of times students can be called assuming each student gives the right answer. While it is given that if two numbers are same in the given set, they have different colors. It means that if a1 = a2, then choosing a1 and choosing a2 will be considered as different sets. 

Note  

Two subsets are different if there exists an element (a_{k}) that is present in one subset but not in other. Let's say set A = {a_{1}, a_{2}, a_{3}} = {2, 2, 3}, then all possible subsets are {}, {a_{1}}, {a_{2}}, {a_{3}}, {a_{1}, a_{2}}, {a_{1}, a_{3}}, {a_{2}, a_{3}}, {a_{1}, a_{2}, a_{3}} which is equivalent to {}, {2}, {2}, {3}, {2, 2}, {2, 3}, {2, 3}, {2, 2, 3}.  

Students can be called multiple times.  

Input Format 

The first line contains an integer N i.e. size of set A. 

Next line will contain N integers, each representing an element of A.  

Output Format 

Print number of time students are called. As this number can be very large you have to print the answer modulo (10^{9} + 7). 

Constraints 

1 ≤ N ≤ 10^{5} 

0 ≤ a_{i} ≤ 10^{4} , where i ∈ [1 .. N]

Sample Input 00  

4
2 4 6 1

Sample Output 00  

7

Sample Input 01  

3
1 2 2

Sample Output 01  

3

Explanation 

There are 7 different ways in which a non-empty subset, with even sum, can be selected, i.e., {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6}.

For second sample test case, there are 3 different ways in which a non-empty subset, with even sum, can be selected, i.e., {a_{2}}, {a_{3}}, {a_{2}, a_{3}} which is equivalent to {2}, {2}, {2,2}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem is different from the hard version. In this version Ujan makes exactly one exchange. You can hack this problem only if you solve both problems.

After struggling and failing many times, Ujan decided to try to clean up his house again. He decided to get his strings in order first.

Ujan has two distinct strings $s$ and $t$ of length $n$ consisting of only of lowercase English characters. He wants to make them equal. Since Ujan is lazy, he will perform the following operation exactly once: he takes two positions $i$ and $j$ ($1 \le i,j \le n$, the values $i$ and $j$ can be equal or different), and swaps the characters $s_i$ and $t_j$. Can he succeed?

Note that he has to perform this operation exactly once. He has to perform this operation.


-----Input-----

The first line contains a single integer $k$ ($1 \leq k \leq 10$), the number of test cases.

For each of the test cases, the first line contains a single integer $n$ ($2 \leq n \leq 10^4$), the length of the strings $s$ and $t$. 

Each of the next two lines contains the strings $s$ and $t$, each having length exactly $n$. The strings consist only of lowercase English letters. It is guaranteed that strings are different.


-----Output-----

For each test case, output "Yes" if Ujan can make the two strings equal and "No" otherwise.

You can print each letter in any case (upper or lower).


-----Example-----
Input
4
5
souse
houhe
3
cat
dog
2
aa
az
3
abc
bca

Output
Yes
No
No
No



-----Note-----

In the first test case, Ujan can swap characters $s_1$ and $t_4$, obtaining the word "house".

In the second test case, it is not possible to make the strings equal using exactly one swap of $s_i$ and $t_j$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three strings $s$, $t$ and $p$ consisting of lowercase Latin letters. You may perform any number (possibly, zero) operations on these strings.

During each operation you choose any character from $p$, erase it from $p$ and insert it into string $s$ (you may insert this character anywhere you want: in the beginning of $s$, in the end or between any two consecutive characters). 

For example, if $p$ is aba, and $s$ is de, then the following outcomes are possible (the character we erase from $p$ and insert into $s$ is highlighted):

  aba $\rightarrow$ ba, de $\rightarrow$ ade;  aba $\rightarrow$ ba, de $\rightarrow$ dae;  aba $\rightarrow$ ba, de $\rightarrow$ dea;  aba $\rightarrow$ aa, de $\rightarrow$ bde;  aba $\rightarrow$ aa, de $\rightarrow$ dbe;  aba $\rightarrow$ aa, de $\rightarrow$ deb;  aba $\rightarrow$ ab, de $\rightarrow$ ade;  aba $\rightarrow$ ab, de $\rightarrow$ dae;  aba $\rightarrow$ ab, de $\rightarrow$ dea; 

Your goal is to perform several (maybe zero) operations so that $s$ becomes equal to $t$. Please determine whether it is possible.

Note that you have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 100$) — the number of queries. Each query is represented by three consecutive lines.

The first line of each query contains the string $s$ ($1 \le |s| \le 100$) consisting of lowercase Latin letters.

The second line of each query contains the string $t$ ($1 \le |t| \le 100$) consisting of lowercase Latin letters.

The third line of each query contains the string $p$ ($1 \le |p| \le 100$) consisting of lowercase Latin letters.


-----Output-----

For each query print YES if it is possible to make $s$ equal to $t$, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).


-----Example-----
Input
4
ab
acxb
cax
a
aaaa
aaabbcc
a
aaaa
aabbcc
ab
baaa
aaaaa

Output
YES
YES
NO
NO



-----Note-----

In the first test case there is the following sequence of operation:   $s = $ ab, $t = $ acxb, $p = $ cax;  $s = $ acb, $t = $ acxb, $p = $ ax;  $s = $ acxb, $t = $ acxb, $p = $ a. 

In the second test case there is the following sequence of operation:   $s = $ a, $t = $ aaaa, $p = $ aaabbcc;  $s = $ aa, $t = $ aaaa, $p = $ aabbcc;  $s = $ aaa, $t = $ aaaa, $p = $ abbcc;  $s = $ aaaa, $t = $ aaaa, $p = $ bbcc.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After last year’s edition of the BAPC, you are still stuck in Delft. In order to participate again this year, you are going to Amsterdam by bus. During the journey you look out of the window and look for traffic signs that point in the direction of Amsterdam. To your surprise, you notice that the bus is never taking the roads that are pointed out by the signs!

You think that the bus company might have chosen a route such that, at no intersection, the bus goes in the direction that is pointed to by the signs. Your friends, however, find this very unbelievable, and don’t think this is possible. Can you figure out whether there exists a bus route that satisfies this requirement? Note that a bus route never visits the same place twice.

A traffic sign pointing in the direction of the shortest route to Amsterdam is placed at every intersection. You may assume that the input graph is both simple and connected, and that there is a unique optimal route to Amsterdam from every intersection.

-----Input-----
 - A single line containing two integers: $n$ ($2 \le n \le 10^5$), the number of intersections, and $m$ ($1 \le m \le 10^6$), the number of undirected roads that connect the intersections. The intersections are numbered from $0$ to $n-1$. Delft is denoted by intersection $i=0$ and Amsterdam is denoted by intersection $i=1$.
 - $m$ lines that specify the roads
 - A road is specified by three integers, $a_ i$, $b_ i$ ($0 \leq a_ i, b_ i < n$ and $a_ i \ne b_ i$) and $d_ i$ ($0 \le d_ i \leq 500000$), where $a_ i$ and $b_ i$ are ids of the two intersections that are connected by this road and $d_ i$ is the distance that the bus has to travel to get from $a_ i$ to $b_ i$ or vice versa.

-----Output-----
As output, give one of the following:
 - A path from Delft to Amsterdam that satisfies the requirements, in case such a path exists.
 - A path is specified by a single line containing an integer $k$, the length of the path, followed by $k$ integers $p_ i$ that specify the intersections along the path in the order in which they are crossed, with $p_0 = 0$ and $p_{k-1}=1$.
 - The text “impossible”, if such a path does not exist.

-----Examples-----
Sample Input 1:
4 5
0 2 5
2 1 5
0 3 10
3 1 20
3 2 5
Sample Output 1:
3 0 3 1

Sample Input 2:
4 3
0 1 10
1 2 20
2 3 30
Sample Output 2:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The number ```1331``` is the first positive perfect cube,  higher than ```1```, having all its digits odd (its cubic root is ```11```).

The next one is ```3375```.

In the interval [-5000, 5000] there are six pure odd digit perfect cubic numbers and are: ```[-3375,-1331, -1, 1, 1331, 3375]```

Give the numbers of this sequence that are in the range ```[a,b] ```(both values inclusive)

Examples:
``` python
odd_dig_cubic(-5000, 5000) == [-3375,-1331, -1, 1, 1331, 3375] # the output should be sorted.
odd_dig_cubic(0, 5000) == [1, 1331, 3375]
odd_dig_cubic(-1, 5000) == [-1, 1, 1331, 3375]
odd_dig_cubic(-5000, -2) == [-3375,-1331]

```
Features of the random tests for python:
```
number of Tests = 94
minimum value for a = -1e17
maximum value for b = 1e17
```
You do not have to check the entries, ```a``` and ```b``` always integers and ```a < b``` 

Working well in Python 2 and Python 3.
Translation into Ruby is coming soon.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As we all know, Dhoni loves drinking milk. Once he and Sir Jadeja were invited in the inauguration of a Dairy company in Ranchi.

The company had arranged  n   jars of milk from various breeds of cows , jar number  i  containing  a[i]  litres of milk. Since Dhoni loves driking milk more than Sir Jadeja, so Kohli suggested a plan for them. His plan was that each time Dhoni will choose a jar containing the maximum amount of milk. If this jar has less than  k   litres of milk or if Dhoni has already drunk more than  m  number of times from this jar, then the milk contained in the jar will be drunk by Sir Jadeja. Sir Jadeja will drink all the milk left in that jar. Otherwise Dhoni will drink exactly k  litres of milk from the jar and put it back at its position. Dhoni will do so until he has given all jars to Sir Jadeja.

You have to calculate how much milk Sir Jadega will get after Dhoni satisfies his hunger modulo 1,000,000,007.

-----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 integer N , M, K denoting the number of milk jars, maximum number of time Dhoni will drink from any jar and maximum amount of milk Dhoni will drink at any time respectively. The second line contains N space-separated integers A1, A2, ..., AN denoting the amount of milk in each jar. 

-----Output-----
- For each test case, output a single line containing the amount of milk Sir Jadega will get modulo 1,000,000,007.

-----Constraints-----
- 1 ≤ T ≤  10 
- 1 ≤ N ≤  10^5 
- 0 ≤ M ≤  10^6 
- 1 ≤ K ≤  10^6 
- 0 ≤ Ai ≤  10^9 

-----Example-----
Input:
1
3 3 3
15 8 10

Output:
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Devu is a dumb guy, his learning curve is very slow. You are supposed to teach him n subjects, the i^{th} subject has c_{i} chapters. When you teach him, you are supposed to teach all the chapters of a subject continuously.

Let us say that his initial per chapter learning power of a subject is x hours. In other words he can learn a chapter of a particular subject in x hours.

Well Devu is not complete dumb, there is a good thing about him too. If you teach him a subject, then time required to teach any chapter of the next subject will require exactly 1 hour less than previously required (see the examples to understand it more clearly). Note that his per chapter learning power can not be less than 1 hour.

You can teach him the n subjects in any possible order. Find out minimum amount of time (in hours) Devu will take to understand all the subjects and you will be free to do some enjoying task rather than teaching a dumb guy.

Please be careful that answer might not fit in 32 bit data type.


-----Input-----

The first line will contain two space separated integers n, x (1 ≤ n, x ≤ 10^5). The next line will contain n space separated integers: c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^5).


-----Output-----

Output a single integer representing the answer to the problem.


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

Output
11

Input
4 2
5 1 2 1

Output
10

Input
3 3
1 1 1

Output
6



-----Note-----

Look at the first example. Consider the order of subjects: 1, 2. When you teach Devu the first subject, it will take him 3 hours per chapter, so it will take 12 hours to teach first subject. After teaching first subject, his per chapter learning time will be 2 hours. Now teaching him second subject will take 2 × 1 = 2 hours. Hence you will need to spend 12 + 2 = 14 hours.

Consider the order of subjects: 2, 1. When you teach Devu the second subject, then it will take him 3 hours per chapter, so it will take 3 × 1 = 3 hours to teach the second subject. After teaching the second subject, his per chapter learning time will be 2 hours. Now teaching him the first subject will take 2 × 4 = 8 hours. Hence you will need to spend 11 hours.

So overall, minimum of both the cases is 11 hours.

Look at the third example. The order in this example doesn't matter. When you teach Devu the first subject, it will take him 3 hours per chapter. When you teach Devu the second subject, it will take him 2 hours per chapter. When you teach Devu the third subject, it will take him 1 hours per chapter. In total it takes 6 hours.

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