1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Garbage Disposal
Contest: 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1300
Tags: greedy

Enough is enough. Too many times it happened that Vasya forgot to dispose of garbage and his apartment stank afterwards. Now he wants to create a garbage disposal plan and stick to it.

For each of next $$$n$$$ days Vasya knows $$$a_i$$$ — number of units of garbage he will produce on the $$$i$$$-th day. Each unit of garbage must be disposed of either on the day it was produced or on the next day. Vasya disposes of garbage by putting it inside a bag and dropping the bag into a garbage container. Each bag can contain up to $$$k$$$ units of garbage. It is allowed to compose and drop multiple bags into a garbage container in a single day.

Being economical, Vasya wants to use as few bags as possible. You are to compute the minimum number of bags Vasya needs to dispose of all of his garbage for the given $$$n$$$ days. No garbage should be left after the $$$n$$$-th day.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2\cdot10^5, 1 \le k \le 10^9$$$) — number of days to consider and bag's capacity. The second line contains $$$n$$$ space separated integers $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) — the number of units of garbage produced on the $$$i$$$-th day.

Output format:
Output a single integer — the minimum number of bags Vasya needs to dispose of all garbage. Each unit of garbage should be disposed on the day it was produced or on the next day. No garbage can be left after the $$$n$$$-th day. In a day it is allowed to compose and drop multiple bags.

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

Example input:
3 2
3 2 1

Example output:
3

Example input:
5 1
1000000000 1000000000 1000000000 1000000000 1000000000

Example output:
5000000000

Editorial:
For the first day it is obvious that Vasya should dispose of all garbage produced on that day which fully fills some bags. Or mathematically speaking Vasya should dispose of $$$\lfloor a_1 / k \rfloor$$$ number of full bags. After that $$$a_1 \pmod k$$$ units of garbage remain, which does not fully fill a bag. Vasya loses nothing if he leaves that garbage for the next day, so that is what he should do.
Now, on day $$$i$$$ $$$(i \gt 1)$$$ Vasya has $$$a_i$$$ units of garbage produced on that day and $$$r$$$ $$$(0 \le r \lt k)$$$ units of garbage left from day $$$i - 1$$$. If $$$r$$$ is strictly greater than $$$0$$$, then Vasya must dispose of these $$$r$$$ units of garbage on day $$$i$$$. Obviously he should add garbage produced on day $$$i$$$ to that bag, so that he disposes of as much garbage as possible with the bag. Lets say that afterwards $$$t$$$ $$$(0 \le t \le a_i)$$$ units of garbage remains. Like on day $$$1$$$, Vasya should dispose of all garbage which fully fills some bags and leave the rest for day $$$i+1$$$.
Iterating with the given greedy algorithm through all $$$n$$$ days yields the total number of bags needed to dispose of all the garbage. The solution requires $$$O(n)$$$ time and $$$O(1)$$$ additional memory.
Debate
Contest: 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1500
Tags: greedy

Elections in Berland are coming. There are only two candidates — Alice and Bob.

The main Berland TV channel plans to show political debates. There are $$$n$$$ people who want to take part in the debate as a spectator. Each person is described by their influence and political views. There are four kinds of political views:

- supporting none of candidates (this kind is denoted as "00"),
- supporting Alice but not Bob (this kind is denoted as "10"),
- supporting Bob but not Alice (this kind is denoted as "01"),
- supporting both candidates (this kind is denoted as "11").

The direction of the TV channel wants to invite some of these people to the debate. The set of invited spectators should satisfy three conditions:

- at least half of spectators support Alice (i.e. $$$2 \cdot a \ge m$$$, where $$$a$$$ is number of spectators supporting Alice and $$$m$$$ is the total number of spectators),
- at least half of spectators support Bob (i.e. $$$2 \cdot b \ge m$$$, where $$$b$$$ is number of spectators supporting Bob and $$$m$$$ is the total number of spectators),
- the total influence of spectators is maximal possible.

Help the TV channel direction to select such non-empty set of spectators, or tell that this is impossible.

Input format:
The first line contains integer $$$n$$$ ($$$1 \le n \le 4\cdot10^5$$$) — the number of people who want to take part in the debate as a spectator.

These people are described on the next $$$n$$$ lines. Each line describes a single person and contains the string $$$s_i$$$ and integer $$$a_i$$$ separated by space ($$$1 \le a_i \le 5000$$$), where $$$s_i$$$ denotes person's political views (possible values — "00", "10", "01", "11") and $$$a_i$$$ — the influence of the $$$i$$$-th person.

