1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Beautiful Matrix
Contest: Codeforces Round 161 (Div. 2)
Difficulty rating: 800
Tags: implementation

You've got a 5 × 5 matrix, consisting of 24 zeroes and a single number one. Let's index the matrix rows by numbers from 1 to 5 from top to bottom, let's index the matrix columns by numbers from 1 to 5 from left to right. In one move, you are allowed to apply one of the two following transformations to the matrix:

1. Swap two neighboring matrix rows, that is, rows with indexes i and i + 1 for some integer i (1 ≤ i < 5).
2. Swap two neighboring matrix columns, that is, columns with indexes j and j + 1 for some integer j (1 ≤ j < 5).

You think that a matrix looks beautiful, if the single number one of the matrix is located in its middle (in the cell that is on the intersection of the third row and the third column). Count the minimum number of moves needed to make the matrix beautiful.

Input format:
The input consists of five lines, each line contains five integers: the j-th integer in the i-th line of the input represents the element of the matrix that is located on the intersection of the i-th row and the j-th column. It is guaranteed that the matrix consists of 24 zeroes and a single number one.

Output format:
Print a single integer — the minimum number of moves needed to make the matrix beautiful.

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

Example input:
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Example output:
3

Example input:
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0

Example output:
1

Editorial:
Squares
Contest: Codeforces Round 161 (Div. 2)
Difficulty rating: 900
Tags: greedy, implementation, sortings

Vasya has found a piece of paper with a coordinate system written on it. There are n distinct squares drawn in this coordinate system. Let's number the squares with integers from 1 to n. It turned out that points with coordinates (0, 0) and (ai, ai) are the opposite corners of the i-th square.

Vasya wants to find such integer point (with integer coordinates) of the plane, that belongs to exactly k drawn squares. We'll say that a point belongs to a square, if the point is located either inside the square, or on its boundary.

Help Vasya find a point that would meet the described limits.

Input format:
The first line contains two space-separated integers n, k (1 ≤ n, k ≤ 50). The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

It is guaranteed that all given squares are distinct.

Output format:
In a single line print two space-separated integers x and y (0 ≤ x, y ≤ 109) — the coordinates of the point that belongs to exactly k squares. If there are multiple answers, you are allowed to print any of them.

If there is no answer, print "-1" (without the quotes).

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

Example input:
4 3
5 1 3 4

Example output:
2 1

Example input:
3 1
2 4 1

Example output:
4 0

Editorial:
Circle of Numbers
Contest: Codeforces Round 161 (Div. 2)
Difficulty rating: 2000
Tags: brute force, dfs and similar, implementation

One day Vasya came up to the blackboard and wrote out n distinct integers from 1 to n in some order in a circle. Then he drew arcs to join the pairs of integers (a, b) (a ≠ b), that are either each other's immediate neighbors in the circle, or there is number c, such that a and с are immediate neighbors, and b and c are immediate neighbors. As you can easily deduce, in the end Vasya drew 2·n arcs.

For example, if the numbers are written in the circle in the order 1, 2, 3, 4, 5 (in the clockwise direction), then the arcs will join pairs of integers (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (1, 3), (2, 4), (3, 5), (4, 1) and (5, 2).

Much time has passed ever since, the numbers we wiped off the blackboard long ago, but recently Vasya has found a piece of paper with 2·n written pairs of integers that were joined with the arcs on the board. Vasya asks you to find the order of numbers in the circle by these pairs.

Input format:
The first line of the input contains a single integer n (5 ≤ n ≤ 105) that shows, how many numbers were written on the board. Next 2·n lines contain pairs of integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the numbers that were connected by the arcs.

It is guaranteed that no pair of integers, connected by a arc, occurs in the input more than once. The pairs of numbers and the numbers in the pairs are given in the arbitrary order.

Output format:
If Vasya made a mistake somewhere and there isn't any way to place numbers from 1 to n on the circle according to the statement, then print a single number "-1" (without the quotes). Otherwise, print any suitable sequence of n distinct integers from 1 to n.

If there are multiple solutions, you are allowed to print any of them. Specifically, it doesn't matter which number you write first to describe the sequence of the order. It also doesn't matter whether you write out the numbers in the clockwise or counter-clockwise direction.

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

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

Example output:
1 2 3 4 5

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

Example output:
1 2 4 5 3 6

Editorial:
Cycle in Graph
Contest: Codeforces Round 161 (Div. 2)
Difficulty rating: 1800
Tags: dfs and similar, graphs

You've got a undirected graph G, consisting of n nodes. We will consider the nodes of the graph indexed by integers from 1 to n. We know that each node of graph G is connected by edges with at least k other nodes of this graph. Your task is to find in the given graph a simple cycle of length of at least k + 1.

A simple cycle of length d (d > 1) in graph G is a sequence of distinct graph nodes v1, v2, ..., vd such, that nodes v1 and vd are connected by an edge of the graph, also for any integer i (1 ≤ i < d) nodes vi and vi + 1 are connected by an edge of the graph.

Input format:
The first line contains three integers n, m, k (3 ≤ n, m ≤ 105; 2 ≤ k ≤ n - 1) — the number of the nodes of the graph, the number of the graph's edges and the lower limit on the degree of the graph node. Next m lines contain pairs of integers. The i-th line contains integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the indexes of the graph nodes that are connected by the i-th edge.

It is guaranteed that the given graph doesn't contain any multiple edges or self-loops. It is guaranteed that each node of the graph is connected by the edges with at least k other nodes of the graph.

Output format:
In the first line print integer r (r ≥ k + 1) — the length of the found cycle. In the next line print r distinct integers v1, v2, ..., vr (1 ≤ vi ≤ n) — the found simple cycle.

It is guaranteed that the answer exists. If there are multiple correct answers, you are allowed to print any of them.

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

Example input:
3 3 2
1 2
2 3
3 1

Example output:
3
1 2 3

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

Example output:
4
3 4 1 2

Editorial:
Rhombus
Contest: Codeforces Round 161 (Div. 2)
Difficulty rating: 2500
Tags: brute force, data structures, dp

You've got a table of size n × m. On the intersection of the i-th row (1 ≤ i ≤ n) and the j-th column (1 ≤ j ≤ m) there is a non-negative integer ai, j. Besides, you've got a non-negative integer k.

Your task is to find such pair of integers (a, b) that meets these conditions:

- k ≤ a ≤ n - k + 1;
- k ≤ b ≤ m - k + 1;
- let's denote the maximum of the function $$f(x,y) = \sum_{i=1}^{n} \sum_{j=1}^{m} a_{i,j} \cdot max(0,k-|i-x|-|j-y|)$$ among all integers x and y, that satisfy the inequalities k ≤ x ≤ n - k + 1 and k ≤ y ≤ m - k + 1, as mval; for the required pair of numbers the following equation must hold f(a, b) = mval.

Input format:
The first line contains three space-separated integers n, m and k (1 ≤ n, m ≤ 1000, $$1 \leq k \leq \left\lfloor \frac{\min(n,m)+1}{2} \right\rfloor$$). Next n lines each contains m integers: the j-th number on the i-th line equals ai, j (0 ≤ ai, j ≤ 106).

The numbers in the lines are separated by spaces.

Output format:
Print the required pair of integers a and b. Separate the numbers by a space.

If there are multiple correct answers, you are allowed to print any of them.

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

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

Example output:
3 2

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

Example output:
3 3

Editorial:
Flamingoes of Mystery
Contest: 2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 1400
Tags: interactive

This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

Mr. Chanek wants to buy a flamingo to accompany his chickens on his farm. Before going to the pet shop, Mr. Chanek stops at an animal festival to have fun. It turns out there is a carnival game with a flamingo as the prize.

There are $$$N$$$ mysterious cages, which are numbered from $$$1$$$ to $$$N$$$. Cage $$$i$$$ has $$$A_i$$$ $$$(0 \le A_i \le 10^3)$$$ flamingoes inside $$$(1 \le i \le N)$$$. However, the game master keeps the number of flamingoes inside a secret. To win the flamingo, Mr. Chanek must guess the number of flamingoes in each cage.

Coincidentally, Mr. Chanek has $$$N$$$ coins. Each coin can be used to ask once, what is the total number of flamingoes inside cages numbered $$$L$$$ to $$$R$$$ inclusive? With $$$L < R$$$.

Input format:
Use standard input to read the responses of your questions.

Initially, the judge will give an integer $$$N$$$ $$$(3 \le N \le 10^3)$$$, the number of cages, and the number of coins Mr. Chanek has.

For each of your questions, the jury will give an integer that denotes the number of flamingoes from cage $$$L$$$ to $$$R$$$ inclusive.

If your program does not guess the flamingoes or ask other questions, you will get "Wrong Answer". Of course, if your program asks more questions than the allowed number, your program will get "Wrong Answer".

Output format:
To ask questions, your program must use standard output.

Then, you can ask at most $$$N$$$ questions. Questions are asked in the format "? L R", ($$$1 \le L < R \le N$$$).

To guess the flamingoes, print a line that starts with "!" followed by $$$N$$$ integers where the $$$i$$$-th integer denotes the number of flamingo in cage $$$i$$$. After answering, your program must terminate or will receive the "idle limit exceeded" verdict. You can only guess the flamingoes once.

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

Note:
In the sample input, the correct flamingoes amount is $$$[1, 4, 4, 6, 7, 8]$$$.

Example input:
6
5
15
10

Example output:
? 1 2
? 5 6
? 3 4
! 1 4 4 6 7 8

Editorial:
First get the values of the first three elements using three queries:
1. "? 1 3"
2. "? 1 2"
3. "? 2 3"
Once you get $$$A_i$$$, element $$$A_{i+1}$$$ can be obtained using "? i i+1"
Time complexity: $$$O(N)$$$
United We Stand
Contest: Codeforces Round 892 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, math, number theory

Given an array $$$a$$$ of length $$$n$$$, containing integers. And there are two initially empty arrays $$$b$$$ and $$$c$$$. You need to add each element of array $$$a$$$ to exactly one of the arrays $$$b$$$ or $$$c$$$, in order to satisfy the following conditions:

- Both arrays $$$b$$$ and $$$c$$$ are non-empty. More formally, let $$$l_b$$$ be the length of array $$$b$$$, and $$$l_c$$$ be the length of array $$$c$$$. Then $$$l_b, l_c \ge 1$$$.
- For any two indices $$$i$$$ and $$$j$$$ ($$$1 \le i \le l_b, 1 \le j \le l_c$$$), $$$c_j$$$ is not a divisor of $$$b_i$$$.

Output the arrays $$$b$$$ and $$$c$$$ that can be obtained, or output $$$-1$$$ if they do not exist.

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$$$ ($$$2 \le n \le 100$$$) — the length of array $$$a$$$.

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

Output format:
For each test case, output a single integer $$$-1$$$ if a solution does not exist.

Otherwise, in the first line, output two integers $$$l_b$$$ and $$$l_c$$$ — the lengths of arrays $$$b$$$ and $$$c$$$ respectively.

In the second line, output $$$l_b$$$ integers $$$b_1, b_2, \ldots, b_{l_b}$$$ — the elements of array $$$b$$$.

In the third line, output $$$l_c$$$ integers $$$c_1, c_2, \ldots, c_{l_c}$$$ — the elements of array $$$c$$$.

If there are multiple solutions, output any of them. You can output the elements of the arrays in any order.

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

Note:
In the first test case, a solution does not exist.

In the second test case, we can obtain $$$b = [1, 3, 5]$$$ and $$$c = [2, 4]$$$. Then elements $$$2$$$ and $$$4$$$ do not divide elements $$$1, 3$$$ and $$$5$$$.

In the fifth test case, we can obtain $$$b = [4, 8, 4]$$$ and $$$c = [12, 12]$$$.

Example input:
5
3
2 2 2
5
1 2 3 4 5
3
1 3 5
7
1 7 7 2 9 1 4
5
4 8 12 12 4

Example output:
-1
3 2
1 3 5 
2 4 
1 2
1 
3 5 
2 5
1 1 
2 4 7 7 9 
3 2
4 8 4 
12 12

Editorial:
First, if all numbers are equal, then there is no answer (since $$$a$$$ is divisible by $$$a$$$, if both arrays are non-empty, then $$$c_1$$$ is a divisor of $$$b_1$$$).
Second, if $$$a$$$ is divisible by $$$b$$$ and they are both natural numbers, then the following equality holds: $$$b \le a$$$ (by definition, if $$$a$$$ is divisible by $$$b$$$, then $$$a$$$ can be represented as $$$k \dot b$$$, where $$$k$$$ is a natural number).
Now we can place all instances of the smallest number into $$$b$$$, and all other numbers into $$$c$$$. It can be seen that such a construction always gives a valid answer.
Another Permutation Problem
Contest: Codeforces Round 892 (Div. 2)
Difficulty rating: 1200
Tags: brute force, dp, greedy, math

Andrey is just starting to come up with problems, and it's difficult for him. That's why he came up with a strange problem about permutations$$$^{\dagger}$$$ and asks you to solve it. Can you do it?

Let's call the cost of a permutation $$$p$$$ of length $$$n$$$ the value of the expression:

$$$(\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)$$$.

Find the maximum cost among all permutations of length $$$n$$$.

$$$^{\dagger}$$$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:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 30$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 250$$$) — the length of the permutation.

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 — the maximum cost among all permutations of length $$$n$$$.

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

Note:
In the first test case, the permutation with the maximum cost is $$$[2, 1]$$$. The cost is equal to $$$2 \cdot 1 + 1 \cdot 2 - \max (2 \cdot 1, 1 \cdot 2)= 2 + 2 - 2 = 2$$$.

In the second test case, the permutation with the maximum cost is $$$[1, 2, 4, 3]$$$. The cost is equal to $$$1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4 - 4 \cdot 3 = 17$$$.

Example input:
5
2
4
3
10
20

Example output:
2
17
7
303
2529

Editorial:
Maximum Monogonosity
Contest: Codeforces Round 892 (Div. 2)
Difficulty rating: 2500
Tags: brute force, dp, math

You are given an array $$$a$$$ of length $$$n$$$ and an array $$$b$$$ of length $$$n$$$. The cost of a segment $$$[l, r]$$$, $$$1 \le l \le r \le n$$$, is defined as $$$|b_l - a_r| + |b_r - a_l|$$$.

Recall that two segments $$$[l_1, r_1]$$$, $$$1 \le l_1 \le r_1 \le n$$$, and $$$[l_2, r_2]$$$, $$$1 \le l_2 \le r_2 \le n$$$, are non-intersecting if one of the following conditions is satisfied: $$$r_1 < l_2$$$ or $$$r_2 < l_1$$$.

The length of a segment $$$[l, r]$$$, $$$1 \le l \le r \le n$$$, is defined as $$$r - l + 1$$$.

Find the maximum possible sum of costs of non-intersecting segments $$$[l_j, r_j]$$$, $$$1 \le l_j \le r_j \le n$$$, whose total length is equal to $$$k$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3000$$$) — the length of array $$$a$$$ and the total length of segments.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — the elements of array $$$b$$$.

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

Output format:
For each test case, output a single number — the maximum possible sum of costs of such segments.

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

Note:
In the first test case, the cost of any segment is $$$0$$$, so the total cost is $$$0$$$.

In the second test case, we can take the segment $$$[1, 1]$$$ with a cost of $$$8$$$ and the segment $$$[3, 3]$$$ with a cost of $$$2$$$ to get a total sum of $$$10$$$. It can be shown that this is the optimal solution.

In the third test case, we are only interested in segments of length $$$1$$$, and the cost of any such segment is $$$0$$$.

In the fourth test case, it can be shown that the optimal sum is $$$16$$$. For example, we can take the segments $$$[3, 3]$$$ and $$$[4, 4]$$$.

Example input:
5
4 4
1 1 1 1
1 1 1 1
3 2
1 3 2
5 2 3
5 1
1 2 3 4 5
1 2 3 4 5
7 2
1 3 7 6 4 7 2
1 5 3 2 7 4 5
4 2
17 3 5 8
16 2 5 9

Example output:
0
10
0
16
28

Editorial:
Serval and Mocha's Array
Contest: Codeforces Round 853 (Div. 2)
Difficulty rating: 800
Tags: brute force, math, number theory

Mocha likes arrays, and Serval gave her an array consisting of positive integers as a gift.

Mocha thinks that for an array of positive integers $$$a$$$, it is good iff the greatest common divisor of all the elements in $$$a$$$ is no more than its length. And for an array of at least $$$2$$$ positive integers, it is beautiful iff all of its prefixes whose length is no less than $$$2$$$ are good.

For example:

- $$$[3,6]$$$ is not good, because $$$\gcd(3,6)=3$$$ is greater than its length $$$2$$$.
- $$$[1,2,4]$$$ is both good and beautiful, because all of its prefixes whose length is no less than $$$2$$$, which are $$$[1,2]$$$ and $$$[1,2,4]$$$, are both good.
- $$$[3,6,1]$$$ is good but not beautiful, because $$$[3,6]$$$ is not good.

Now Mocha gives you the gift array $$$a$$$ of $$$n$$$ positive integers, and she wants to know whether array $$$a$$$ could become beautiful by reordering the elements in $$$a$$$. It is allowed to keep the array $$$a$$$ unchanged.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_1,a_2,\ldots,a_n\leq 10^6$$$) — the elements of array $$$a$$$.

Output format:
For each test case, print Yes if it is possible to reorder the elements in $$$a$$$ to make it beautiful, and print No if not.

You can output Yes and No in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

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

Note:
In the first test case, neither $$$[3,6]$$$ nor $$$[6,3]$$$ are beautiful, so it's impossible to obtain a beautiful array by reordering the elements in $$$a$$$.

In the second test case, $$$[1,2,4]$$$ is already beautiful. Keeping the array $$$a$$$ unchanged can obtain a beautiful array.

Example input:
6
2
3 6
3
1 2 4
3
3 6 1
3
15 35 21
4
35 10 35 14
5
1261 227821 143 4171 1941

Example output:
No
Yes
Yes
No
Yes
Yes

Editorial:
Serval and Inversion Magic
Contest: Codeforces Round 853 (Div. 2)
Difficulty rating: 800
Tags: brute force, implementation, strings, two pointers

Serval has a string $$$s$$$ that only consists of 0 and 1 of length $$$n$$$. The $$$i$$$-th character of $$$s$$$ is denoted as $$$s_i$$$, where $$$1\leq i\leq n$$$.

Serval can perform the following operation called Inversion Magic on the string $$$s$$$:

- Choose an segment $$$[l, r]$$$ ($$$1\leq l\leq r\leq n$$$). For $$$l\leq i\leq r$$$, change $$$s_i$$$ into 1 if $$$s_i$$$ is 0, and change $$$s_i$$$ into 0 if $$$s_i$$$ is 1.

For example, let $$$s$$$ be 010100 and the segment $$$[2,5]$$$ is chosen. The string $$$s$$$ will be 001010 after performing the Inversion Magic.

Serval wants to make $$$s$$$ a palindrome after performing Inversion Magic exactly once. Help him to determine whether it is possible.

A string is a palindrome iff it reads the same backwards as forwards. For example, 010010 is a palindrome but 10111 is not.

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

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

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$. Only characters 0 and 1 can appear in $$$s$$$.

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

Output format:
For each test case, print Yes if $$$s$$$ can be a palindrome after performing Inversion Magic exactly once, and print No if not.

You can output Yes and No in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

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

Note:
In the first test case, Serval can perform Inversion Magic on the segment $$$[1,4]$$$. The string $$$s$$$ will be 0110 after the magic.

In the second test case, Serval can perform Inversion Magic on the segment $$$[1,3]$$$. The string $$$s$$$ will be 01110 after the magic.

In the third test case, Serval can't make $$$s$$$ a palindrome by performing Inversion Magic exactly once.

Example input:
3
4
1001
5
10010
7
0111011

Example output:
Yes
Yes
No

Editorial: