1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Make It Equal
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2100
Tags: binary search, brute force, greedy, math

You are given an integer array $$$a$$$ of size $$$n$$$. The elements of the array are numbered from $$$1$$$ to $$$n$$$.

You can perform the following operation any number of times (possibly, zero): choose an index $$$i$$$ from $$$1$$$ to $$$n$$$; decrease $$$a_i$$$ by $$$2$$$ and increase $$$a_{(i \bmod n) + 1}$$$ by $$$1$$$.

After you perform the operations, all elements of the array should be non-negative equal integers.

Your task is to calculate the minimum number of operations you have to perform.

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 second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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 minimum number of operations you have to perform. If it is impossible to make all elements of the array equal, print -1.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
3
2
1 1
3
1 3 2
4
2 1 2 6

Example output:
0
-1
3

Editorial:
DIY
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 1400
Tags: data structures, geometry, greedy, sortings

You are given a list of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. You need to pick $$$8$$$ elements from the list and use them as coordinates of four points. These four points should be corners of a rectangle which has its sides parallel to the coordinate axes. Your task is to pick coordinates in such a way that the resulting rectangle has the maximum possible area. The rectangle can be degenerate, i. e. its area can be $$$0$$$. Each integer can be used as many times as it occurs in the list (or less).

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 25\,000$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$8 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

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

Output format:
For each test case, print the answer as follows:

- if it is impossible to construct a rectangle which meets the constraints from the statement, print a single line containing the word NO (case-insensitive);
- otherwise, in the first line, print YES (case-insensitive). In the second line, print $$$8$$$ integers $$$x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4$$$ — the coordinates of the corners of the rectangle. You can print the corners in any order.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
3
16
-5 1 1 2 2 3 3 4 4 5 5 6 6 7 7 10
8
0 0 -1 2 2 1 1 3
8
0 0 0 0 0 5 0 5

Example output:
YES
1 2 1 7 6 2 6 7
NO
YES
0 0 0 5 0 0 0 5

Editorial:
Divide OR Conquer
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2400
Tags: binary search, bitmasks, data structures, dp, implementation

You are given an array $$$[a_1, a_2, \ldots a_n]$$$ consisting of integers between $$$0$$$ and $$$10^9$$$. You have to split this array into several segments (possibly one) in such a way that each element belongs to exactly one segment.

Let the first segment be the array $$$[a_{l_1}, a_{l_1 + 1}, \ldots, a_{r_1}]$$$, the second segment be $$$[a_{l_2}, a_{l_2+ 1}, \ldots, a_{r_2}]$$$, ..., the last segment be $$$[a_{l_k}, a_{l_k+ 1}, \ldots, a_{r_k}]$$$. Since every element should belong to exactly one array, $$$l_1 = 1$$$, $$$r_k = n$$$, and $$$r_i + 1 = l_{i+1}$$$ for each $$$i$$$ from $$$1$$$ to $$$k-1$$$. The split should meet the following condition: $$$f([a_{l_1}, a_{l_1 + 1}, \ldots, a_{r_1}]) \le f([a_{l_2}, a_{l_2+ 1}, \ldots, a_{r_2}]) \le \dots \le f([a_{l_k}, a_{l_k+1}, \ldots, a_{r_k}])$$$, where $$$f(a)$$$ is the bitwise OR of all elements of the array $$$a$$$.

Calculate the number of ways to split the array, and print it modulo $$$998\,244\,353$$$. Two ways are considered different if the sequences $$$[l_1, r_1, l_2, r_2, \ldots, l_k, r_k]$$$ denoting the splits are different.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10 ^9$$$) — the elements of the given array.

Output format:
Print one integer — the number of ways to split the array, taken modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first two examples, every way to split the array is valid.

In the third example, there are three valid ways to split the array:

