yl-9/probench huggingface dataset:
# Eliminating Balls With Merging (Hard Version)

## Problem Description

Drink water.

— Sun Tzu, The Art of Becoming a Healthy Programmer



This is the hard version of the problem. The only difference is that $ x=1 $ in this version. You must solve both versions to be able to hack.

You are given two integers $ n $ and $ x $ ( $ x=1 $ ). There are $ n $ balls lined up in a row, numbered from $ 1 $ to $ n $ from left to right. Initially, there is a value $ a_i $ written on the $ i $ -th ball.

For each integer $ i $ from $ 1 $ to $ n $ , we define a function $ f(i) $ as follows:

- Suppose you have a set $ S = \{1, 2, \ldots, i\} $ .
- In each operation, you have to select an integer $ l $ ( $ 1 \leq l < i $ ) from $ S $ such that $ l $ is not the largest element of $ S $ . Suppose $ r $ is the smallest element in $ S $ which is greater than $ l $ .
  - If $ a_l > a_r $ , you set $ a_l = a_l + a_r $ and remove $ r $ from $ S $ .
  - If $ a_l < a_r $ , you set $ a_r = a_l + a_r $ and remove $ l $ from $ S $ .
  - If $ a_l = a_r $ , you choose either the integer $ l $ or $ r $ to remove from $ S $ : 
      - If you choose to remove $ l $ from $ S $ , you set $ a_r = a_l + a_r $ and remove $ l $ from $ S $ .
      - If you choose to remove $ r $ from $ S $ , you set $ a_l = a_l + a_r $ and remove $ r $ from $ S $ .
- $ f(i) $ denotes the number of integers $ j $ ( $ 1 \le j \le i $ ) such that it is possible to obtain $ S = \{j\} $ after performing the above operations exactly $ i - 1 $ times.

For each integer $ i $ from $ x $ to $ n $ , you need to find $ f(i) $ .

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains two integers $ n $ and $ x $ ( $ 1 \leq n \leq 2 \cdot 10^5; x = 1 $ ) — the number of balls and the smallest index $ i $ for which you need to find $ f(i) $ .

The second line of each test case contains $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the initial number written on each ball.

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

## Output Format

For each test case, output $ n-x+1 $ space separated integers on a new line, where the $ j $ -th integer should represent $ f(x+j-1) $ .

## Sample #1

### Sample Input #1

```
3
5 1
1 2 3 2 1
7 1
4 5 1 2 1 4 5
11 1
1 2 3 1 1 9 3 2 4 1 3
```

### Sample Output #1

```
1 1 2 2 3
1 1 1 1 1 3 4
1 1 2 2 2 1 1 1 3 3 4
```

## Hint

In the first test case, below are the possible values of $ j $ for each $ f(i) $ from $ 1 $ to $ n $ .

- For $ f(1) $ , the only possible value of $ j $ is $ 1 $ .
- For $ f(2) $ , the only possible value of $ j $ is $ 2 $ .
- For $ f(3) $ , the possible values of $ j $ are $ 2 $ and $ 3 $ .
- For $ f(4) $ , the possible values of $ j $ are $ 2 $ and $ 3 $ .
- For $ f(5) $ , the possible values of $ j $ are $ 2 $ , $ 3 $ , and $ 4 $ .

## Limit



Time Limit
4.00s

Memory Limit
500.00MB

Tags: binary search, brute force, data structures, divide and conquer, greedy, implementation
Difficulty: 2500
# Perform Operations to Maximize Score

## Problem Description

I see satyam343. I'm shaking. Please more median problems this time. I love those. Please satyam343 we believe in you.

— satyam343's biggest fan



You are given an array $ a $ of length $ n $ and an integer $ k $ . You are also given a binary array $ b $ of length $ n $ .

You can perform the following operation at most $ k $ times:

