vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
"I don't have any fancy quotes." - vijju123
Chef was reading some quotes by great people. Now, he is interested in classifying all the fancy quotes he knows. He thinks that all fancy quotes which contain the word "not" are Real Fancy; quotes that do not contain it are regularly fancy.
You are given some quotes. For each quote, you need to tell Chef if it is Real Fancy or just regularly fancy.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single string $S$ denoting a quote.

-----Output-----
For each test case, print a single line containing the string "Real Fancy" or "regularly fancy" (without quotes).

-----Constraints-----
- $1 \le T \le 50$
- $1 \le |S| \le 100$
- each character of $S$ is either a lowercase English letter or a space

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
2
i do not have any fancy quotes
when nothing goes right go left

-----Example Output-----
Real Fancy
regularly fancy

-----Explanation-----
Example case 1: "i do not have any fancy quotes"
Example case 2: The word "not" does not appear in the given quote.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chilly Willy loves playing with numbers. He only knows prime numbers that are digits yet. These numbers are 2, 3, 5 and 7. But Willy grew rather bored of such numbers, so he came up with a few games that were connected with them.

Chilly Willy wants to find the minimum number of length n, such that it is simultaneously divisible by all numbers Willy already knows (2, 3, 5 and 7). Help him with that.

A number's length is the number of digits in its decimal representation without leading zeros.


-----Input-----

A single input line contains a single integer n (1 ≤ n ≤ 10^5).


-----Output-----

Print a single integer — the answer to the problem without leading zeroes, or "-1" (without the quotes), if the number that meet the problem condition does not exist.


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

Output
-1

Input
5

Output
10080

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two non-empty strings $s$ and $t$, consisting of Latin letters.

In one move, you can choose an occurrence of the string $t$ in the string $s$ and replace it with dots.

Your task is to remove all occurrences of the string $t$ in the string $s$ in the minimum number of moves, and also calculate how many different sequences of moves of the minimum length exist.

Two sequences of moves are considered different if the sets of indices at which the removed occurrences of the string $t$ in $s$ begin differ. For example, the sets $\{1, 2, 3\}$ and $\{1, 2, 4\}$ are considered different, the sets $\{2, 4, 6\}$ and $\{2, 6\}$ — too, but sets $\{3, 5\}$ and $\{5, 3\}$ — not.

For example, let the string $s =$ "abababacababa" and the string $t =$ "aba". We can remove all occurrences of the string $t$ in $2$ moves by cutting out the occurrences of the string $t$ at the $3$th and $9$th positions. In this case, the string $s$ is an example of the form "ab...bac...ba". It is also possible to cut occurrences of the string $t$ at the $3$th and $11$th positions. There are two different sequences of minimum length moves.

Since the answer can be large, output it modulo $10^9 + 7$.


-----Input-----

The first line of the input contains a single integer $q$ ($1 \le q \le 50$) — the number of test cases. The descriptions of the sets follow.

The first line of each set contains a non-empty string $s$ ($1 \le |s| \le 500$) consisting of lowercase Latin letters.

The second line of each set contains a non-empty string $t$ ($1 \le |t| \le 500$) consisting of lowercase Latin letters.

It is guaranteed that the sum of string lengths $s$ over all test cases does not exceed $500$. Similarly, it is guaranteed that the sum of string lengths $t$ over all test cases does not exceed $500$.


-----Output-----

For each test case print two integers — the minimum number of moves and the number of different optimal sequences, modulo $10^9 + 7$.


-----Examples-----

Input
8
abababacababa
aba
ddddddd
dddd
xyzxyz
xyz
abc
abcd
abacaba
abaca
abc
def
aaaaaaaa
a
aaaaaaaa
aa
Output
2 2
1 4
2 1
0 1
1 1
0 1
8 1
3 6


-----Note-----

The first test case is explained in the statement.

In the second case, it is enough to cut any of the four occurrences.

In the third case, string $s$ is the concatenation of two strings $t =$ "xyz", so there is a unique optimal sequence of $2$ moves.

In the fourth and sixth cases, the string $s$ initially contains no occurrences of the string $t$.