- $$$k = 3$$$; $$$l_1 = 1, r_1 = 1, l_2 = 2, r_2 = 2, l_3 = 3, r_3 = 3$$$; the resulting arrays are $$$[3]$$$, $$$[4]$$$, $$$[6]$$$, and $$$3 \le 4 \le 6$$$;
- $$$k = 2$$$; $$$l_1 = 1, r_1 = 1, l_2 = 2, r_2 = 3$$$; the resulting arrays are $$$[3]$$$ and $$$[4, 6]$$$, and $$$3 \le 6$$$;
- $$$k = 1$$$; $$$l_1 = 1, r_1 = 3$$$; there will be only one array: $$$[3, 4, 6]$$$.

If you split the array into two arrays $$$[3, 4]$$$ and $$$[6]$$$, the bitwise OR of the first array is $$$7$$$, and the bitwise OR of the second array is $$$6$$$; $$$7 > 6$$$, so this way to split the array is invalid.

Example input:
3
1 2 3

Example output:
4

Example input:
5
1000 1000 1000 1000 1000

Example output:
16

Editorial:
Barrels
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2900
Tags: data structures, greedy, math

Suppose you have $$$n$$$ water barrels standing in a row, numbered from $$$1$$$ to $$$n$$$.

All barrels are equal and have a bottom area equal to one unit, so the volume of the water inside a barrel is equal to the height of the water column. Initially, the $$$i$$$-th barrel has $$$v_i$$$ units of water.

Adjacent barrels are connected by pipes. In other words, for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, barrels $$$i$$$ and $$$i + 1$$$ are connected by a single horizontal pipe at height $$$h_i$$$. The widths of the pipes are negligible. These pipes allow water to flow between barrels.

Now you want to play with barrels. Your plan is to maximize the volume of the water in the first barrel by throwing clay into barrels. In one step, you can choose any barrel and throw one unit of clay into it. One unit of clay has the same volume as one unit of water. Clay is heavier than water and doesn't mix with it, so it falls to the bottom of the barrel, distributing evenly.

Clay has a sticky structure, so it seals pipes if the clay column is high enough. More formally, suppose the pipe is at height $$$h$$$. If the height of the clay column is also $$$\boldsymbol{h}$$$ (or lower), the pipe is working. But the moment you add more clay into the barrel, the pipe becomes sealed instantly, preventing any water from moving between barrels.

You have a mountain of clay, so you can repeat the step described above any number of times. However, between the steps, you have to wait until the water reaches the new equilibrium.

What is the maximum water volume you can collect in the first barrel?

Assume that the barrels are high enough, so the water doesn't overflow, and the pipe widths are negligible.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of barrels.

The second line contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$0 \le v_i \le 10^6$$$), where $$$v_i$$$ is the initial water volume in the $$$i$$$-th barrel.

The third line contains $$$n - 1$$$ integers $$$h_1, h_2, \dots, h_{n - 1}$$$ ($$$1 \le h_i \le 10^6$$$), where $$$h_i$$$ is the height of the pipe between the $$$i$$$-th and the $$$(i + 1)$$$-st barrel.

Additional constraint on the input: the given water heights are in an equilibrium.

Output format:
Print a single number — the maximum volume of water in the first barrel. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
An optimal strategy for the first example is shown in the picture below:

Example input:
2
1 2
2

Example output:
2.500000000000000

Example input:
3
3 0 0
6 9

Example output:
3.000000000000000

Editorial:
Alternative Platforms
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2500
Tags: combinatorics, data structures, fft, math, sortings

Suppose you are working in the Ministry of Digital Development of Berland, and your task is to monitor the industry of video blogging.

There are $$$n$$$ bloggers in Berland. Recently, due to the poor state of the main video platform in Berland, two alternative platforms were introduced. That's why bloggers started to reupload their videos to these alternative platforms. You've got the statistics that the $$$i$$$-th blogger uploaded $$$v_i$$$ videos to the first alternative platform and $$$r_i$$$ videos to the second alternative platform.