- Select an index $ i $ ( $ 1 \leq i \leq n $ ) such that $ b_i = 1 $ . Set $ a_i = a_i + 1 $ (i.e., increase $ a_i $ by $ 1 $ ).

Your score is defined to be $ \max\limits_{i = 1}^{n} \left( a_i + \operatorname{median}(c_i) \right) $ , where $ c_i $ denotes the array of length $ n-1 $ that you get by deleting $ a_i $ from $ a $ . In other words, your score is the maximum value of $ a_i + \operatorname{median}(c_i) $ over all $ i $ from $ 1 $ to $ n $ .

Find the maximum score that you can achieve if you perform the operations optimally.

For an arbitrary array $ p $ , $ \operatorname{median}(p) $ is defined as the $ \left\lfloor \frac{|p|+1}{2} \right\rfloor $ -th smallest element of $ p $ . For example, $ \operatorname{median} \left( [3,2,1,3] \right) = 2 $ and $ \operatorname{median} \left( [6,2,4,5,1] \right) = 4 $ .

## Input Format

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

Each test case begins with two integers $ n $ and $ k $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ , $ 0 \leq k \leq 10^9 $ ) — the length of the $ a $ and the number of operations you can perform.

The following line contains $ n $ space separated integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — denoting the array $ a $ .

The following line contains $ n $ space separated integers $ b_1, b_2, \ldots, b_n $ ( $ b_i $ is $ 0 $ or $ 1 $ ) — denoting the array $ b $ .

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

## Output Format

For each test case, output the maximum value of score you can get on a new line.

## Sample #1

### Sample Input #1

```
8
2 10
3 3
1 1
3 10
3 3 3
0 0 0
4 4
2 1 5 1
0 1 0 1
5 4
7 5 2 5 4
0 0 1 0 1
5 1
5 15 15 2 11
1 0 0 1 1
5 2
10 11 4 10 15
1 1 0 1 0
4 4
1 1 2 5
1 1 0 0
2 1000000000
1000000000 1000000000
1 1
```

### Sample Output #1

```
16
6
8
13
21
26
8
3000000000
```

## Hint

For the first test case, it is optimal to perform $ 5 $ operations on both elements so $ a = [8,8] $ . So, the maximum score we can achieve is $ \max(8 + \operatorname{median}[8], 8 + \operatorname{median}[8]) = 16 $ , as $ c_1 = [a_2] = [8] $ . It can be proven that you cannot get a better score.

For the second test case, you are not able to perform operations on any elements, so $ a $ remains $ [3,3,3] $ . So, the maximum score we can achieve is $ 3 + \operatorname{median}[3, 3] = 6 $ , as $ c_1 = [a_2, a_3] = [3, 3] $ . It can be proven that you cannot get a better score.

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: binary search, brute force, constructive algorithms, greedy, implementation
Difficulty: 1900
# Minimize Equal Sum Subarrays

## Problem Description

It is known that [Farmer John likes Permutations](https://usaco.org/index.php?page=viewproblem2&cpid=1421), but I like them too!

— Sun Tzu, The Art of Constructing Permutations



You are given a permutation $ ^{\text{∗}} $ $ p $ of length $ n $ .

Find a permutation $ q $ of length $ n $ that minimizes the number of pairs ( $ i, j $ ) ( $ 1 \leq i \leq j \leq n $ ) such that $ p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j $ .

 $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ).

The following line contains $ n $ space-separated integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \leq p_i \leq n $ ) — denoting the permutation $ p $ of length $ n $ .

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

## Output Format

For each test case, output one line containing any permutation of length $ n $ (the permutation $ q $ ) such that $ q $ minimizes the number of pairs.

## Sample #1

### Sample Input #1

```
3
2
1 2
5
1 2 3 4 5
7
4 7 5 1 2 6 3
```

### Sample Output #1

```
2 1
3 5 4 2 1
6 2 1 4 7 3 5
```

## Hint