In the fifth case, the string $s$ contains exactly one occurrence of the string $t$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Characters in Star Wars each speak a language, but they typically understand a lot more languages that they don’t or can’t speak. For example, Han Solo might speak in Galactic Basic and Chewbacca might respond in Shyriiwook; since they each understand the language spoken by the other, they can communicate just fine like this.

We’ll say two characters can converse if they can exchange messages in both directions. Even if they didn’t understand each other’s languages, two characters can still converse as long as there is a sequence of characters who could translate for them through a sequence of intermediate languages. For example, Jabba the Hutt and R2D2 might be able to converse with some help. Maybe when Jabba spoke in Huttese, Boba Fett could translate to Basic, which R2D2 understands. When R2D2 replies in Binary, maybe Luke could translate to Basic and then Bib Fortuna could translate back to Huttese for Jabba.

In Star Wars Episode IV, there’s a scene with a lot of different characters in a cantina, all speaking different languages. Some pairs of characters may not be able to converse (even if others in the cantina are willing to serve as translators). This can lead to all kinds of problems, fights, questions over who shot first, etc. You’re going to help by asking some of the patrons to leave. The cantina is a business, so you’d like to ask as few as possible to leave. You need to determine the size of the smallest set of characters $S$ such that if all the characters in $S$ leave, all pairs of remaining characters can converse.

For example, in the first sample input below, Chewbacca and Grakchawwaa can converse, but nobody else understands Shyriiwook, so they can’t converse with others in the bar. If they leave, everyone else can converse. In the second sample input, Fran and Ian can converse, as can Polly and Spencer, but no other pairs of characters can converse, so either everyone but Polly and Spencer must leave or everyone but Fran and Ian.

-----Input-----
Input starts with a positive integer, $1 \le N \le 100$, the number of characters in the cantina. This is followed by $N$ lines, each line describing a character. Each of these $N$ lines starts with the character’s name (which is distinct), then the language that character speaks, then a list of $0$ to $20$ additional languages the character understands but doesn’t speak. All characters understand the language they speak. All character and language names are sequences of $1$ to $15$ letters (a-z and A-Z), numbers, and hyphens. Character names and languages are separated by single spaces.

-----Output-----
Print a line of output giving the size of the smallest set of characters $S$ that should be asked to leave so that all remaining pairs of characters can converse.

-----Examples-----
Sample Input:
7
Jabba-the-Hutt Huttese
Bib-Fortuna Huttese Basic
Boba-Fett Basic Huttese
Chewbacca Shyriiwook Basic
Luke Basic Jawaese Binary
Grakchawwaa Shyriiwook Basic Jawaese
R2D2 Binary Basic
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the hard version of Problem F. The only difference between the easy version and the hard version is the constraints.

We will call a non-empty string balanced if it contains the same number of plus and minus signs. For example: strings "+--+" and "++-+--" are balanced, and strings "+--", "--" and "" are not balanced.

We will call a string promising if the string can be made balanced by several (possibly zero) uses of the following operation:

replace two adjacent minus signs with one plus sign.

In particular, every balanced string is promising. However, the converse is not true: not every promising string is balanced.

For example, the string "-+---" is promising, because you can replace two adjacent minuses with plus and get a balanced string "-++-", or get another balanced string "-+-+".

How many non-empty substrings of the given string $s$ are promising? Each non-empty promising substring must be counted in the answer as many times as it occurs in string $s$.

Recall that a substring is a sequence of consecutive characters of the string. For example, for string "+-+" its substring are: "+-", "-+", "+", "+-+" (the string is a substring of itself) and some others. But the following strings are not its substring: "--", "++", "-++".


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

Then the descriptions of test cases follow.

Each test case of input data consists of two lines. The first line consists of the number $n$ ($1 \le n \le 2 \cdot 10^5$): the length of $s$.

The second line of the test case contains the string $s$ of length $n$, consisting only of characters "+" and "-".

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


-----Output-----

For each test case, print a single number: the number of the promising non-empty substrings of string $s$. Each non-empty promising substring must be counted in the answer as many times as it occurs in string $s$.


-----Examples-----

Input
5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---
Output
2
4
2
7
4


-----Note-----

The following are the promising substrings for the first three test cases in the example:

$s[1 \dots 2]$="+-", $s[2 \dots 3]$="-+";

$s[1 \dots 2]$="-+", $s[2 \dots 3]$="+-", $s[1 \dots 5]$="-+---", $s[3 \dots 5]$="---";

$s[1 \dots 3]$="---", $s[2 \dots 4]$="---".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day, Delta, the dog, got very angry. He has $N$ items with different values, and he decided to destroy a few of them. However, Delta loves his hooman as well. So he only destroyed those items whose Least Significant Bit in binary representation is 0. 
Can you help Delta to find the total damage he did so he could make an equally sorry face?

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of Each test case a single integer $N$.
- Next line contains $N$ integers denoting values of items.

-----Output:-----
For each testcase, output in a single line the total damage caused by Delta.

-----Constraints-----
- $1 \leq T \leq 10^3$
- $1 \leq N \leq 10^3$
- $1 \leq value \leq 10^3$

-----Sample Input:-----
1
5

1 2 3 4 5

-----Sample Output:-----
6

-----EXPLANATION:-----
Total Damage: $2  + 4 = 6$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
IPL 2021 Finals are here and it is between the most successful team of the IPL Mumbai Indians and the team striving to garb their first trophy Royal Challengers Banglore. Rohit Sharma, captain of the team Mumbai Indians has the most experience in IPL finals, he feels lucky if he solves a programming question before the IPL finals. So, he asked the team's head coach  Mahela Jayawardene for a question. Question is, given a string S consisting only of opening and closing parenthesis 'ie '('  and ')',  the task is to find out the length of the longest valid parentheses substring.
NOTE: The length of the smallest valid substring ( ) is 2.
Example 1:
Input: S = "(()("
Output: 2
Explanation: The longest valid 
substring is "()". Length = 2.
Example 2:
Input: S = "()(())("
Output: 6
Explanation: The longest valid 
substring is "()(())". Length = 6.
Your Task:  
You don't need to read input or print anything. Complete the function findMaxLen() which takes S as input parameter and returns the max length.
Constraints:
1  ≤  |S|  ≤  10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer $n$.

Consider all pairs of integer arrays $a$ and $p$ of the same length such that $n = \prod a_i^{p_i}$ (i.e. $a_1^{p_1}\cdot a_2^{p_2}\cdot\ldots$) ($a_i>1;p_i>0$) and $a_i$ is the product of some (possibly one) distinct prime numbers.

For example, for $n = 28 = 2^2\cdot 7^1 = 4^1 \cdot 7^1$ the array pair $a = [2, 7]$, $p = [2, 1]$ is correct, but the pair of arrays $a = [4, 7]$, $p = [1, 1]$ is not, because $4=2^2$ is a product of non-distinct prime numbers.

Your task is to find the maximum value of $\sum a_i \cdot p_i$ (i.e. $a_1\cdot p_1 + a_2\cdot p_2 + \ldots$) over all possible pairs of arrays $a$ and $p$. Note that you do not need to minimize or maximize the length of the arrays.


-----Input-----

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

Each test case contains only one integer $n$ ($2 \le n \le 10^9$).


-----Output-----

For each test case, print the maximum value of $\sum a_i \cdot p_i$.


-----Examples-----

Input
7
100
10
864
130056192
1000000000
2
999999018
Output
20
10
22
118
90
2
333333009


-----Note-----

In the first test case, $100 = 10^2$ so that $a = [10]$, $p = [2]$ when $\sum a_i \cdot p_i$ hits the maximum value $10\cdot 2 = 20$. Also, $a = [100]$, $p = [1]$ does not work since $100$ is not made of distinct prime factors.

In the second test case, we can consider $10$ as $10^1$, so $a = [10]$, $p = [1]$. Notice that when $10 = 2^1\cdot 5^1$, $\sum a_i \cdot p_i = 7$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An integer sequence is called beautiful if the difference between any two consecutive numbers is equal to 1. More formally, a sequence s_1, s_2, …, s_{n} is beautiful if |s_i - s_{i+1}| = 1 for all 1 ≤ i ≤ n - 1.

Trans has a numbers 0, b numbers 1, c numbers 2 and d numbers 3. He wants to construct a beautiful sequence using all of these a + b + c + d numbers.

However, it turns out to be a non-trivial task, and Trans was not able to do it. Could you please help Trans?

Input

The only input line contains four non-negative integers a, b, c and d (0 < a+b+c+d ≤ 10^5).

Output

If it is impossible to construct a beautiful sequence satisfying the above constraints, print "NO" (without quotes) in one line.

Otherwise, print "YES" (without quotes) in the first line. Then in the second line print a + b + c + d integers, separated by spaces — a beautiful sequence. There should be a numbers equal to 0, b numbers equal to 1, c numbers equal to 2 and d numbers equal to 3.

If there are multiple answers, you can print any of them.

Examples

Input


2 2 2 1


Output


YES
0 1 0 1 2 3 2


Input


1 2 3 4


Output


NO


Input


2 2 2 3


Output


NO

Note

In the first test, it is easy to see, that the sequence is beautiful because the difference between any two consecutive numbers is equal to 1. Also, there are exactly two numbers, equal to 0, 1, 2 and exactly one number, equal to 3.

It can be proved, that it is impossible to construct beautiful sequences in the second and third tests.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are two 100-story buildings, called A and B. (In this problem, the ground floor is called the first floor.)
For each i = 1,\dots, 100, the i-th floor of A and that of B are connected by a corridor.
Also, for each i = 1,\dots, 99, there is a corridor that connects the (i+1)-th floor of A and the i-th floor of B.
You can traverse each of those corridors in both directions, and it takes you x minutes to get to the other end.
Additionally, both of the buildings have staircases. For each i = 1,\dots, 99, a staircase connects the i-th and (i+1)-th floors of a building, and you need y minutes to get to an adjacent floor by taking the stairs.
Find the minimum time needed to reach the b-th floor of B from the a-th floor of A.

-----Constraints-----
 - 1 \leq a,b,x,y \leq 100
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
a b x y

-----Output-----
Print the minimum time needed to reach the b-th floor of B from the a-th floor of A.

-----Sample Input-----
2 1 1 5

-----Sample Output-----
1

There is a corridor that directly connects the 2-nd floor of A and the 1-st floor of B, so you can travel between them in 1 minute.
This is the fastest way to get there, since taking the stairs just once costs you 5 minutes.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a sequence of positive integers *a*1,<=*a*2,<=...,<=*a**n*. 

While possible, you perform the following operation: find a pair of equal consecutive elements. If there are more than one such pair, find the leftmost (with the smallest indices of elements). If the two integers are equal to *x*, delete both and insert a single integer *x*<=+<=1 on their place. This way the number of elements in the sequence is decreased by 1 on each step. 

You stop performing the operation when there is no pair of equal consecutive elements.

For example, if the initial sequence is [5,<=2,<=1,<=1,<=2,<=2], then after the first operation you get [5,<=2,<=2,<=2,<=2], after the second — [5,<=3,<=2,<=2], after the third — [5,<=3,<=3], and finally after the fourth you get [5,<=4]. After that there are no equal consecutive elements left in the sequence, so you stop the process.

Determine the final sequence after you stop performing the operation.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=2·105) — the number of elements in the sequence.

The second line contains the sequence of integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109).

Output Specification:
In the first line print a single integer *k* — the number of elements in the sequence after you stop performing the operation. 

In the second line print *k* integers — the sequence after you stop performing the operation.

Demo Input:
['6\n5 2 1 1 2 2\n', '4\n1000000000 1000000000 1000000000 1000000000\n', '7\n4 10 22 11 12 5 6\n']

Demo Output:
['2\n5 4 ', '1\n1000000002 ', '7\n4 10 22 11 12 5 6 ']

Note:
The first example is described in the statements.

