1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Bugged Sort
Contest: Codeforces Round 998 (Div. 3)
Difficulty rating: 2400
Tags: dp, greedy, sortings

Today, Alice has given Bob arrays for him to sort in increasing order again! At this point, no one really knows how many times she has done this.

Bob is given two sequences $$$a$$$ and $$$b$$$, both of length $$$n$$$. All integers in the range from $$$1$$$ to $$$2n$$$ appear exactly once in either $$$a$$$ or $$$b$$$. In other words, the concatenated$$$^{\text{∗}}$$$ sequence $$$a+b$$$ is a permutation$$$^{\text{†}}$$$ of length $$$2n$$$.

Bob must sort both sequences in increasing order at the same time using Alice's swap function. Alice's swap function is implemented as follows:

- Given two indices $$$i$$$ and $$$j$$$ ($$$i \neq j$$$), it swaps $$$a_i$$$ with $$$b_j$$$, and swaps $$$b_i$$$ with $$$a_j$$$.

Given sequences $$$a$$$ and $$$b$$$, please determine if both sequences can be sorted in increasing order simultaneously after using Alice's swap function any number of times.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

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

The second line of each test case contains $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 2n$$$).

The third line of each test case contains $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \le b_i \le 2n$$$).

It is guaranteed that all integers in the range $$$[1,2n]$$$ appear exactly once in either $$$a$$$ or $$$b$$$.

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

Output format:
If it is possible to sort both sequences simultaneously, print "YES" on a new line. Otherwise, print "NO" on a new line.

You can output the answer in any case. For example, the strings "yEs", "yes", and "Yes" will also be recognized as positive responses.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Note:
In the first test case, it can be shown that it is impossible.

In the second test case, Bob can perform one operation with indices $$$i=1$$$ and $$$j=2$$$. The arrays become $$$[3,4,5]$$$ and $$$[1,2,6]$$$ respectively. Both arrays are now sorted.

Example input:
5
3
2 1 3
4 6 5
3
2 1 5
4 3 6
4
1 6 4 3
5 2 8 7
4
5 3 7 1
8 6 4 2
7
5 1 9 12 3 13 7
2 4 11 14 6 10 8

Example output:
NO
YES
NO
YES
YES

Editorial:
Preparing for the Olympiad
Contest: Codeforces Round 995 (Div. 3)
Difficulty rating: 800
Tags: greedy

Monocarp and Stereocarp are preparing for the Olympiad. There are $$$n$$$ days left until the Olympiad. On the $$$i$$$-th day, if Monocarp plans to practice, he will solve $$$a_i$$$ problems. Similarly, if Stereocarp plans to practice on the same day, he will solve $$$b_i$$$ problems.

Monocarp can train on any day he wants. However, Stereocarp watches Monocarp and follows a different schedule: if Monocarp trained on day $$$i$$$ and $$$i < n$$$, then Stereocarp will train on day $$$(i+1)$$$.

Monocarp wants to organize his training process in a way that the difference between the number of problems he solves and the number of problems Stereocarp solves is as large as possible. Formally, Monocarp wants to maximize the value of $$$(m-s)$$$, where $$$m$$$ is the number of problems he solves, and $$$s$$$ is the number of problems Stereocarp solves. Help Monocarp determine the maximum possible difference in the number of solved problems between them.

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 100$$$).

Output format:
For each test case, print a single integer — the maximum possible difference between the number of problems Monocarp solves and the number of problems Stereocarp solves.

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

Note:
Let's analyze the example from the statement:

- In the first test case, it is optimal for Monocarp to train both days; then Stereocarp will train on day $$$2$$$.
- In the second test case, it is optimal for Monocarp to train on the only day, and Stereocarp will not train at all.
- In the third test case, it is optimal for Monocarp to train on the last day (and only on that day).
- In the fourth test case, it is optimal for Monocarp to train on days $$$1, 3, 4, 6$$$; then Stereocarp will train on days $$$2, 4, 5$$$.

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

Example output:
4
5
1
16

Editorial:
Let's consider what contribution each day that Monokarp trains makes to the difference. For each day, except the last one, if Monokarp trains on that day, then the number of problems he has solved will increase by $$$a_i$$$, and the number of problems solved by Stereokarp will increase by $$$b_{i+1}$$$. Therefore, if $$$a_i - b_{i+1} > 0$$$, it is beneficial for Monokarp to train on the $$$i$$$-th day; otherwise, it is not beneficial.
On the last day, it is always beneficial to train, as Stereokarp will not solve anything on the day following it.
Journey
Contest: Codeforces Round 995 (Div. 3)
Difficulty rating: 800
Tags: binary search, math

Monocarp decided to embark on a long hiking journey.

He decided that on the first day he would walk $$$a$$$ kilometers, on the second day he would walk $$$b$$$ kilometers, on the third day he would walk $$$c$$$ kilometers, on the fourth day, just like on the first, he would walk $$$a$$$ kilometers, on the fifth day, just like on the second, he would walk $$$b$$$ kilometers, on the sixth day, just like on the third, he would walk $$$c$$$ kilometers, and so on.

Monocarp will complete his journey on the day when he has walked at least $$$n$$$ kilometers in total. Your task is to determine the day on which Monocarp will complete his journey.

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

Each test case consists of one line containing four integers $$$n$$$, $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le a, b, c \le 10^6$$$).

Output format:
For each test case, output one integer — the day on which Monocarp will have walked at least $$$n$$$ kilometers in total and will complete his journey.

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

Note:
In the first example, over the first four days, Monocarp will cover $$$1 + 5 + 3 + 1 = 10$$$ kilometers. On the fifth day, he will cover another $$$5$$$ kilometers, meaning that in total over five days he will have covered $$$10 + 5 = 15$$$ kilometers. Since $$$n = 12$$$, Monocarp will complete his journey on the fifth day.

In the second example, Monocarp will cover $$$6$$$ kilometers on the first day. Since $$$n = 6$$$, Monocarp will complete his journey on the very first day.

In the third example, Monocarp will cover $$$3 + 4 + 1 + 3 + 4 + 1 = 16$$$ kilometers over the first six days. Since $$$n = 16$$$, Monocarp will complete his journey on the sixth day.

Example input:
4
12 1 5 3
6 6 7 4
16 3 4 1
1000000000 1 1 1

Example output:
5
1
6
1000000000

Editorial:
Processing every day separately is too slow. Instead, we will use the fact that every three days, the number of kilometers Monocarp walks repeats, and process days in "triples".
During every three days, Monocarp walks exactly $$$(a+b+c)$$$ kilometers, so we can do the following: while $$$n \ge a + b + c$$$, subtract $$$(a+b+c)$$$ from $$$n$$$ and increase the answer by $$$3$$$; and finally, process the remaining days, since there will be at most $$$3$$$ of them.
However, this works in $$$O(n)$$$ per test case, so it is still too slow. We need to improve the part when we subtract $$$a+b+c$$$ from $$$n$$$ until $$$n$$$ becomes less than this sum. Does this sound familiar?
The number of times we need to subtract $$$(a+b+c)$$$ from $$$n$$$ is exactly $$$\lfloor \frac{n}{a+b+c} \rfloor$$$, and the number we get after that is $$$n \bmod (a+b+c)$$$ by definition of integer division and remainder. This allows us to process all "triples" in $$$O(1)$$$, instead of running a loop in $$$O(n)$$$.
The solution we get works in $$$O(1)$$$ per test case.
Sakurako and Kosuke
Contest: Codeforces Round 981 (Div. 3)
Difficulty rating: 800
Tags: constructive algorithms, implementation, math

Sakurako and Kosuke decided to play some games with a dot on a coordinate line. The dot is currently located in position $$$x=0$$$. They will be taking turns, and Sakurako will be the one to start.

On the $$$i$$$-th move, the current player will move the dot in some direction by $$$2\cdot i-1$$$ units. Sakurako will always be moving the dot in the negative direction, whereas Kosuke will always move it in the positive direction.

In other words, the following will happen:

1. Sakurako will change the position of the dot by $$$-1$$$, $$$x = -1$$$ now
2. Kosuke will change the position of the dot by $$$3$$$, $$$x = 2$$$ now
3. Sakurako will change the position of the dot by $$$-5$$$, $$$x = -3$$$ now
4. $$$\cdots$$$

They will keep on playing while the absolute value of the coordinate of the dot does not exceed $$$n$$$. More formally, the game continues while $$$-n\le x\le n$$$. It can be proven that the game will always end.

Your task is to determine who will be the one who makes the last turn.

Input format:
The first line contains one integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of games that Sakurako and Kosuke played.

Each game is described by one number $$$n$$$ ($$$1 \le n\le 100$$$) — the number that defines the condition when the game ends.