For the first test, there exists only one pair ( $ i, j $ ) ( $ 1 \leq i \leq j \leq n $ ) such that $ p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j $ , which is ( $ 1, 2 $ ). It can be proven that no such $ q $ exists for which there are no pairs.

## Limit



Time Limit
1.50s

Memory Limit
250.00MB

Tags: constructive algorithms, math, number theory
Difficulty: 1000
# Find K Distinct Points with Fixed Center

## Problem Description

I couldn't think of a good title for this problem, so I decided to learn from LeetCode.

— Sun Tzu, The Art of War



You are given three integers $ x_c $ , $ y_c $ , and $ k $ ( $ -100 \leq x_c, y_c \leq 100 $ , $ 1 \leq k \leq 1000 $ ).

You need to find $ k $ distinct points ( $ x_1, y_1 $ ), ( $ x_2, y_2 $ ), $ \ldots $ , ( $ x_k, y_k $ ), having integer coordinates, on the 2D coordinate plane such that:

- their center $ ^{\text{∗}} $ is ( $ x_c, y_c $ )
- $ -10^9 \leq x_i, y_i \leq 10^9 $ for all $ i $ from $ 1 $ to $ k $

It can be proven that at least one set of $ k $ distinct points always exists that satisfies these conditions.

 $ ^{\text{∗}} $ The center of $ k $ points ( $ x_1, y_1 $ ), ( $ x_2, y_2 $ ), $ \ldots $ , ( $ x_k, y_k $ ) is $ \left( \frac{x_1 + x_2 + \ldots + x_k}{k}, \frac{y_1 + y_2 + \ldots + y_k}{k} \right) $ .

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases.

Each test case contains three integers $ x_c $ , $ y_c $ , and $ k $ ( $ -100 \leq x_c, y_c \leq 100 $ , $ 1 \leq k \leq 1000 $ ) — the coordinates of the center and the number of distinct points you must output.

It is guaranteed that the sum of $ k $ over all test cases does not exceed $ 1000 $ .

## Output Format

For each test case, output $ k $ lines, the $ i $ -th line containing two space separated integers, $ x_i $ and $ y_i $ , ( $ -10^9 \leq x_i, y_i \leq 10^9 $ ) — denoting the position of the $ i $ -th point.

If there are multiple answers, print any of them. It can be shown that a solution always exists under the given constraints.

## Sample #1

### Sample Input #1

```
4
10 10 1
0 0 3
-5 -8 8
4 -5 3
```

### Sample Output #1

```
10 10
-1 -1
5 -1
-4 2
-6 -7
-5 -7
-4 -7
-4 -8
-4 -9
-5 -9
-6 -9
-6 -8
1000 -1000
-996 995
8 -10
```

## Hint

For the first test case, $ \left( \frac{10}{1}, \frac{10}{1} \right) = (10, 10) $ .

For the second test case, $ \left( \frac{-1 + 5 - 4}{3}, \frac{-1 -1 + 2}{3} \right) = (0, 0) $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, implementation, math
Difficulty: 800
# Chips on a Line

## Problem Description

You have $ n $ chips, and you are going to place all of them in one of $ x $ points, numbered from $ 1 $ to $ x $ . There can be multiple chips in each point.

After placing the chips, you can perform the following four operations (in any order, any number of times):

- choose a chip in point $ i \ge 3 $ , remove it and place two chips: one in $ i-1 $ , one in $ i-2 $ ;
- choose two chips in adjacent points $ i $ and $ i+1 $ , remove them and place a new chip in $ i+2 $ ;
- choose a chip in point $ 1 $ and move it to $ 2 $ ;
- choose a chip in point $ 2 $ and move it to $ 1 $ .

Note that the coordinates of the chips you place during the operations cannot be less than $ 1 $ , but can be greater than $ x $ .

Denote the cost of chip placement as the minimum number of chips which can be present on the line after you perform these operations, starting from the placement you've chosen.

For example, the cost of placing two chips in points $ 3 $ and one chip in point $ 5 $ is $ 2 $ , because you can reduce the number of chips to $ 2 $ as follows:

- choose a chip in point $ 3 $ , remove it, place a chip in $ 1 $ and another chip in $ 2 $ ;
- choose the chips in points $ 2 $ and $ 3 $ , remove them and place a chip in $ 4 $ ;
- choose the chips in points $ 4 $ and $ 5 $ , remove them and place a chip in $ 6 $ .

You are given three integers $ n $ , $ x $ and $ m $ . Calculate the number of placements of exactly $ n $ chips in points from $ 1 $ to $ x $ having cost equal to $ m $ , and print it modulo $ 998244353 $ . Two placements are considered different if the number of chips in some point differs between these placements.

## Input Format

The only line contains three integers $ n $ , $ x $ and $ m $ ( $ 1 \le m \le n \le 1000 $ ; $ 2 \le x \le 10 $ ).

## Output Format

Print one integer — the number of placements with cost equal to $ m $ , taken modulo $ 998244353 $ .

## Sample #1

### Sample Input #1

```
2 3 1
```

### Sample Output #1

```
5
```

## Sample #2

### Sample Input #2

```
42 10 5
```

### Sample Output #2

```
902673363
```

## Sample #3

### Sample Input #3

```
1000 10 8
```

### Sample Output #3

```
187821763
```

## Hint

In the first example, there are five ways to place $ 2 $ chips in points from $ 1 $ to $ 3 $ so that the cost is $ 1 $ :

- $ (1, 1) $ ;
- $ (1, 2) $ ;
- $ (1, 3) $ ;
- $ (2, 2) $ ;
- $ (2, 3) $ .

## Limit



Time Limit
5.00s

Memory Limit
500.00MB

Tags: brute force, combinatorics, dp, greedy, math
Difficulty: 2700
# Level Up

## Problem Description

Monocarp is playing a computer game. He starts the game being level $ 1 $ . He is about to fight $ n $ monsters, in order from $ 1 $ to $ n $ . The level of the $ i $ -th monster is $ a_i $ .

For each monster in the given order, Monocarp's encounter goes as follows:

- if Monocarp's level is strictly higher than the monster's level, the monster flees (runs away);
- otherwise, Monocarp fights the monster.

After every $ k $ -th fight with a monster (fleeing monsters do not count), Monocarp's level increases by $ 1 $ . So, his level becomes $ 2 $ after $ k $ monsters he fights, $ 3 $ after $ 2k $ monsters, $ 4 $ after $ 3k $ monsters, and so on.

You need to process $ q $ queries of the following form:

- $ i~x $ : will Monocarp fight the $ i $ -th monster (or will this monster flee) if the parameter $ k $ is equal to $ x $ ?

## Input Format

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n, q \le 2 \cdot 10^5 $ ) — the number of monsters and the number of queries.

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 2 \cdot 10^5 $ ) — the levels of the monsters.

In the $ j $ -th of the following $ q $ lines, two integers $ i $ and $ x $ ( $ 1 \le i, x \le n $ ) — the index of the monster and the number of fights required for a level up in the $ j $ -th query.

## Output Format

For each query, output "YES", if Monocarp will fight the $ i $ -th monster in this query, and "NO", if the $ i $ -th monster flees.

## Sample #1

### Sample Input #1

```
4 16
2 1 2 1
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4
```

### Sample Output #1

```
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
```

## Sample #2

### Sample Input #2

```
7 15
1 1 2 1 1 1 1
5 3
2 2
2 2
1 6
5 1
5 5
7 7
3 5
7 4
4 3
2 5
1 2
5 6
4 1
6 1
```

### Sample Output #2

```
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
```

## Limit



Time Limit
4.00s

Memory Limit
500.00MB

Tags: binary search, brute force, data structures, divide and conquer, implementation
Difficulty: 2200
# Maximize the Root

## Problem Description

You are given a rooted tree, consisting of $ n $ vertices. The vertices in the tree are numbered from $ 1 $ to $ n $ , and the root is the vertex $ 1 $ . The value $ a_i $ is written at the $ i $ -th vertex.

You can perform the following operation any number of times (possibly zero): choose a vertex $ v $ which has at least one child; increase $ a_v $ by $ 1 $ ; and decrease $ a_u $ by $ 1 $ for all vertices $ u $ that are in the subtree of $ v $ (except $ v $ itself). However, after each operation, the values on all vertices should be non-negative.

Your task is to calculate the maximum possible value written at the root using the aforementioned operation.

## Input Format

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

The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree.

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the initial values written at vertices.

The third line contains $ n-1 $ integers $ p_2, p_3, \dots, p_n $ ( $ 1 \le p_i \le n $ ), where $ p_i $ is the parent of the $ i $ -th vertex in the tree. Vertex $ 1 $ is the root.

Additional constraint on the input: the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, print a single integer — the maximum possible value written at the root using the aforementioned operation.

## Sample #1

### Sample Input #1

```
3
4
0 1 0 2
1 1 3
2
3 0
1
5
2 5 3 9 6
3 1 5 2
```

### Sample Output #1

```
1
3
6
```

## Hint

In the first test case, the following sequence of operations is possible:

- perform the operation on $ v=3 $ , then the values on the vertices will be $ [0, 1, 1, 1] $ ;
- perform the operation on $ v=1 $ , then the values on the vertices will be $ [1, 0, 0, 0] $ .

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: binary search, dfs and similar, dp, greedy, trees
Difficulty: 1500
# Even Positions

## Problem Description

Monocarp had a regular bracket sequence $ s $ of length $ n $ ( $ n $ is even). He even came up with his own way to calculate its cost.

He knows that in a regular bracket sequence (RBS), each opening bracket is paired up with the corresponding closing bracket. So he decided to calculate the cost of RBS as the sum of distances between pairs of corresponding bracket pairs.

For example, let's look at RBS (())(). It has three pairs of brackets:

- (\_\_)\_\_: the distance between brackets at position $ 1 $ and at $ 4 $ is $ 4 - 1 = 3 $ ;
- \_()\_\_\_: the distance is $ 3 - 2 = 1 $ ;
- \_\_\_\_(): the distance is $ 6 - 5 = 1 $ .

 So the cost of (())() is $ 3 + 1 + 1 = 5 $ .Unfortunately, due to data corruption, Monocarp lost all characters on odd positions $ s_1, s_3, \dots, s_{n-1} $ . Only characters on even positions ( $ s_2, s_4, \dots, s_{n} $ ) remain. For example, (())() turned to \_(\_)\_).

Monocarp wants to restore his RBS by placing brackets on the odd positions. But since the restored RBS may not be unique, he wants to choose one with minimum cost. It's too hard to do for Monocarp alone, so can you help him?

Reminder: A regular bracket sequence is a string consisting of only brackets, such that this sequence, when inserted 1-s and +-s, gives a valid mathematical expression. For example, (), (()) or (()())() are RBS, while ), ()( or ())(() are not.

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 5000 $ ) — the number of test cases. Next $ t $ cases follow.

The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ; $ n $ is even) — the length of string $ s $ .

The second line of each test case contains a string $ s $ of length $ n $ , where all characters on the odd positions are '\_' and all characters on the even positions are either '(' or ')'.

Additional constraints:

- $ s $ can be restored to at least one regular bracket sequence;
- the total sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, print one integer — the minimum cost of the regular bracket sequence that can be obtained from $ s $ by replacing '\_'-s with brackets.

## Sample #1

### Sample Input #1

```
4
6
_(_)_)
2
_)
8
_)_)_)_)
8
_(_)_(_)
```

### Sample Output #1

```
5
1
4
8
```

## Hint

In the first test case, it's optimal to make $ s $ equal to (())(). The cost of $ s $ will be equal to $ 3 + 1 + 1 = 5 $ .

In the second test case, the only option is to make $ s $ equal to () with cost $ 1 $ .

In the third test case, the only possible RBS is ()()()() with cost $ 1 + 1 + 1 + 1 = 4 $ .

In the fourth test case, it's optimal to make $ s $ equal to (())(()) with cost $ 3 + 1 + 3 + 1 = 8 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, data structures, greedy
Difficulty: 1100
# Make Three Regions

## Problem Description

There is a grid, consisting of $ 2 $ rows and $ n $ columns. Each cell of the grid is either free or blocked.

A free cell $ y $ is reachable from a free cell $ x $ if at least one of these conditions holds:

- $ x $ and $ y $ share a side;
- there exists a free cell $ z $ such that $ z $ is reachable from $ x $ and $ y $ is reachable from $ z $ .

A connected region is a set of free cells of the grid such that all cells in it are reachable from one another, but adding any other free cell to the set violates this rule.

For example, consider the following layout, where white cells are free, and dark grey cells are blocked:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1997B/424d758ade46752deca8fcae4121a5c7f0d1a2fb.png) There are $ 3 $ regions in it, denoted with red, green and blue color respectively:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1997B/4fc8127700d32cdc5514e7db503c30c93554657e.png) The given grid contains at most $ 1 $ connected region. Your task is to calculate the number of free cells meeting the following constraint:

- if this cell is blocked, the number of connected regions becomes exactly $ 3 $ .

## Input Format

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

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of columns.

The $ i $ -th of the next two lines contains a description of the $ i $ -th row of the grid — the string $ s_i $ , consisting of $ n $ characters. Each character is either . (denoting a free cell) or x (denoting a blocked cell).

Additional constraint on the input:

- the given grid contains at most $ 1 $ connected region;
- the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, print a single integer — the number of cells such that the number of connected regions becomes $ 3 $ if this cell is blocked.

## Sample #1

### Sample Input #1

```
4
8
.......x
.x.xx...
2
..
..
3
xxx
xxx
9
..x.x.x.x
x.......x
```

### Sample Output #1

```
1
0
0
2
```

## Hint

In the first test case, if the cell $ (1, 3) $ is blocked, the number of connected regions becomes $ 3 $ (as shown in the picture from the statement).

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, two pointers
Difficulty: 1100
# Strong Password

## Problem Description

Monocarp's current password on Codeforces is a string $ s $ , consisting of lowercase Latin letters. Monocarp thinks that his current password is too weak, so he wants to insert exactly one lowercase Latin letter into the password to make it stronger. Monocarp can choose any letter and insert it anywhere, even before the first character or after the last character.

Monocarp thinks that the password's strength is proportional to the time it takes him to type the password. The time it takes to type the password is calculated as follows:

- the time to type the first character is $ 2 $ seconds;
- for each character other than the first, the time it takes to type it is $ 1 $ second if it is the same as the previous character, or $ 2 $ seconds otherwise.

For example, the time it takes to type the password abacaba is $ 14 $ ; the time it takes to type the password a is $ 2 $ ; the time it takes to type the password aaabacc is $ 11 $ .

You have to help Monocarp — insert a lowercase Latin letter into his password so that the resulting password takes the maximum possible amount of time to type.

## Input Format

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

Each test case consists of one line containing the string $ s $ ( $ 1 \le |s| \le 10 $ ), consisting of lowercase Latin letters.

## Output Format

For each test case, print one line containing the new password — a string which can be obtained from $ s $ by inserting one lowercase Latin letter. The string you print should have the maximum possible required time to type it. If there are multiple answers, print any of them.

## Sample #1

### Sample Input #1

```
4
a
aaa
abb
password
```

### Sample Output #1

```
wa
aada
abcb
pastsword
```

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: brute force, implementation, strings
Difficulty: 800