Output format:
Print a single integer — maximal possible total influence of a set of spectators so that at least half of them support Alice and at least half of them support Bob. If it is impossible print 0 instead.

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

Note:
In the first example $$$4$$$ spectators can be invited to maximize total influence: $$$1$$$, $$$2$$$, $$$3$$$ and $$$6$$$. Their political views are: "11", "10", "01" and "00". So in total $$$2$$$ out of $$$4$$$ spectators support Alice and $$$2$$$ out of $$$4$$$ spectators support Bob. The total influence is $$$6+4+3+9=22$$$.

In the second example the direction can select all the people except the $$$5$$$-th person.

In the third example the direction can select people with indices: $$$1$$$, $$$4$$$, $$$5$$$ and $$$6$$$.

In the fourth example it is impossible to select any non-empty set of spectators.

Example input:
6
11 6
10 4
01 3
00 3
00 7
00 9

Example output:
22

Example input:
5
11 1
01 1
00 100
10 1
01 1

Example output:
103

Editorial:
BerOS File Suggestion
Contest: 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1500
Tags: brute force, implementation

Polycarp is working on a new operating system called BerOS. He asks you to help with implementation of a file suggestion feature.

There are $$$n$$$ files on hard drive and their names are $$$f_1, f_2, \dots, f_n$$$. Any file name contains between $$$1$$$ and $$$8$$$ characters, inclusive. All file names are unique.

The file suggestion feature handles queries, each represented by a string $$$s$$$. For each query $$$s$$$ it should count number of files containing $$$s$$$ as a substring (i.e. some continuous segment of characters in a file name equals $$$s$$$) and suggest any such file name.

For example, if file names are "read.me", "hosts", "ops", and "beros.18", and the query is "os", the number of matched files is $$$2$$$ (two file names contain "os" as a substring) and suggested file name can be either "hosts" or "beros.18".

Input format:
The first line of the input contains integer $$$n$$$ ($$$1 \le n \le 10000$$$) — the total number of files.

The following $$$n$$$ lines contain file names, one per line. The $$$i$$$-th line contains $$$f_i$$$ — the name of the $$$i$$$-th file. Each file name contains between $$$1$$$ and $$$8$$$ characters, inclusive. File names contain only lowercase Latin letters, digits and dot characters ('.'). Any sequence of valid characters can be a file name (for example, in BerOS ".", ".." and "..." are valid file names). All file names are unique.

The following line contains integer $$$q$$$ ($$$1 \le q \le 50000$$$) — the total number of queries.

The following $$$q$$$ lines contain queries $$$s_1, s_2, \dots, s_q$$$, one per line. Each $$$s_j$$$ has length between $$$1$$$ and $$$8$$$ characters, inclusive. It contains only lowercase Latin letters, digits and dot characters ('.').

Output format:
Print $$$q$$$ lines, one per query. The $$$j$$$-th line should contain the response on the $$$j$$$-th query — two values $$$c_j$$$ and $$$t_j$$$, where

- $$$c_j$$$ is the number of matched files for the $$$j$$$-th query,
- $$$t_j$$$ is the name of any file matched by the $$$j$$$-th query. If there is no such file, print a single character '-' instead. If there are multiple matched files, print any.

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

Example input:
4
test
contests
test.
.test
6
ts
.
st.
.test
contes.
st

Example output:
1 contests
2 .test
1 test.
1 .test
0 -
4 test.

Editorial:
For each file name $$$f_i$$$ consider all distinct substrings. There are at most $$$7\cdot8/2=28$$$ for file name of length $$$8$$$. Use map<string,int> counts and map<string,string> representative to store responses for each substring. Processing a file name $$$f_i$$$ iterate over all its distinct substrings $$$t$$$ and do counts[t]++ and representative[t] = f_i.
After processing all $$$f_i$$$ two maps counts and representative store responses. Just print counts[s_j] and representative[s_j] (or "0 -" if there is no such keys in the maps).
Privatization of Roads in Berland
Contest: 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 2400
Tags: flows, graph matchings, graphs

There are $$$n$$$ cities and $$$m$$$ two-way roads in Berland, each road connecting two distinct cities.

Recently the Berland government has made a tough decision to transfer ownership of the roads to private companies. In total, there are $$$100500$$$ private companies in Berland, numbered by integers from $$$1$$$ to $$$100500$$$. After the privatization, every road should belong to exactly one company.

The anti-monopoly committee demands that after the privatization each company can own at most two roads. The urbanists of Berland also stated their opinion: each city should be adjacent to the roads owned by at most $$$k$$$ companies.