In the second example the initial sequence is [1000000000, 1000000000, 1000000000, 1000000000]. After the first operation the sequence is equal to [1000000001, 1000000000, 1000000000]. After the second operation the sequence is [1000000001, 1000000001]. After the third operation the sequence is [1000000002].

In the third example there are no two equal consecutive elements initially, so the sequence does not change.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Uh oh! Applications to tech companies are due soon, and you've been procrastinating by doing contests instead! (Let's pretend for now that it is actually possible to get a job in these uncertain times.)

You have completed many programming projects. In fact, there are exactly $n$ types of programming projects, and you have completed $a_i$ projects of type $i$. Your résumé has limited space, but you want to carefully choose them in such a way that maximizes your chances of getting hired.

You want to include several projects of the same type to emphasize your expertise, but you also don't want to include so many that the low-quality projects start slipping in. Specifically, you determine the following quantity to be a good indicator of your chances of getting hired:

$$ f(b_1,\ldots,b_n)=\sum\limits_{i=1}^n b_i(a_i-b_i^2). $$

Here, $b_i$ denotes the number of projects of type $i$ you include in your résumé. Of course, you cannot include more projects than you have completed, so you require $0\le b_i \le a_i$ for all $i$.

Your résumé only has enough room for $k$ projects, and you will absolutely not be hired if your résumé has empty space, so you require $\sum\limits_{i=1}^n b_i=k$.

Find values for $b_1,\ldots, b_n$ that maximize the value of $f(b_1,\ldots,b_n)$ while satisfying the above two constraints.


-----Input-----

The first line contains two integers $n$ and $k$ ($1\le n\le 10^5$, $1\le k\le \sum\limits_{i=1}^n a_i$) — the number of types of programming projects and the résumé size, respectively.

The next line contains $n$ integers $a_1,\ldots,a_n$ ($1\le a_i\le 10^9$) — $a_i$ is equal to the number of completed projects of type $i$.


-----Output-----

In a single line, output $n$ integers $b_1,\ldots, b_n$ that achieve the maximum value of $f(b_1,\ldots,b_n)$, while satisfying the requirements $0\le b_i\le a_i$ and $\sum\limits_{i=1}^n b_i=k$. If there are multiple solutions, output any.

Note that you do not have to output the value $f(b_1,\ldots,b_n)$.


-----Examples-----
Input
10 32
1 2 3 4 5 5 5 5 5 5

Output
1 2 3 3 3 4 4 4 4 4 

Input
5 8
4 4 8 2 1

Output
2 2 2 1 1 



-----Note-----

For the first test, the optimal answer is $f=-269$. Note that a larger $f$ value is possible if we ignored the constraint $\sum\limits_{i=1}^n b_i=k$.

For the second test, the optimal answer is $f=9$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You take part in the testing of new weapon. For the testing a polygon was created. The polygon is a rectangular field n × m in size, divided into unit squares 1 × 1 in size. The polygon contains k objects, each of which is a rectangle with sides, parallel to the polygon sides and entirely occupying several unit squares. The objects don't intersect and don't touch each other.

The principle according to which the weapon works is highly secret. You only know that one can use it to strike any rectangular area whose area is not equal to zero with sides, parallel to the sides of the polygon. The area must completely cover some of the unit squares into which the polygon is divided and it must not touch the other squares. Of course the area mustn't cross the polygon border. Your task is as follows: you should hit no less than one and no more than three rectangular objects. Each object must either lay completely inside the area (in that case it is considered to be hit), or lay completely outside the area.

Find the number of ways of hitting.

Input

The first line has three integers n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 90) — the sizes of the polygon and the number of objects on it respectively. Next n lines contain m symbols each and describe the polygon. The symbol "*" stands for a square occupied an object, whereas the symbol "." stands for an empty space. The symbols "*" form exactly k rectangular connected areas that meet the requirements of the task.

Output

Output a single number — the number of different ways to hit a target.

Examples

Input

3 3 3
*.*
...
*..


Output

21


Input

4 5 4
.*.**
...**
**...
...**


Output

38


Input

2 2 1
.*
..


Output

4

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