vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Kostya is a progamer specializing in the discipline of Dota 2. Valve Corporation, the developer of this game, has recently released a new patch which turned the balance of the game upside down. Kostya, as the captain of the team, realizes that the greatest responsibility lies on him, so he wants to resort to the analysis of innovations patch from the mathematical point of view to choose the best heroes for his team in every game.

A Dota 2 match involves two teams, each of them must choose some heroes that the players of the team are going to play for, and it is forbidden to choose the same hero several times, even in different teams. In large electronic sports competitions where Kostya's team is going to participate, the matches are held in the Captains Mode. In this mode the captains select the heroes by making one of two possible actions in a certain, predetermined order: pick or ban.

  * To pick a hero for the team. After the captain picks, the picked hero goes to his team (later one of a team members will play it) and can no longer be selected by any of the teams. 
  * To ban a hero. After the ban the hero is not sent to any of the teams, but it still can no longer be selected by any of the teams. 



The team captain may miss a pick or a ban. If he misses a pick, a random hero is added to his team from those that were available at that moment, and if he misses a ban, no hero is banned, as if there was no ban.

Kostya has already identified the strength of all the heroes based on the new patch fixes. Of course, Kostya knows the order of picks and bans. The strength of a team is the sum of the strengths of the team's heroes and both teams that participate in the match seek to maximize the difference in strengths in their favor. Help Kostya determine what team, the first one or the second one, has advantage in the match, and how large the advantage is.

Input

The first line contains a single integer n (2 ≤ n ≤ 100) — the number of heroes in Dota 2.

The second line contains n integers s1, s2, ..., sn (1 ≤ si ≤ 106) — the strengths of all the heroes.

The third line contains a single integer m (2 ≤ m ≤ min(n, 20)) — the number of actions the captains of the team must perform.

Next m lines look like "action team", where action is the needed action: a pick (represented as a "p") or a ban (represented as a "b"), and team is the number of the team that needs to perform the action (number 1 or 2).

It is guaranteed that each team makes at least one pick. Besides, each team has the same number of picks and the same number of bans.

Output

Print a single integer — the difference between the strength of the first team and the strength of the second team if the captains of both teams will act optimally well.

Examples

Input

2
2 1
2
p 1
p 2


Output

1


Input

6
6 4 5 4 5 5
4
b 2
p 1
b 1
p 2


Output

0


Input

4
1 2 3 4
4
p 2
b 2
p 1
b 1


Output

-2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are strings S and T. Consider changing S to T by repeating the operation below. Find the minimum number of operations required to do so.
Operation: Choose one character of S and replace it with a different character.

-----Constraints-----
 - S and T have lengths between 1 and 2\times 10^5 (inclusive).
 - S and T consists of lowercase English letters.
 - S and T have equal lengths.

-----Input-----
Input is given from Standard Input in the following format:
S
T

-----Output-----
Print the answer.

-----Sample Input-----
cupofcoffee
cupofhottea

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

We can achieve the objective in four operations, such as the following:
 - First, replace the sixth character c with h.
 - Second, replace the eighth character f with t.
 - Third, replace the ninth character f with t.
 - Fourth, replace the eleventh character e with a.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Blobo2 is in his practical exam. The teacher gave him a *permutation* A of N integers.
 
The teacher has allowed Blobo2 to make a certain type of operation on the *permutation*. In one operation, he can:
Apply left shift on the permutation. In other words, he can take the first element of the permutation and move it to the back of the permutation. 

The teacher has asked Blobo2 to find the lexicographically smallest permutation possible after applying any (possibly zero) number of given operations.

Since Blobo2 wants to impress his teacher, he decided to perform at most two swaps in addition to the allowed operation.

Find the lexicographically smallest possible permutation Blobo2 can generate after applying at most two swaps and any number of given operations.

Note:
A permutation of size N consists of all integers from 1 to N exactly once.
During a swap, Blobo2 can choose any two indices i and j (1≤ i,j≤ N) and swap A_{i} with A
_j.
A permutation X is said to be lexicographically smaller than a permutation Y if X_{i} < Y_{i}, where i is the first index where both the permutations differ.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The second line will contain the integer N, denoting the size of the permutation.
- The third line contains N distinct integers, the elements of the permutation A.

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

Output the lexicographically smallest possible permutation Blobo2 can generate after applying at most two swaps and any number of given operations.

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

$1≤ T≤ 5\cdot 10^{5}$
$1≤ N≤ 10^{5}$
$1≤ A_{i}≤ N$
$A$ is a permutation
- The sum of $N$ over all test cases won't exceed $5\cdot 10^{5}$.

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

----- Sample Output 1 ------ 
1 2 3 4 5 
1 2 3 4 5