Help the government to distribute the roads between the companies so that both conditions are satisfied. That is, each company gets at most two roads, and each city has roads of at most $$$k$$$ distinct companies adjacent to it.

Input format:
Input contains one or several test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 300$$$) — the number of test cases in the input. Solve test cases separately, test cases are completely independent and do not affect each other.

The following lines describe the test cases. Each case starts with a line consisting of three space-separated integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 600$$$, $$$1 \le m \le 600$$$, $$$1 \le k \le n - 1$$$) — the number of cities, the number of roads and the maximum diversity of the roads adjacent to a city.

Then $$$m$$$ lines follow, each having a pair of space-separated integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$; $$$a_i \ne b_i$$$). It means that the $$$i$$$-th road connects cities $$$a_i$$$ and $$$b_i$$$. All roads are two-way. There is at most one road between a pair of the cities.

The sum of $$$n$$$ values for all test cases doesn't exceed $$$600$$$. The sum of $$$m$$$ values for all test cases doesn't exceed $$$600$$$.

Output format:
Print $$$t$$$ lines: the $$$i$$$-th line should contain the answer for the $$$i$$$-th test case. For a test case, print a sequence of integers $$$c_1, c_2, \dots, c_m$$$ separated by space, where $$$c_i$$$ ($$$1 \le c_i \le 100500$$$) is the company which owns the $$$i$$$-th road in your plan. If there are multiple solutions, output any of them. If there is no solution for a test case, print $$$c_1=c_2=\ldots=c_m=0$$$.

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

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

Example output:
1 2 3
2 1 1 2 3
0 0 0 0 0 0

Editorial:
Streets and Avenues in Berhattan
Contest: 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 2300
Tags: dp

Berhattan is the capital of Berland. There are $$$n$$$ streets running parallel in the east-west direction (horizontally), and there are $$$m$$$ avenues running parallel in the south-north direction (vertically). Each street intersects with each avenue, forming a crossroad. So in total there are $$$n \cdot m$$$ crossroads in Berhattan.

Recently, the government has changed in Berland. The new government wants to name all avenues and all streets after heroes of revolution.

The special committee prepared the list of $$$k$$$ names. Only these names can be used as new names for streets and avenues. Each name can be used at most once.

The members of committee want to name streets and avenues in the way that minimizes inconvenience for residents. They believe that if street and avenue names start with the same letter, then their crossroad will be inconvenient. Hence only the first letter of each name matters.

Given first letters of $$$k$$$ names, find $$$C$$$ — minimal possible number of inconvenient crossroads in Berhattan after the naming process.

Input format:
Input contains one or several test cases to process. The first line contains $$$t$$$ ($$$1 \le t \le 30000$$$) — the number of test cases. Solve test cases separately, test cases are completely independent and do not affect each other.

The description of $$$t$$$ test cases follows. Each test case starts with line with space-separated numbers $$$n, m, k$$$ ($$$1 \le n,m \le 30000$$$; $$$n+m \le k \le 2\cdot10^5$$$) — the number of streets, number of avenues and the number of names in the committee's list, respectively.

The the second line of each test case contains a string of $$$k$$$ uppercase English letters. $$$i$$$-th letter of the string is the first letter of $$$i$$$-th name from the committee's list.

It's guaranteed that the sum of numbers $$$n$$$ from all test cases is not greater than $$$30000$$$. Similarly, the sum of numbers $$$m$$$ from all test cases is not greater than $$$30000$$$. The sum of numbers $$$k$$$ from all test cases is not greater than $$$2\cdot10^5$$$.

Output format:
For each test case print single number $$$C$$$ in the separate line — minimal possible number of inconvenient crossroads in Berhattan after the naming process.

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

Example input:
2
2 3 9
EEZZEEZZZ
2 7 9
EEZZEEZZZ

Example output:
0
4

Example input:
2
4 4 8
CZBBCZBC
1 1 4
TTCT

Example output:
1
0

Editorial:
Video Posts
Contest: 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1100
Tags: implementation

Polycarp took $$$n$$$ videos, the duration of the $$$i$$$-th video is $$$a_i$$$ seconds. The videos are listed in the chronological order, i.e. the $$$1$$$-st video is the earliest, the $$$2$$$-nd video is the next, ..., the $$$n$$$-th video is the last.

Now Polycarp wants to publish exactly $$$k$$$ ($$$1 \le k \le n$$$) posts in Instabram. Each video should be a part of a single post. The posts should preserve the chronological order, it means that the first post should contain one or more of the earliest videos, the second post should contain a block (one or more videos) going next and so on. In other words, if the number of videos in the $$$j$$$-th post is $$$s_j$$$ then:

- $$$s_1+s_2+\dots+s_k=n$$$ ($$$s_i>0$$$),
- the first post contains the videos: $$$1, 2, \dots, s_1$$$;
- the second post contains the videos: $$$s_1+1, s_1+2, \dots, s_1+s_2$$$;
- the third post contains the videos: $$$s_1+s_2+1, s_1+s_2+2, \dots, s_1+s_2+s_3$$$;
- ...
- the $$$k$$$-th post contains videos: $$$n-s_k+1,n-s_k+2,\dots,n$$$.

Polycarp is a perfectionist, he wants the total duration of videos in each post to be the same.

Help Polycarp to find such positive integer values $$$s_1, s_2, \dots, s_k$$$ that satisfy all the conditions above.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^5$$$). The next line contains $$$n$$$ positive integer numbers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$), where $$$a_i$$$ is the duration of the $$$i$$$-th video.

Output format:
If solution exists, print "Yes" in the first line. Print $$$k$$$ positive integers $$$s_1, s_2, \dots, s_k$$$ ($$$s_1+s_2+\dots+s_k=n$$$) in the second line. The total duration of videos in each post should be the same. It can be easily proven that the answer is unique (if it exists).

If there is no solution, print a single line "No".

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

Example input:
6 3
3 3 1 4 1 6

Example output:
Yes
2 3 1

Example input:
3 3
1 1 1

Example output:
Yes
1 1 1

Editorial:
To find the duration of a single post calculate $$$c = (a_1 + a_2 + \dots + a_n) / k$$$ (if it is not an integer number then print "No"). After it you can split $$$a_i$$$ on posts with a single scan from left to right. You can iterate over $$$a_1, a_2, \dots, a_n$$$ from the left to the right: find the videos of the first post, after it find the videos of the second post and so on. Print "No" if you can't compose a post of duration $$$c$$$ with a sequence of adjacent videos.
Minimums and Maximums
Contest: Educational Codeforces Round 128 (Rated for Div. 2)
Difficulty rating: 800
Tags: brute force, math

An array is beautiful if both of the following two conditions meet:

- there are at least $$$l_1$$$ and at most $$$r_1$$$ elements in the array equal to its minimum;
- there are at least $$$l_2$$$ and at most $$$r_2$$$ elements in the array equal to its maximum.

For example, the array $$$[2, 3, 2, 4, 4, 3, 2]$$$ has $$$3$$$ elements equal to its minimum ($$$1$$$-st, $$$3$$$-rd and $$$7$$$-th) and $$$2$$$ elements equal to its maximum ($$$4$$$-th and $$$5$$$-th).

Another example: the array $$$[42, 42, 42]$$$ has $$$3$$$ elements equal to its minimum and $$$3$$$ elements equal to its maximum.

Your task is to calculate the minimum possible number of elements in a beautiful array.

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

Each test case consists of one line containing four integers $$$l_1$$$, $$$r_1$$$, $$$l_2$$$ and $$$r_2$$$ ($$$1 \le l_1 \le r_1 \le 50$$$; $$$1 \le l_2 \le r_2 \le 50$$$).

Output format:
For each test case, print one integer — the minimum possible number of elements in a beautiful array.

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

Note:
Optimal arrays in the test cases of the example:

1. $$$[1, 1, 1, 1]$$$, it has $$$4$$$ minimums and $$$4$$$ maximums;
2. $$$[4, 4, 4, 4, 4]$$$, it has $$$5$$$ minimums and $$$5$$$ maximums;
3. $$$[1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2]$$$, it has $$$3$$$ minimums and $$$10$$$ maximums;
4. $$$[8, 8, 8]$$$, it has $$$3$$$ minimums and $$$3$$$ maximums;
5. $$$[4, 6, 6]$$$, it has $$$1$$$ minimum and $$$2$$$ maximums;
6. $$$[3, 4, 3]$$$, it has $$$2$$$ minimums and $$$1$$$ maximum;
7. $$$[5, 5, 5, 5, 5, 5]$$$, it has $$$6$$$ minimums and $$$6$$$ maximums.

Example input:
7
3 5 4 6
5 8 5 5
3 3 10 12
1 5 3 3
1 1 2 2
2 2 1 1
6 6 6 6

Example output:
4
5
13
3
3
3
6

Editorial:
Firstly, since we are interested in minimum possible size of the array, we don't need any elements other than minimums and maximums. So, the array has at most $$$2$$$ distinct elements.
Now there are many possible solutions. The simplest one is to iterate on the number of minimums (let this be $$$i$$$) and maximums (let this be $$$j$$$). If the number of minimums is equal to the number of maximums, then the array should have all elements as both its minimums and maximums, so its length should be $$$i$$$; otherwise, it should be $$$i + j$$$. We can iterate on all possible pairs $$$(i, j)$$$ and find the best result over all of them.
A solution in $$$O(1)$$$ is possible if you see that you only have to consider $$$l_1$$$ and $$$l_2$$$ as the number of minimums/maximums, or check if the segments $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ intersect in $$$O(1)$$$.
Unit Array
Contest: Codeforces Round 879 (Div. 2)
Difficulty rating: 800
Tags: greedy, math

Given an array $$$a$$$ of length $$$n$$$, which elements are equal to $$$-1$$$ and $$$1$$$. Let's call the array $$$a$$$ good if the following conditions are held at the same time:

- $$$a_1 + a_2 + \ldots + a_n \ge 0$$$;
- $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n = 1$$$.

In one operation, you can select an arbitrary element of the array $$$a_i$$$ and change its value to the opposite. In other words, if $$$a_i = -1$$$, you can assign the value to $$$a_i := 1$$$, and if $$$a_i = 1$$$, then assign the value to $$$a_i := -1$$$.

Determine the minimum number of operations you need to perform to make the array $$$a$$$ good. It can be shown that this is always possible.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i = \pm 1$$$) — the elements of the array $$$a$$$.

Output format:
For each test case, output a single integer — the minimum number of operations that need to be done to make the $$$a$$$ array good.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can assign the value $$$a_1 := 1$$$. Then $$$a_1 + a_2 + a_3 + a_4 = 1 + (-1) + 1 + (-1) = 0 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 = 1 \cdot (-1) \cdot 1 \cdot (-1) = 1$$$. Thus, we performed $$$1$$$ operation.

In the second test case, we can assign $$$a_1 := 1$$$. Then $$$a_1 + a_2 + a_3 + a_4 + a_5 = 1 + (-1) + (-1) + 1 + 1 = 1 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 = 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot 1 = 1$$$. Thus, we performed $$$1$$$ operation.

In the third test case, $$$a_1 + a_2 + a_3 + a_4 = (-1) + 1 + (-1) + 1 = 0 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 = (-1) \cdot 1 \cdot (-1) \cdot 1 = 1$$$. Thus, all conditions are already satisfied and no operations are needed.

In the fourth test case, we can assign the values $$$a_1 := 1, a_2 := 1, a_3 := 1$$$. Then $$$a_1 + a_2 + a_3 = 1 + 1 + 1 = 3 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 = 1 \cdot 1 \cdot 1 = 1$$$. Thus, we performed $$$3$$$ operations.

Example input:
7
4
-1 -1 1 -1
5
-1 -1 -1 1 1
4
-1 1 -1 1
3
-1 -1 -1
5
1 1 1 1 1
1
-1
2
-1 -1

Example output:
1
1
0
3
0
1
2

Editorial:
First, let's make the sum of the array elements $$$\ge 0$$$. To do this, we just need to change some $$$-1$$$ to $$$1$$$. The number of such replacements can be calculated using a formula or explicitly simulated.
After that, there are two possible situations: either the product of all elements is equal to $$$1$$$, or the product of all elements is equal to $$$-1$$$. In the first case, we don't need to do anything else. In the second case, we need to replace one more $$$-1$$$ with $$$1$$$ (note that in this case the sum will remain $$$\ge 0$$$).
Stair, Peak, or Neither?
Contest: Codeforces Round 937 (Div. 4)
Difficulty rating: 800
Tags: implementation

You are given three digits $$$a$$$, $$$b$$$, and $$$c$$$. Determine whether they form a stair, a peak, or neither.

- A stair satisfies the condition $$$a<b<c$$$.
- A peak satisfies the condition $$$a<b>c$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The only line of each test case contains three digits $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \leq a$$$, $$$b$$$, $$$c \leq 9$$$).

Output format:
For each test case, output "STAIR" if the digits form a stair, "PEAK" if the digits form a peak, and "NONE" otherwise (output the strings without quotes).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
7
1 2 3
3 2 1
1 5 3
3 4 1
0 0 0
4 1 7
4 5 7

Example output:
STAIR
NONE
PEAK
PEAK
NONE
NONE
STAIR

Editorial:
You just need to write two if-statements and check the two cases. Please note that some languages like C++ won't allow a chain of comparisons like a < b < c, and you should instead write it as a < b && b < c.