Output format:
For each of the $$$t$$$ games, output a line with the result of that game. If Sakurako makes the last turn, output "Sakurako" (without quotes); else output "Kosuke".

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

Example input:
4
1
6
3
98

Example output:
Kosuke
Sakurako
Kosuke
Sakurako

Editorial:
For this task we could just brute-force the answer by repeatedly adding or substracting the odd numbers from the initial position $$$0$$$. This would result in $$$O(n)$$$ time complexity. This is sufficient enough.
Sakurako and Water
Contest: Codeforces Round 981 (Div. 3)
Difficulty rating: 900
Tags: brute force, constructive algorithms, greedy

During her journey with Kosuke, Sakurako and Kosuke found a valley that can be represented as a matrix of size $$$n \times n$$$, where at the intersection of the $$$i$$$-th row and the $$$j$$$-th column is a mountain with a height of $$$a_{i,j}$$$. If $$$a_{i,j} < 0$$$, then there is a lake there.

Kosuke is very afraid of water, so Sakurako needs to help him:

- With her magic, she can select a square area of mountains and increase the height of each mountain on the main diagonal of that area by exactly one.

More formally, she can choose a submatrix with the upper left corner located at $$$(i, j)$$$ and the lower right corner at $$$(p, q)$$$, such that $$$p-i=q-j$$$. She can then add one to each element at the intersection of the $$$(i + k)$$$-th row and the $$$(j + k)$$$-th column, for all $$$k$$$ such that $$$0 \le k \le p-i$$$.

Determine the minimum number of times Sakurako must use her magic so that there are no lakes.

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

Each test case is described as follows:

- The first line of each test case consists of a single number $$$n$$$ ($$$1 \le n \le 500$$$).
- Each of the following $$$n$$$ lines consists of $$$n$$$ integers separated by spaces, which correspond to the heights of the mountains in the valley $$$a$$$ ($$$-10^5 \le a_{i,j} \le 10^5$$$).

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

Output format:
For each test case, output the minimum number of times Sakurako will have to use her magic so that all lakes disappear.

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

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

Example output:
0
1
4
19

Editorial:
In this task we were supposed to find the minimal possible amount of moves that Sakurako needs to make in order to make all elements in the matrix non-negative.
The key observation is to notice that Sakurako can only add simultaneously to elements that lay on one diagonal.
For cell $$$(i,j)$$$, let the "index" of diagonal which it is placed on is equal to $$$d(i,j)=(i-j)$$$.
This is proven by the fact that for $$$(i,j)$$$ and $$$(i+1,j+1)$$$ the equation $$$d(i,j)=d(i+1,j+1)$$$ holds.
We are able to add to a pair of elements $$$(x,y)$$$ and $$$(x_1,y_1)$$$ simultaneously if and only if $$$d(x,y)=d(x_1,y_1)$$$.
From this we can reduce our problem to finding the amount of times that we need to add 1 to this diagonal in order for all of its elements to become non-negative.
For each diagonal we find the minimal element in it and there will be two cases:
1. The minimal element is non-negative: we don't need to add anything to that diagonal.
2. The minimal element is negative and equal to $$$x$$$: we will need to add one at least $$$-x$$$ times (remember that $$$x$$$ is negative).
After that, the answer for our task is the sum of answers for each individual diagonal.
Total time complexity $$$O(n^2)$$$
Sakurako, Kosuke, and the Permutation
Contest: Codeforces Round 981 (Div. 3)
Difficulty rating: 1400
Tags: brute force, data structures, dfs and similar, dsu, graphs, greedy, math

Sakurako's exams are over, and she did excellently. As a reward, she received a permutation $$$p$$$. Kosuke was not entirely satisfied because he failed one exam and did not receive a gift. He decided to sneak into her room (thanks to the code for her lock) and spoil the permutation so that it becomes simple.

A permutation $$$p$$$ is considered simple if for every $$$i$$$ $$$(1\le i \le n)$$$ one of the following conditions holds:

- $$$p_i=i$$$
- $$$p_{p_i}=i$$$

For example, the permutations $$$[1, 2, 3, 4]$$$, $$$[5, 2, 4, 3, 1]$$$, and $$$[2, 1]$$$ are simple, while $$$[2, 3, 1]$$$ and $$$[5, 2, 1, 4, 3]$$$ are not.

In one operation, Kosuke can choose indices $$$i,j$$$ $$$(1\le i,j\le n)$$$ and swap the elements $$$p_i$$$ and $$$p_j$$$.

Sakurako is about to return home. Your task is to calculate the minimum number of operations that Kosuke needs to perform to make the permutation simple.

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

Each test case is described by two lines.

- The first line contains one integer $$$n$$$ ($$$1\le n \le 10^6$$$) — the length of the permutation $$$p$$$.
- The second line contains $$$n$$$ integers $$$p_i$$$ ($$$1\le p_i\le n$$$) — the elements of the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^6$$$.

It is guaranteed that $$$p$$$ is a permutation.

Output format:
For each test case, output the minimum number of operations that Kosuke needs to perform to make the permutation simple.

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

Note:
In the first and second examples, the permutations are already simple.

In the fourth example, it is sufficient to swap $$$p_2$$$ and $$$p_4$$$. Thus, the permutation will become $$$[2, 1, 4, 3]$$$ in $$$1$$$ operation.

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

Example output:
0
0
2
1
0
2

Editorial:
Lets make this the shortest editorial out of all.
Observation $$$1$$$:
All permutations can be split into cycles. All cycles of permutation can be traversed in $$$O(n)$$$ time.
Observation $$$2$$$:
When we are swapping $$$2$$$ elements that belong to one cycle, we are splitting our cycle into $$$2$$$ parts.
If we rephrase our definition of simple permutation, we can see that the permutation is called simple if every cycle in it has length not larger than $$$2$$$.
Observation $$$3$$$:
By splitting our initial cycle of length $$$x$$$ repeatedly, we can achieve its division into cycles of length not larger than $$$2$$$ in $$$\lfloor\frac{x-1}{2}\rfloor$$$ swaps. (this is achieved by repeatedly decreasing size of the cycle by $$$2$$$)
Observation $$$4$$$:
All cycles are independent, so the answer for the initial task is the sum of answers for every cycle.
Total time complexity is $$$O(n)$$$.
Kosuke's Sloth
Contest: Codeforces Round 981 (Div. 3)
Difficulty rating: 1800
Tags: brute force, math, number theory

Kosuke is too lazy. He will not give you any legend, just the task:

Fibonacci numbers are defined as follows:

- $$$f(1)=f(2)=1$$$.
- $$$f(n)=f(n-1)+f(n-2)$$$ $$$(3\le n)$$$

As this number can be too big, output it by modulo $$$10^9+7$$$.

For example: $$$G(3,2)=9$$$ because the $$$3$$$-rd Fibonacci number that is divisible by $$$2$$$ is $$$34$$$. $$$[1,1,\textbf{2},3,5,\textbf{8},13,21,\textbf{34}]$$$.

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

The first and only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le k \le 10^5$$$).

It is guaranteed that the sum of $$$k$$$ across all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output the only number: the value $$$G(n,k)$$$ taken by modulo $$$10^9+7$$$.

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

Example input:
3
3 2
100 1
1000000000000 1377

Example output:
9
100
999244007

Editorial:
This was one of my favourite tasks untill I realised that the amount of numbers in Fibonacci cycle is either $$$1$$$, $$$2$$$ or $$$4$$$...
First of all, the length of cycle after which our sequence would be repeating for modulo $$$k$$$ is at most $$$6k$$$ (We will just take this as a fact for now, it is too long to explain but you can read it here.
Now, if we know that the amount of operations needed to take untill we are in a cycle is at most $$$6k$$$, we can brute-force our solution in $$$O(k)$$$ time.
Also, one last thing that we will need to consider is the fact that
if $$$F_i$$$ is divisible by $$$k$$$, then for every $$$j$$$, $$$F_{i\cdot j}$$$ is also divisible by $$$k$$$.
Proof:
as we know, $$$gcd(F_n,F_m)=F_{gcd(n,m)}$$$ so if we take any multiple of $$$i$$$ as $$$n$$$ and $$$i=m$$$, then the $$$gcd(F_{n},F_{m})$$$ would be equal to $$$F_{i}$$$.
And because $$$F_{i}$$$ is divisible by $$$k$$$, every other multiple of $$$i$$$ is going to be also divisible by $$$k$$$.
So, our final solution would be brute-forcing first $$$6k$$$ Fibonacci numbers and their remainder after division by $$$k$$$ in order to find the first one that is divisible by $$$k$$$. Then just multiply that number by $$$n$$$ and we will get the answer for our task. Also, don't forget to take everything via modulo $$$10^9+7$$$. (Someone kept whining about it in comments)
Total time complexity $$$O(k)$$$.
MEX Destruction
Contest: Codeforces Round 994 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation

Evirir the dragon snuck into a wizard's castle and found a mysterious contraption, and their playful instincts caused them to play with (destroy) it...

Evirir the dragon found an array $$$a_1, a_2, \ldots, a_n$$$ of $$$n$$$ non-negative integers.

In one operation, they can choose a non-empty subarray$$$^{\text{∗}}$$$ $$$b$$$ of $$$a$$$ and replace it with the integer $$$\operatorname{mex}(b)$$$$$$^{\text{†}}$$$. They want to use this operation any number of times to make $$$a$$$ only contain zeros. It can be proven that this is always possible under the problem constraints.

What is the minimum number of operations needed?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.

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

The second line of each test case contains $$$n$$$ space-separated integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 100$$$).

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