----- explanation 1 ------ 
Test case $1$: Blobo2 can perform $2$ swaps:
- For the first swap, Blobo2 can swap the first and second elements: $[\underline{5},\underline{2},1,4,3]$ $\rightarrow$ $[2,5,1,4,3]$
- For the second swap, he can swap the first and fourth elements: $[\underline{2},5,1,\underline{4},3]$ $\rightarrow$ $[4,5,1,2,3]$

Finally, Blobo2 will left shift the array two times which will lead to the lexicographically smallest permutation: $[1,2,3,4,5]$.

Test case $2$: Blobo2 can perform $2$ swaps:
- For the first swap, Blobo2 can swap the third and fifth elements: $[3,5,\underline{2},1,\underline{4}]$ $\rightarrow$ $[3,5,4,1,2]$
- For the second swap, he can swap the second and third elements: $[3,\underline{5},\underline{4},1,2]$ $\rightarrow$ $[3,4,5,1,2]$

Finally, Blobo2 will left shift the array two times which will lead to the lexicographically smallest permutation: $[1,2,3,4,5]$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mayor of city S just hates trees and lawns. They take so much space and there could be a road on the place they occupy!

The Mayor thinks that one of the main city streets could be considerably widened on account of lawn nobody needs anyway. Moreover, that might help reduce the car jams which happen from time to time on the street.

The street is split into *n* equal length parts from left to right, the *i*-th part is characterized by two integers: width of road *s**i* and width of lawn *g**i*.

For each of *n* parts the Mayor should decide the size of lawn to demolish. For the *i*-th part he can reduce lawn width by integer *x**i* (0<=≤<=*x**i*<=≤<=*g**i*). After it new road width of the *i*-th part will be equal to *s*'*i*<==<=*s**i*<=+<=*x**i* and new lawn width will be equal to *g*'*i*<==<=*g**i*<=-<=*x**i*.

On the one hand, the Mayor wants to demolish as much lawn as possible (and replace it with road). On the other hand, he does not want to create a rapid widening or narrowing of the road, which would lead to car accidents. To avoid that, the Mayor decided that width of the road for consecutive parts should differ by at most 1, i.e. for each *i* (1<=≤<=*i*<=&lt;<=*n*) the inequation |*s*'*i*<=+<=1<=-<=*s*'*i*|<=≤<=1 should hold. Initially this condition might not be true.

You need to find the the total width of lawns the Mayor will destroy according to his plan.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=2·105) — number of parts of the street.

Each of the following *n* lines contains two integers *s**i*,<=*g**i* (1<=≤<=*s**i*<=≤<=106, 0<=≤<=*g**i*<=≤<=106) — current width of road and width of the lawn on the *i*-th part of the street.

Output Specification:
In the first line print the total width of lawns which will be removed.

In the second line print *n* integers *s*'1,<=*s*'2,<=...,<=*s*'*n* (*s**i*<=≤<=*s*'*i*<=≤<=*s**i*<=+<=*g**i*) — new widths of the road starting from the first part and to the last.

If there is no solution, print the only integer -1 in the first line.

Demo Input:
['3\n4 5\n4 5\n4 10\n', '4\n1 100\n100 1\n1 100\n100 1\n', '3\n1 1\n100 100\n1 1\n']

Demo Output:
['16\n9 9 10 \n', '202\n101 101 101 101 \n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let us remind you the rules of a very popular game called "Snake" (or sometimes "Boa", "Python" or "Worm").

The game field is represented by an n × m rectangular table. Some squares of the field are considered impassable (walls), all other squares of the fields are passable.

You control a snake, the snake consists of segments. Each segment takes up exactly one passable square of the field, but any passable square contains at most one segment. All segments are indexed by integers from 1 to k, where k is the snake's length. The 1-th segment is the head and the k-th segment is the tail. For any i (1 ≤ i < k), segments with indexes i and i + 1 are located in the adjacent squares of the field, that is, these squares share a common side.

One of the passable field squares contains an apple. The snake's aim is to reach the apple and eat it (that is, to position its head in the square with the apple).

The snake moves throughout the game. During one move the snake can move its head to an adjacent field square. All other segments follow the head. That is, each segment number i (1 < i ≤ k) moves to the square that has just had segment number i - 1. Consider that all segments including the head move simultaneously (see the second test sample). If the snake's head moves to an unpassable square or to the square, occupied by its other segment, the snake dies. That's why we will consider such moves unvalid.

Your task is to determine the minimum number of valid moves that the snake needs to reach the apple.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 15) — the number of rows and columns of the game field.

Next n lines describe the game field. Each of these lines contains m characters. Character "#" represents a wall, "." is a passable square, "@" is an apple. The snake's first segment is represented by character "1", the second one segment — by character "2" and so on.

The game field description doesn't contain any characters besides "#', ".", "@" and digits (except 0). It is guaranteed that the described field is correct. It is guaranteed that the described field contains exactly one apple and exactly one snake, the snake's length is at least 3 and at most 9.

Output

Print a single integer to the output — the minimum number of moves needed to reach the apple. If the snake can't reach the apple, print -1.

Examples

Input

4 5
##...
..1#@
432#.
...#.


Output

4


Input

4 4
#78#
.612
.543
..@.


Output

6


Input

3 2
3@
2#
1#


Output

-1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Iahub and Iahubina went to a date at a luxury restaurant. Everything went fine until paying for the food. Instead of money, the waiter wants Iahub to write a Hungry sequence consisting of *n* integers. 

A sequence *a*1, *a*2, ..., *a**n*, consisting of *n* integers, is Hungry if and only if: 
 -  Its elements are in increasing order. That is an inequality *a**i*<=&lt;<=*a**j* holds for any two indices *i*,<=*j* (*i*<=&lt;<=*j*). -  For any two indices *i* and *j* (*i*<=&lt;<=*j*), *a**j* must not be divisible by *a**i*. 
Iahub is in trouble, so he asks you for help. Find a Hungry sequence with *n* elements.

Input Specification:
The input contains a single integer: *n* (1<=≤<=*n*<=≤<=105).

Output Specification:
Output a line that contains *n* space-separated integers *a*1 *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=107), representing a possible Hungry sequence. Note, that each *a**i* must not be greater than 10000000 (107) and less than 1.

If there are multiple solutions you can output any one.

Demo Input:
['3\n', '5\n']

Demo Output:
['2 9 15\n', '11 14 20 27 31\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an input string composed solely of lowercase English letters, find the longest substring that occurs more than once in the input string. The two occurrences are allowed to partially overlap.

-----Input-----
The input is a single line containing a string of lowercase letters. The string contains more than one character, but no more than $10^5$. At least one letter will appear at least twice.

-----Output-----
Print a single line of output: the longest substring that occurs more than once in the input string. If there are multiple longest repeated substrings, print the one the would come first when the longest substrings are sorted in lexicographical (alphabetical) order.

-----Examples-----
Sample Input 1:
abcefgabc
Sample Output 1:
abc

Sample Input 2:
abcbabcba
Sample Output 2:
abcba

Sample Input 3:
aaaa
Sample Output 3:
aaa

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our chef has recently opened a new restaurant with a unique style. The restaurant is divided into K compartments (numbered from 1 to K) and each compartment can be occupied by at most one customer. 
Each customer that visits the restaurant has a strongly preferred compartment p (1 ≤ p ≤ K), and if that compartment is already occupied, then the customer simply leaves. Now obviously, the chef wants to maximize the total number of customers that dine at his restaurant and so he allows (or disallows) certain customers so as to achieve this task. You are to help him with this. 
Given a list of N customers with their arrival time, departure time and the preferred compartment, you need to calculate the maximum number of customers that can dine at the restaurant. 

-----Input-----
The first line contains an integer T denoting the number of test cases. Each of the next T lines contains two integers N and  K , the number of customers that plan to visit the chef's restaurant and the number of compartments the restaurant is divided into respectively. Each of the next N lines contains three integers si, fi and pi , the arrival time, departure time and the strongly preferred compartment of the ith customer respectively.  

Note that the ith customer wants to occupy the pith compartment from [si, fi)  i.e the ith customer leaves just before   fi  so that another customer can occupy that compartment from   fi  onwards.

-----Output-----
For every test case, print in a single line the maximum number of customers that dine at the restaurant.

-----Constraints-----
-  1 ≤  T ≤   30 
-  0  ≤ N  ≤  105 
-  1  ≤  K  ≤  109 
-  0  ≤  si < fi ≤   109 
-  1  ≤  pi  ≤  K  

-----Example-----
Input:
2
3 3
1 3 1
4 6 2
7 10 3
4 2
10 100 1
100 200 2
150 500 2
200 300 2

Output:
3
3

-----Explanation-----
Example case 1.

All three customers want different compartments and hence all 3 can be accommodated.

Example case 2.

If we serve the 1st, 2nd and 4th customers, then we can get a maximum of 3.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an undirected graph consisting of *n* vertices. Initially there are no edges in the graph. Also you are given *q* queries, each query either adds one undirected edge to the graph or removes it. After each query you have to check if the resulting graph is bipartite (that is, you can paint all vertices of the graph into two colors so that there is no edge connecting two vertices of the same color).

Input Specification:
The first line contains two integers *n* and *q* (2<=≤<=*n*,<=*q*<=≤<=100000).

Then *q* lines follow. *i*th line contains two numbers *x**i* and *y**i* (1<=≤<=*x**i*<=&lt;<=*y**i*<=≤<=*n*). These numbers describe *i*th query: if there is an edge between vertices *x**i* and *y**i*, then remove it, otherwise add it.

Output Specification:
Print *q* lines. *i*th line must contain YES if the graph is bipartite after *i*th query, and NO otherwise.

Demo Input:
['3 5\n2 3\n1 3\n1 2\n1 2\n1 2\n']

Demo Output:
['YES\nYES\nNO\nYES\nNO\n']

Note:
none

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
There are *n* cities numbered from 1 to *n* in Berland. Some of them are connected by two-way roads. Each road has its own length — an integer number from 1 to 1000. It is known that from each city it is possible to get to any other city by existing roads. Also for each pair of cities it is known the shortest distance between them. Berland Government plans to build *k* new roads. For each of the planned road it is known its length, and what cities it will connect. To control the correctness of the construction of new roads, after the opening of another road Berland government wants to check the sum of the shortest distances between all pairs of cities. Help them — for a given matrix of shortest distances on the old roads and plans of all new roads, find out how the sum of the shortest distances between all pairs of cities changes after construction of each road.

Input Specification:
The first line contains integer *n* (2<=≤<=*n*<=≤<=300) — amount of cities in Berland. Then there follow *n* lines with *n* integer numbers each — the matrix of shortest distances. *j*-th integer in the *i*-th row — *d**i*,<=*j*, the shortest distance between cities *i* and *j*. It is guaranteed that *d**i*,<=*i*<==<=0,<=*d**i*,<=*j*<==<=*d**j*,<=*i*, and a given matrix is a matrix of shortest distances for some set of two-way roads with integer lengths from 1 to 1000, such that from each city it is possible to get to any other city using these roads.

Next line contains integer *k* (1<=≤<=*k*<=≤<=300) — amount of planned roads. Following *k* lines contain the description of the planned roads. Each road is described by three space-separated integers *a**i*, *b**i*, *c**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=*a**i*<=≠<=*b**i*,<=1<=≤<=*c**i*<=≤<=1000) — *a**i* and *b**i* — pair of cities, which the road connects, *c**i* — the length of the road. It can be several roads between a pair of cities, but no road connects the city with itself.

Output Specification:
Output *k* space-separated integers *q**i* (1<=≤<=*i*<=≤<=*k*). *q**i* should be equal to the sum of shortest distances between all pairs of cities after the construction of roads with indexes from 1 to *i*. Roads are numbered from 1 in the input order. Each pair of cities should be taken into account in the sum exactly once, i. e. we count unordered pairs.

Demo Input:
['2\n0 5\n5 0\n1\n1 2 3\n', '3\n0 4 5\n4 0 9\n5 9 0\n2\n2 3 8\n1 2 1\n']

Demo Output:
['3 ', '17 12 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef got his dream seat in F1 and secured a 3^{rd} place in his debut race. He now wants to know the time gap between him and the winner of the race.

You are his chief engineer and you only know the time gap between Chef and the runner up of the race, given as A seconds, and the time gap between the runner up and the winner of the race, given as B seconds. 

Please calculate and inform Chef about the time gap between him and the winner of the race.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input containing two space-separated integers A and B denoting the time gap between Chef and the runner up and the time gap between the runner up and the winner respectively. 

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

For each test case, output the time gap between Chef and the winner of the race.

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

$1 ≤ T ≤ 100$
$1 ≤ A, B ≤ 10$

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

----- Sample Output 1 ------ 
2
7
5
11

----- explanation 1 ------ 
Test case $1$: The time gap between Chef and runner up is $1$ second. The time gap between runner up and the winner is $1$ second. Thus, the time gap between Chef and the winner is $1+1=2$ seconds.

Test case $2$: The time gap between Chef and runner up is $2$ seconds. The time gap between runner up and the winner is $5$ second. Thus, the time gap between Chef and the winner is $2+5=7$ seconds.

Test case $3$: The time gap between Chef and runner up is $3$ seconds. The time gap between runner up and the winner is $2$ second. Thus, the time gap between Chef and the winner is $3+2=5$ seconds.

Test case $4$: The time gap between Chef and runner up is $5$ seconds. The time gap between runner up and the winner is $6$ second. Thus, the time gap between Chef and the winner is $5+6=11$ seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two sorted arrays that contain only integers. Your task is to find a way to merge them into a single one, sorted in **ascending order**. Complete the function `mergeArrays(arr1, arr2)`, where `arr1` and `arr2` are the original sorted arrays.

You don't need to worry about validation, since `arr1` and `arr2` must be arrays with 0 or more Integers. If both `arr1` and `arr2` are empty, then just return an empty array.

**Note:** `arr1` and `arr2` may be sorted in different orders. Also `arr1` and `arr2` may have same integers. Remove duplicated in the returned result.

## Examples

Happy coding!

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