You think that a potential user will be upset if even at least one of his favorite bloggers doesn't upload anything. However, if a blogger uploads videos to both platforms, the user will watch that blogger on the platform where more videos are available. So, you've come up with the following function to estimate user experience. Suppose a user watches $$$k$$$ bloggers $$$b_1, b_2, \dots, b_k$$$; then, let user experience be $$$$$$E(b_1, \dots, b_k) = \max\left(\min_{i=1..k}{v[b_i]}, \min_{i=1..k}{r[b_i]}\right).$$$$$$

In order to get some statistics, you want to calculate the value $$$\mathit{avg}_k$$$ that is equal to an average experience among all subsets of bloggers of size $$$k$$$. Also, you have to calculate $$$\mathit{avg}_k$$$ for each $$$k$$$ from $$$1$$$ to $$$n$$$.

Since answers may be too large, print them modulo $$$998\,244\,353$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of bloggers.

The second line contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$0 \le v_i \le 10^6$$$), where $$$v_i$$$ is the number of videos of the $$$i$$$-th blogger on the first alternative platform.

The third line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$0 \le r_i \le 10^6$$$), where $$$r_i$$$ is the number of videos of the $$$i$$$-th blogger on the second alternative platform.

Output format:
Print $$$n$$$ integers $$$\mathit{avg}_1, \mathit{avg}_2, \dots, \mathit{avg}_n$$$.

It can be proven that $$$\mathit{avg}_k$$$ may be represented as an irreducible fraction $$$\dfrac{x}{y}$$$ where $$$y \not\equiv 0 \pmod{998\,244\,353}$$$. So, print $$$\mathit{avg}_k$$$ in a form $$$x \cdot y^{-1} \bmod 998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, $$$332748119$$$ is $$$\frac{4}{3}$$$. In the third example, $$$199648873$$$ is $$$\frac{12}{5}$$$.

Example input:
3
2 1 2
1 2 1

Example output:
2 332748119 1

Example input:
4
5 5 5 5
0 0 0 0

Example output:
5 5 5 5

Editorial:
Galactic Council
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 3000
Tags: flows

Monocarp plays a computer game. In this game, he maintains a space empire. The empire is governed by $$$n$$$ political parties. Initially, every party has political power equal to $$$0$$$, and there is no ruling party.

During each of the next $$$m$$$ turns, the following happens:

1. initially, Monocarp has to choose which party he supports. He can support any party, except for the ruling party. When Monocarp supports a party, its political power is increased by $$$1$$$. If Monocarp supports the $$$i$$$-th party during the $$$j$$$-th turn, his score increases by $$$a_{i,j}$$$ points;
2. then, the elections happen, and the party with the maximum political power is chosen as the ruling party (if there are multiple such parties, the party with the lowest index among them is chosen). The former ruling party is replaced, unless it is chosen again;
3. finally, an event happens. At the end of the $$$j$$$-th turn, the party $$$p_j$$$ must be the ruling party to prevent a bad outcome of the event, otherwise Monocarp loses the game.

Determine which party Monocarp has to support during each turn so that he doesn't lose the game due to the events, and the score he achieves is the maximum possible. Initially, Monocarp's score is $$$0$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 50$$$) — the number of political parties and the number of turns, respectively.

The second line contains $$$m$$$ integers $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_j \le n$$$), where $$$p_j$$$ is the index of the party which should be the ruling party at the end of the $$$j$$$-th turn.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^5$$$), where $$$a_{i,j}$$$ is the amount of points Monocarp gets if he supports the $$$i$$$-th party during the $$$j$$$-th turn.

Output format:
If Monocarp loses the game no matter how he acts, print one integer $$$-1$$$.

Otherwise, print $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_j \le n$$$), where $$$c_j$$$ is the index of the party Monocarp should support during the $$$j$$$-th turn. If there are multiple answers, print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
2 3
2 1 2
1 2 3
4 5 6

Example output:
2 1 2