Output format:
For each test case, output a single integer on a line, the minimum number of operations needed to make $$$a$$$ contain only zeros.

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

Note:
In the first test case, Evirir can choose the subarray $$$b = [1, 2, 3]$$$ and replace it with $$$\operatorname{mex}(1, 2, 3) = 0$$$, changing $$$a$$$ from $$$[0, \underline{1, 2, 3}]$$$ to $$$[0, 0]$$$ (where the chosen subarray is underlined). Therefore, the answer is $$$1$$$.

In the second test case, $$$a$$$ already contains only $$$0$$$s, so no operation is needed.

In the third test case, Evirir can change $$$a$$$ as follows: $$$[1, \underline{0, 1, 0, 1}] \to [\underline{1, 2}] \to [0]$$$. Here, $$$\operatorname{mex}(0, 1, 0, 1) = 2$$$ and $$$\operatorname{mex}(1, 2) = 0$$$.

In the fourth test case, Evirir can choose $$$b$$$ to be the entire array $$$a$$$, changing $$$a$$$ from $$$[\underline{3, 1, 4, 1, 5}]$$$ to $$$[0]$$$.

Example input:
10
4
0 1 2 3
6
0 0 0 0 0 0
5
1 0 1 0 1
5
3 1 4 1 5
4
3 2 1 0
7
9 100 0 89 12 2 3
4
0 3 9 0
7
0 7 0 2 0 7 0
1
0
2
0 1

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

Editorial:
pspspsps
Contest: Codeforces Round 994 (Div. 2)
Difficulty rating: 1300
Tags: brute force, constructive algorithms, graph matchings, implementation

Cats are attracted to pspspsps, but Evirir, being a dignified dragon, is only attracted to pspspsps with oddly specific requirements...

Given a string $$$s = s_1s_2\ldots s_n$$$ of length $$$n$$$ consisting of characters p, s, and . (dot), determine whether a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$ exists, such that for all integers $$$i$$$ ($$$1 \le i \le n$$$):

- If $$$s_i$$$ is p, then $$$[p_1, p_2, \ldots, p_i]$$$ forms a permutation (of length $$$i$$$);
- If $$$s_i$$$ is s, then $$$[p_i, p_{i+1}, \ldots, p_{n}]$$$ forms a permutation (of length $$$n-i+1$$$);
- If $$$s_i$$$ is ., then there is no additional restriction.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 500$$$), the length of $$$s$$$.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ that consists of the characters p, s, and ..

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

Output format:
For each test case, output YES or NO on a line. Output YES if there is such a permutation and NO otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

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

Note:
For the first test case, one permutation that works is $$$p = [3, 4, 1, 2]$$$. The restrictions are as follows:

- $$$s_1 =$$$ s: $$$[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$$$ forms a permutation.
- $$$s_2 =$$$ .: No additional restriction.
- $$$s_3 =$$$ s: $$$[p_3, p_4] = [1, 2]$$$ forms a permutation.
- $$$s_4 =$$$ p: $$$[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$$$ forms a permutation.

For the second test case, it can be proven that there is no permutation that satisfies all restrictions.

For the third test case, one permutation that satisfies the constraints is $$$p = [1, 2, 3, 4, 5]$$$.

Example input:
9
4
s.sp
6
pss..s
5
ppppp
2
sp
4
.sp.
8
psss....
1
.
8
pspspsps
20
....................

Example output:
YES
NO
YES
YES
NO
NO
YES
NO
YES

Editorial: