vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Chef has $N$ dishes of different types arranged in a row: $A_1, A_2, \ldots, A_N$, where $A_i$ denotes the type of the $i^{th}$ dish. He wants to choose as many dishes as possible from the given list but while satisfying two conditions: 
- He can choose only one type of dish.   
- No two chosen dishes should be adjacent to each other. 
Chef wants to know which type of dish he should choose from, so that he can pick the maximum number of dishes.
Example:

Given $N$=$9$ and $A$=$[1, 2, 2, 1, 2, 1, 1, 1, 1]$.

For type 1, Chef can choose at most four dishes. One of the ways to choose four dishes of type 1 is $A_1$, $A_4$, $A_7$ and $A_9$.

For type 2, Chef can choose at most two dishes. One way is to choose $A_3$ and $A_5$.

So in this case, Chef should go for type 1, in which he can pick more dishes.

-----Input:-----
- The first line contains $T$, the number of test cases. Then the test cases follow.
- For each test case, the first line contains a single integer $N$.
- The second line contains $N$ integers $A_1, A_2, \ldots, A_N$. 

-----Output:-----
For each test case, print a single line containing one integer ― the type of the dish that Chef should choose from. If there are multiple answers, print the smallest one.

-----Constraints-----
- $1 \le T \le 10^3$
- $1 \le N \le 10^3$
- $1 \le A_i \le 10^3$
- Sum of $N$ over all test cases doesn't exceed $10^4$

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

-----Sample Output:-----
1
1
2

-----Explanation:-----
Test case 1:

For both type 1 and type 2, Chef can pick at most two dishes. In the case of multiple answers, we pick the smallest one. Hence the answer will be $1$.
Test case 2:

There are only dishes of type 1. So the answer is $1$.
Test case 3:

For type 1, Chef can choose at most two dishes. For type 2, he can choose three dishes. For type 3 and type 4, Chef can choose the only dish available. Hence the maximum is in type 2 and so the answer is $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Countless lithographs have been found in the ruins of the ancient nation Iwashiro. Researchers have found that each lithograph has one word engraved on it. However, due to many years of weathering, some lithographs are difficult to decipher for the following reasons.

* Only one letter of a word written on a lithograph may be covered with moss, and that letter cannot be grasped.
* The left side of the lithograph may be missing, and some character string may have been written there (it is not possible to grasp more than 0 characters on the left side of the lithograph).
* The right side of the lithograph may be missing, and some character string may have been written there (it is not possible to grasp more than 0 characters on the right side of the lithograph).



There is at most one place where moss grows on the lithograph. In addition, although moss may grow on the chipped lithograph, both sides of the lithograph are not chipped at the same time.

Researchers have a dictionary of words known from surveys prior to the discovery of lithographs. However, when guessing the original word from a lithograph with moss and chips due to the effects of weathering, it is not immediately clear how many words in the dictionary apply.

Create a program that counts how many words are likely to fit in a given dictionary when given lithographic information.



Input

The input is given in the following format.


N M
word1
word2
::
wordN
slate1
slate2
::
slateM


The number of words in the dictionary N (1 ≤ N ≤ 50000) and the number of lithographs M (1 ≤ M ≤ 50000) are given on the first line. The word wordi is given on the following N lines. A word is a character string with a length of 1 or more and 200 or less, including only lowercase letters. However, the N words are all different. The following M line is given the string slatei that represents the information for each lithograph. slatei is a character string with a length of 1 or more and 200 or less, including lowercase letters, "?", And "*". ? Represents a moss-covered character. At most one? Appears in one string. If the string starts with *, it means that the left side of the lithograph is missing. If the string ends with *, it indicates that the right side of the lithograph is missing. * Does not appear except at the beginning or end of the string, and does not appear on both sides at the same time. A string with only one * is never given.

The total number of characters in the string given in the input does not exceed 3000000.

Output

For each lithograph, output the number of words on one line.

Example

Input

5 4
aloe
apple
apricot
cactus
cat
apple
ap*
*e
ca?*


Output

1
2
2
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"




Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"



Note:

All the strings in the input will only contain lower-case letters.
The size of the dictionary won't exceed 1,000.
The length of all the strings in the input won't exceed 1,000.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Tanya had breakup with his boyfriend and now she is looking for someone who can understand her and take care of her.
So Tanya formulated a problem and puts a condition that whosoever will first solve the problem, she would make him her boyfriend.
Tanya defines the problem as follows.

Given an array of N elements . You have to perform Q queries on this array. Queries are of the following type

1) 1 i j x --> Add x to array elements from index i to index j.

2) 2 i j x --> Subtract x to array elements from index i to index j.

3) 3 i j x --> Set all array elements from index i to index j to x.

4) 4 i j   --> print the sum of squares of all array elements from index i to index j.

5) 5 i j   --> print the sum of all array elements from index i to index j.

Would you like to be her boyfriend ?

Input:

First line contains N and Q , separated by a single space, denoting the size of array and number of queries respectively.

Next line contains N space integers integers.

Then Q lines follow. There can be 3 or 4 integers,separated by a single space, in each line as described as above.

For queries of type 1,2 and 3 , there will be 4 integers , separated by a single space.

For queries of type 4 and 5 , there will be 3 integers , separated by a single space.

Output:

Print the answer for queries of type 4 and 5 in a new line.

Constraints:

1 ≤ N ≤ 10^5

1 ≤ array element ≤ 100

1 ≤ Q ≤ 10^5

1 ≤ i ≤ j ≤ N

1 ≤ x ≤ 100

SAMPLE INPUT
5 5
1 2 3 4 5
1 1 3 5
2 2 4 3
4 2 5
3 1 5 2
5 1 5

SAMPLE OUTPUT
67
10

Explanation

Inital array      - {1 , 2 , 3 , 4 , 5}
After first query - {6 , 7 , 8 , 4 , 5}
After second query -{6 , 4 , 5 , 1 , 5}

sum of squares = 44 + 55 + 11 + 55 = 67

After third query - {2 , 2 , 2 , 2 , 2}

sum of array = 2 + 2 + 2 + 2 + 2 = 10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the drawing below we have a part of the Pascal's triangle, lines are numbered from **zero** (top).
The left diagonal in pale blue with only numbers equal to 1 is diagonal **zero**, then in dark green 
(1, 2, 3, 4, 5, 6, 7) is diagonal 1, then in pale green (1, 3, 6, 10, 15, 21) is
diagonal 2 and so on.

We want to calculate the sum of the binomial coefficients on a given diagonal.
The sum on diagonal 0 is 8 (we'll write it S(7, 0), 7 is the number of the line where we start, 
0 is the number of the diagonal). In the same way S(7, 1) is 28, S(7, 2) is 56.

Can you write a program which calculate S(n, p) where n is the line where we start and p 
is the number of the diagonal?

The function will take n and p (with: `n >= p >= 0`) as parameters and will return the sum.

## Examples:
```
diagonal(20, 3) => 5985
diagonal(20, 4) => 20349
```
## Hint:
When following a diagonal from top to bottom have a look at the numbers on the diagonal at its right.

## Ref:
http://mathworld.wolfram.com/BinomialCoefficient.html

![alternative text](http://i.imgur.com/eUGaNvIm.jpg)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N persons are standing in a row. The height of the i-th person from the front is A_i.
We want to have each person stand on a stool of some heights - at least zero - so that the following condition is satisfied for every person:
Condition: Nobody in front of the person is taller than the person. Here, the height of a person includes the stool.
Find the minimum total height of the stools needed to meet this goal.

-----Constraints-----
 - 1 \leq N \leq 2\times 10^5
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 \ldots A_N

-----Output-----
Print the minimum total height of the stools needed to meet the goal.

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

-----Sample Output-----
4

If the persons stand on stools of heights 0, 1, 0, 1, and 2, respectively, their heights will be 2, 2, 5, 5, and 5, satisfying the condition.
We cannot meet the goal with a smaller total height of the stools.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Kingdom of Kremland is a tree (a connected undirected graph without cycles) consisting of $n$ vertices. Each vertex $i$ has its own value $a_i$. All vertices are connected in series by edges. Formally, for every $1 \leq i < n$ there is an edge between the vertices of $i$ and $i+1$.

Denote the function $f(l, r)$, which takes two integers $l$ and $r$ ($l \leq r$):

    We leave in the tree only vertices whose values ​​range from $l$ to $r$.    The value of the function will be the number of connected components in the new graph. 

Your task is to calculate the following sum: $$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) $$


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of vertices in the tree.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) — the values of the vertices.


-----Output-----

Print one number — the answer to the problem.


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

Output
7
Input
4
2 1 1 3

Output
11
Input
10
1 5 2 5 5 3 10 6 5 1

Output
104


-----Note-----

In the first example, the function values ​​will be as follows:   $f(1, 1)=1$ (there is only a vertex with the number $2$, which forms one component)  $f(1, 2)=1$ (there are vertices $1$ and $2$ that form one component)  $f(1, 3)=1$ (all vertices remain, one component is obtained)  $f(2, 2)=1$ (only vertex number $1$)  $f(2, 3)=2$ (there are vertices $1$ and $3$ that form two components)  $f(3, 3)=1$ (only vertex $3$)  Totally out $7$.

In the second example, the function values ​​will be as follows:   $f(1, 1)=1$  $f(1, 2)=1$  $f(1, 3)=1$  $f(1, 4)=1$  $f(2, 2)=1$  $f(2, 3)=2$  $f(2, 4)=2$  $f(3, 3)=1$  $f(3, 4)=1$  $f(4, 4)=0$ (there is no vertex left, so the number of components is $0$)  Totally out $11$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Young Timofey has a birthday today! He got kit of n cubes as a birthday present from his parents. Every cube has a number a_{i}, which is written on it. Timofey put all the cubes in a row and went to unpack other presents.

In this time, Timofey's elder brother, Dima reordered the cubes using the following rule. Suppose the cubes are numbered from 1 to n in their order. Dima performs several steps, on step i he reverses the segment of cubes from i-th to (n - i + 1)-th. He does this while i ≤ n - i + 1.

After performing the operations Dima went away, being very proud of himself. When Timofey returned to his cubes, he understood that their order was changed. Help Timofey as fast as you can and save the holiday — restore the initial order of the cubes using information of their current location.


-----Input-----

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

The second line contains n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9), where a_{i} is the number written on the i-th cube after Dima has changed their order.


-----Output-----

Print n integers, separated by spaces — the numbers written on the cubes in their initial order.

It can be shown that the answer is unique.


-----Examples-----
Input
7
4 3 7 6 9 1 2

Output
2 3 9 6 7 1 4
Input
8
6 1 4 2 5 6 9 2

Output
2 1 6 2 5 4 9 6


-----Note-----

Consider the first sample.  At the begining row was [2, 3, 9, 6, 7, 1, 4].  After first operation row was [4, 1, 7, 6, 9, 3, 2].  After second operation row was [4, 3, 9, 6, 7, 1, 2].  After third operation row was [4, 3, 7, 6, 9, 1, 2].  At fourth operation we reverse just middle element, so nothing has changed. The final row is [4, 3, 7, 6, 9, 1, 2]. So the answer for this case is row [2, 3, 9, 6, 7, 1, 4].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call a string adorable if its letters can be realigned in such a way that they form two consequent groups of equal symbols (note that different groups must contain different symbols). For example, ababa is adorable (you can transform it to aaabb, where the first three letters form a group of a-s and others — a group of b-s), but cccc is not since in each possible consequent partition letters in these two groups coincide.

You're given a string s. Check whether it can be split into two non-empty subsequences such that the strings formed by these subsequences are adorable. Here a subsequence is an arbitrary set of indexes of the string.


-----Input-----

The only line contains s (1 ≤ |s| ≤ 10^5) consisting of lowercase latin letters.


-----Output-----

Print «Yes» if the string can be split according to the criteria above or «No» otherwise.

Each letter can be printed in arbitrary case.


-----Examples-----
Input
ababa

Output
Yes

Input
zzcxx

Output
Yes

Input
yeee

Output
No



-----Note-----

In sample case two zzcxx can be split into subsequences zc and zxx each of which is adorable.

There's no suitable partition in sample case three.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A new dog show on TV is starting next week. On the show dogs are required to demonstrate bottomless stomach, strategic thinking and self-preservation instinct. You and your dog are invited to compete with other participants and naturally you want to win!

On the show a dog needs to eat as many bowls of dog food as possible (bottomless stomach helps here). Dogs compete separately of each other and the rules are as follows:

At the start of the show the dog and the bowls are located on a line. The dog starts at position x = 0 and n bowls are located at positions x = 1, x = 2, ..., x = n. The bowls are numbered from 1 to n from left to right. After the show starts the dog immediately begins to run to the right to the first bowl.

The food inside bowls is not ready for eating at the start because it is too hot (dog's self-preservation instinct prevents eating). More formally, the dog can eat from the i-th bowl after t_{i} seconds from the start of the show or later.

It takes dog 1 second to move from the position x to the position x + 1. The dog is not allowed to move to the left, the dog runs only to the right with the constant speed 1 distance unit per second. When the dog reaches a bowl (say, the bowl i), the following cases are possible:  the food had cooled down (i.e. it passed at least t_{i} seconds from the show start): the dog immediately eats the food and runs to the right without any stop,  the food is hot (i.e. it passed less than t_{i} seconds from the show start): the dog has two options: to wait for the i-th bowl, eat the food and continue to run at the moment t_{i} or to skip the i-th bowl and continue to run to the right without any stop. 

After T seconds from the start the show ends. If the dog reaches a bowl of food at moment T the dog can not eat it. The show stops before T seconds if the dog had run to the right of the last bowl.

You need to help your dog create a strategy with which the maximum possible number of bowls of food will be eaten in T seconds.


-----Input-----

Two integer numbers are given in the first line - n and T (1 ≤ n ≤ 200 000, 1 ≤ T ≤ 2·10^9) — the number of bowls of food and the time when the dog is stopped.

On the next line numbers t_1, t_2, ..., t_{n} (1 ≤ t_{i} ≤ 10^9) are given, where t_{i} is the moment of time when the i-th bowl of food is ready for eating.


-----Output-----

Output a single integer — the maximum number of bowls of food the dog will be able to eat in T seconds.


-----Examples-----
Input
3 5
1 5 3

Output
2

Input
1 2
1

Output
1

Input
1 1
1

Output
0



-----Note-----

In the first example the dog should skip the second bowl to eat from the two bowls (the first and the third).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kamal is an amazing coder. He normally gets over excited during compilers lab, as compilers is his favorite subject.

One fine day, the professor taught everyone about lex and yacc, and gave a sample lexical analyzer creation as the class work. As we all know, Kamal wants to be the first one to show the output. So he codes blazingly fast, and gets the lex and yacc file. He then gave certain inputs and obtained some values as outputs. Now, Kamal, as his mind is preoccupied with thinking about important things, did not want to test the outputs that he got for validity. So, he asks you to do so. Given the inputs and the outputs, check if it is correct or not.

After printing the required answer, print the line, "Code completed, sir!", which is precisely what Kamal would say while raising his hand.

The work:
    The input would be a statement following the given set of rules. The statement represents a sample code which does two operation:
        1) loop() : loop the blocks following it, n number of times
        2) ASSIGN :  Do an assignment operation.

    Rules:
        `
        line> --> <line><line> | <loop> | <assignment> | ""
        <loop> --> loop(<value>) { <line> }
        <assignment> --> ASSIGN;
        <iter> --> <n>
        `

Input:
    The first line contains the integer ite, the number of queries
    The next line contains the string s, for which the answer is to be found.

Output:
    Print the required answer, one per line

Constraints:
    ite ≤ 100
    |s| ≤ 2500
    n ≤     2^63 -1
    It is guarenteed that the answers will not exceed 2^63 -1

SAMPLE INPUT
2
ASSIGN;loop(10){ASSIGN;}
loop(100){loop(100){}}

SAMPLE OUTPUT
11
0
Code completed, sir!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Memory and his friend Lexa are competing to get higher score in one popular computer game. Memory starts with score a and Lexa starts with score b. In a single turn, both Memory and Lexa get some integer in the range [ - k;k] (i.e. one integer among  - k,  - k + 1,  - k + 2, ...,  - 2,  - 1, 0, 1, 2, ..., k - 1, k) and add them to their current scores. The game has exactly t turns. Memory and Lexa, however, are not good at this game, so they both always get a random integer at their turn.

Memory wonders how many possible games exist such that he ends with a strictly higher score than Lexa. Two games are considered to be different if in at least one turn at least one player gets different score. There are (2k + 1)^2t games in total. Since the answer can be very large, you should print it modulo 10^9 + 7. Please solve this problem for Memory.


-----Input-----

The first and only line of input contains the four integers a, b, k, and t (1 ≤ a, b ≤ 100, 1 ≤ k ≤ 1000, 1 ≤ t ≤ 100) — the amount Memory and Lexa start with, the number k, and the number of turns respectively.


-----Output-----

Print the number of possible games satisfying the conditions modulo 1 000 000 007 (10^9 + 7) in one line.


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

Output
6

Input
1 1 1 2

Output
31

Input
2 12 3 1

Output
0



-----Note-----

In the first sample test, Memory starts with 1 and Lexa starts with 2. If Lexa picks  - 2, Memory can pick 0, 1, or 2 to win. If Lexa picks  - 1, Memory can pick 1 or 2 to win. If Lexa picks 0, Memory can pick 2 to win. If Lexa picks 1 or 2, Memory cannot win. Thus, there are 3 + 2 + 1 = 6 possible games in which Memory wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to quickly solve popular puzzles and train your instantaneous power. Today's challenge is a puzzle of colorful tiles lined up and erasing them well.

In the initial state, tiles are placed on some squares on the grid. Each tile is colored. After the game starts, the player can perform the operations shown in the following procedure many times.

1. Select one square without tiles and hit that square.
2. Follow from the hit square to the top, and pay attention to the tile when you reach the square where the tile is placed. If you get to the edge of the board without the squares on which the tiles are placed, you will not pay attention to anything.
3. Perform the same operation from the square you hit to the bottom, left, and right. Up to 4 tiles will be the focus of attention.
4. If any of the tiles of interest have the same color, remove those tiles from the board. If there are two pairs of tiles of the same color, remove both.
5. The score will be the same as the number of tiles removed.
6. Stop paying attention.



For example, consider the following situation. The squares without tiles are periods, and the tile colors are represented by uppercase letters.


..A ......
....... B ..
..........
..B ......
..A.CC ....


Now consider the operation of hitting the squares in the second row from the top and the third column from the left. Since there are three tiles of interest, `A`,` B`, and `B`, the two of` B` disappear and the board becomes as follows, and two points are obtained.


..A ......
..........
..........
..........
..A.CC ....


If this puzzle is slow, the time will run out, and you will not be able to see part of the board and you will not know how much training you lacked. Two tiles of each color are placed, but it is not always possible to erase all of them, so let the program calculate the maximum score in advance.



Input


M N
C1,1 C1,2 ... C1, N
C2,1 C2,2 ... C2, N
...
CM, 1CM, 2 ... CM, N


The integers M and N indicate that the board is a grid of vertical M x horizontal N. Ci and j are uppercase letters or periods (`.`), And for the cells in the i-th row from the top and the j-th column from the left, the uppercase letters indicate the color of the tiles placed, and the period indicates the color of the tile. Indicates that no tile is placed on this square.

Satisfy 1 ≤ M ≤ 500 and 1 ≤ N ≤ 500. Each uppercase letter appears as 0 or 2 as you type.

Output

Output the maximum score on one line.

Examples

Input

5 10
..A.......
.......B..
..........
..B.......
..A.CC....


Output

4


Input

3 3
ABC
D.D
CBA


Output

4


Input

5 7
NUTUBOR
QT.SZRQ
SANAGIP
LMDGZBM
KLKIODP


Output

34

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