Example input:
3 5
1 1 1 2 1
1 1 1 1 1
10 5 7 8 15
7 10 9 8 15

Example output:
1 3 2 2 1

Editorial:
Waiting for...
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 800
Tags: greedy, implementation

Monocarp is waiting for a bus at the bus stop. Unfortunately, there are many people who want to ride a bus too.

You are given a list of events of two types:

- B $$$b_i$$$ — a bus with $$$b_i$$$ free seats arrives at the stop;
- P $$$p_i$$$ — $$$p_i$$$ people arrive at the stop.

These events are listed in a chronological order.

When a bus arrives, the following happens. All people at the bus stop (except for Monocarp) try to enter the bus. If there are enough free seats for all of them, then they all enter the bus. Otherwise, some people remain at the bus stop (the number of people who enter the bus is equal to the number of free seats).

If there is still at least one free seat after all people (except for Monocarp) enter the bus, then Monocarp can decide to enter this bus as well (but he might choose to wait for another bus). For each bus, you have to determine if it is possible for Monocarp to take that bus.

Input format:
The first line contains one integer $$$n$$$ $$$(1 \le n \le 10^3)$$$ — the number of events.

Then, $$$n$$$ lines follow. The $$$i$$$-th of them contains the description of the $$$i$$$-th event in one of the two following formats:

- B $$$b_i$$$ ($$$1 \le b_i \le 10^6$$$) — a bus with $$$b_i$$$ free seats arrives at the stop;
- P $$$p_i$$$ ($$$1 \le p_i \le 10^6$$$) — $$$p_i$$$ people arrive at the stop.

Additional constraint on the input: there is at least one event of type B.

Output format:
For each event of type B, print YES if it is possible for Monocarp to take the corresponding bus, or NO otherwise (case-insensitive).

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
10
P 2
P 5
B 8
P 14
B 5
B 9
B 3
P 2
B 1
B 2

Example output:
YES
NO
NO
YES
NO
YES

Editorial:
Grid Walk
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2100
Tags: brute force, dp, greedy, math, number theory

You have an $$$n \times n$$$ grid and two integers $$$a$$$ and $$$b$$$. Both the rows and the columns are numbered from $$$1$$$ to $$$n$$$. Let's denote the cell at the intersection of the $$$i$$$-th row and the $$$j$$$-th column as $$$(i, j)$$$.

You are standing in the cell $$$(1, 1)$$$ and want to move into the cell $$$(n, n)$$$.

Suppose you are in the cell $$$(i, j)$$$; in one step, you can move either into the cell $$$(i, j + 1)$$$ or into the cell $$$(i + 1, j)$$$ if the corresponding cells exist.

Let's define the cost of the cell $$$(i, j)$$$ as $$$c(i, j) = \gcd(i, a) + \gcd(j, b)$$$ (here, $$$\gcd(x,y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$). The cost of the route from $$$(1, 1)$$$ to $$$(n, n)$$$ is the sum of costs of the visited cells (including the starting cell and the finishing cell).

Find the route with minimum possible cost and print its cost.

Input format:
The only line contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$2 \le n \le 10^6$$$; $$$1 \le a, b \le 10^6$$$).

Output format:
Print one integer — the cost of the cheapest route from $$$(1, 1)$$$ to $$$(n, n)$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
The first example is described in the picture above.

Example input:
4 2 4

Example output:
21

Example input:
10 210 420

Example output:
125

Editorial:
Bridge Renovation
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 1400
Tags: brute force, dp, greedy, math, two pointers

Recently, Monocarp started working as a director of a park located near his house. The park is quite large, so it even has a small river splitting it into several zones. Several bridges are built across this river. Three of these bridges are especially old and need to be repaired.

All three bridges have the same length but differ in width. Their widths are $$$18$$$, $$$21$$$ and $$$25$$$ units, respectively.

During the park renovation process, Monocarp has to replace the old planks that served as the surface of the bridges with the new ones.

Planks are sold with a standard length of $$$60$$$ units. Monocarp already knows that he needs $$$n$$$ planks for each bridge. But since the bridges have different widths, he needs $$$n$$$ planks of length $$$18$$$ for the first bridge, $$$n$$$ planks of length $$$21$$$ for the second one, and $$$n$$$ planks of length $$$25$$$ for the last one.

Workers in charge of renovation have no problem with cutting planks into parts but refuse to join planks, since it creates weak spots and looks ugly.

Monocarp wants to buy as few planks as possible but struggles to calculate the required number of planks. Can you help him?

Input format:
The first and only line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of planks required for each of the three bridges.

Output format:
Print a single integer — the minimum number of planks of standard length ($$$60$$$ units) Monocarp needs to cover all three bridges if the planks can be cut into parts.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, it is possible to cut one plank of length $$$60$$$ into three planks with lengths $$$25$$$, $$$18$$$ and $$$17$$$, and cut another plank of length $$$60$$$ into two planks with lengths $$$39$$$ and $$$21$$$. That way, Monocarp will have all the required planks.

Example input:
1

Example output:
2

Example input:
3

Example output:
4

Editorial:
Royal Flush
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2800
Tags: dp, implementation

Consider the following game. There is a deck, which consists of cards of $$$n$$$ different suits. For each suit, there are $$$13$$$ cards in the deck, all with different ranks (the ranks are $$$2$$$, $$$3$$$, $$$4$$$, ..., $$$10$$$, Jack, Queen, King and Ace).

Initially, the deck is shuffled randomly (all $$$(13n)!$$$ possible orders of cards have the same probability). You draw $$$5$$$ topmost cards from the deck. Then, every turn of the game, the following events happen, in the given order:

1. if the cards in your hand form a Royal Flush (a $$$10$$$, a Jack, a Queen, a King, and an Ace, all of the same suit), you win, and the game ends;
2. if you haven't won yet, and the deck is empty, you lose, and the game ends;
3. if the game hasn't ended yet, you may choose any cards from your hand (possibly, all of them) and discard them. When a card is discarded, it is removed from the game;
4. finally, you draw cards from the deck, until you have $$$5$$$ cards or the deck becomes empty.

Your goal is to find a strategy that allows you to win in the minimum expected number of turns. Note that the turn when the game ends is not counted (for example, if the $$$5$$$ cards you draw initially already form a Royal Flush, you win in $$$0$$$ turns).

Calculate the minimum possible expected number of turns required to win the game.

Input format:
The only line contains one integer $$$n$$$ ($$$1 \le n \le 4$$$) — the number of suits used in the game.

Output format:
Print the minimum expected number of turns.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer will be accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
1

Example output:
3.598290598

Example input:
2

Example output:
8.067171309

Editorial:
Fixing the Expression
Contest: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 800
Tags: implementation

An expression is a string consisting of three characters, where the first and the last characters are digits (from $$$0$$$ to $$$9$$$), and the middle character is a comparison symbol (<, = or >).

An expression is true if the comparison symbol matches the digits (for example, if the first digit is strictly less than the last digit, the comparison symbol should be <).

For example, the expressions 1<3, 4>2, 0=0 are true, while 5>5, 7<3 are not.

You are given a string $$$s$$$, which is an expression. Change as few characters as possible so that $$$s$$$ becomes a true expression. Note that if $$$s$$$ is already true, you should leave it as it is.

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

Each test case consists of one line containing the string $$$s$$$ ($$$|s| = 3$$$, the first and the last characters of $$$s$$$ are digits, the second character is a comparison symbol).

Output format:
For each test case, print a string consisting of $$$3$$$ characters — a true expression which can be obtained by changing as few characters as possible in $$$s$$$. If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
5
3<7
3>7
8=9
0=0
5<3

Example output:
3<7
8>7
8<9
0=0
0<3

Editorial: