1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Mr. Bender and Square
Contest: Codeforces Round 156 (Div. 2)
Difficulty rating: 1800
Tags: binary search, implementation, math

Mr. Bender has a digital table of size n × n, each cell can be switched on or off. He wants the field to have at least c switched on squares. When this condition is fulfilled, Mr Bender will be happy.

We'll consider the table rows numbered from top to bottom from 1 to n, and the columns — numbered from left to right from 1 to n. Initially there is exactly one switched on cell with coordinates (x, y) (x is the row number, y is the column number), and all other cells are switched off. Then each second we switch on the cells that are off but have the side-adjacent cells that are on.

For a cell with coordinates (x, y) the side-adjacent cells are cells with coordinates (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1).

In how many seconds will Mr. Bender get happy?

Input format:
The first line contains four space-separated integers n, x, y, c (1 ≤ n, c ≤ 109; 1 ≤ x, y ≤ n; c ≤ n2).

Output format:
In a single line print a single integer — the answer to the problem.

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

Note:
Initially the first test has one painted cell, so the answer is 0. In the second test all events will go as is shown on the figure. .

Example input:
6 4 3 1

Example output:
0

Example input:
9 3 8 10

Example output:
2

Editorial:
Furlo and Rublo and Game
Contest: Codeforces Round 156 (Div. 2)
Difficulty rating: 2200
Tags: games, implementation, math

Furlo and Rublo play a game. The table has n piles of coins lying on it, the i-th pile has ai coins. Furlo and Rublo move in turns, Furlo moves first. In one move you are allowed to:

- choose some pile, let's denote the current number of coins in it as x;
- choose some integer y (0 ≤ y < x; x1 / 4 ≤ y ≤ x1 / 2) and decrease the number of coins in this pile to y. In other words, after the described move the pile will have y coins left.

The player who can't make a move, loses.

Your task is to find out, who wins in the given game if both Furlo and Rublo play optimally well.

Input format:
The first line contains integer n (1 ≤ n ≤ 77777) — the number of piles. The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 777777777777) — the sizes of piles. The numbers are separated by single spaces.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output format:
If both players play optimally well and Furlo wins, print "Furlo", otherwise print "Rublo". Print the answers without the quotes.

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

Example input:
1
1

Example output:
Rublo

Example input:
2
1 2

Example output:
Rublo

Editorial:
Row GCD
Contest: Codeforces Round 691 (Div. 1)
Difficulty rating: 1600
Tags: math, number theory

You are given two positive integer sequences $$$a_1, \ldots, a_n$$$ and $$$b_1, \ldots, b_m$$$. For each $$$j = 1, \ldots, m$$$ find the greatest common divisor of $$$a_1 + b_j, \ldots, a_n + b_j$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{18})$$$.

The third line contains $$$m$$$ integers $$$b_1, \ldots, b_m$$$ ($$$1 \leq b_j \leq 10^{18})$$$.

Output format:
Print $$$m$$$ integers. The $$$j$$$-th of them should be equal to GCD$$$(a_1 + b_j, \ldots, a_n + b_j)$$$.

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

Example input:
4 4
1 25 121 169
1 2 7 23

Example output:
2 3 8 24

Editorial:
From basic properties of GCD we know that $$$GCD(x, y) = GCD(x - y, y)$$$. The same applies for multiple arguments: $$$GCD(x, y, z, \ldots) = GCD(x - y, y, z, \ldots)$$$. Let's use this for $$$GCD(a_1 + b_j, \ldots, a_n + b_j)$$$ and subtract $$$a_1 + b_j$$$ from all other arguments: $$$GCD(a_1 + b_j, \ldots, a_n + b_j) = GCD(a_1 + b_j, a_2 - a_1, \ldots, a_n - a_1)$$$.
If we find $$$G = GCD(a_2 - a_1, \ldots, a_n - a_1)$$$, then any answer can be found as $$$GCD(a_1 + b_j, G)$$$. Note that we have to assume that GCD of an empty set is $$$0$$$, and $$$GCD(x, 0) = x$$$ for any $$$x$$$, since $$$0$$$ is the only number divisible by any other number.
LuoTianyi and the Function
Contest: Codeforces Round 872 (Div. 1)
Difficulty rating: 3000
Tags: data structures

LuoTianyi gives you an array $$$a$$$ of $$$n$$$ integers and the index begins from $$$1$$$.

Define $$$g(i,j)$$$ as follows:

- $$$g(i,j)$$$ is the largest integer $$$x$$$ that satisfies $$$\{a_p:i\le p\le j\}\subseteq\{a_q:x\le q\le j\}$$$ while $$$i \le j$$$;
- and $$$g(i,j)=0$$$ while $$$i>j$$$.

There are $$$q$$$ queries. For each query you are given four integers $$$l,r,x,y$$$, you need to calculate $$$\sum\limits_{i=l}^{r}\sum\limits_{j=x}^{y}g(i,j)$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n,q\le 10^6$$$) — the length of the array $$$a$$$ and the number of queries.

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

Next $$$q$$$ lines describe a query. The $$$i$$$-th line contains four integers $$$l,r,x,y$$$ ($$$1\le l\le r\le n, 1\le x\le y\le n$$$) — the integers in the $$$i$$$-th query.

Output format:
Print $$$q$$$ lines where $$$i$$$-th line contains one integer — the answer for the $$$i$$$-th query.

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

Note:
In the first example:

In the first query, the answer is $$$g(1,4)+g(1,5)=3+3=6$$$.

$$$x=1,2,3$$$ can satisfies $$$\{a_p:1\le p\le 4\}\subseteq\{a_q:x\le q\le 4\}$$$, $$$3$$$ is the largest integer so $$$g(1,4)=3$$$.

In the second query, the answer is $$$g(2,3)+g(3,3)=3+3=6$$$.

In the third query, the answer is $$$0$$$, because all $$$i > j$$$ and $$$g(i,j)=0$$$.

In the fourth query, the answer is $$$g(6,6)=6$$$.

In the second example:

In the second query, the answer is $$$g(2,3)=2$$$.

In the fourth query, the answer is $$$g(1,4)+g(1,5)=2+2=4$$$.

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

Example output:
6
6
0
6

Example input:
10 5
10 2 8 10 9 8 2 1 1 8
1 1 10 10
2 2 3 3
6 6 6 6
1 1 4 5
4 8 4 8

Example output:
4
2
6
4
80

Editorial:
We can enumerate the left endpoint $$$i$$$ from $$$n$$$ to $$$1$$$ and maintain all the $$$g(i,j)$$$ with right endpoint $$$j$$$s.
We can find that add $$$a_i$$$ will make $$$g(i,x)\ (i \le x<nxt_i)$$$ become $$$i$$$, and it is the same as modify the matrix $$$[(1,i),(i,nxt_i-1)]$$$ to $$$i$$$.
Then the problem is changed to $$$n$$$ times of marix assignment, and then $$$m$$$ times of matrix sum.
Consider the matrix assignment into several matrix additions, and distribute evenly according to color, we can prove that there are $$$O(n)$$$ matrix add and $$$O(m)$$$ matrix query in all. As the queries are after adds, so we can offline and use fenwick-tree to solve it. The total time is $$$O(n \log n)$$$.
LuoTianyi and Cartridge
Contest: Codeforces Round 872 (Div. 1)
Difficulty rating: 3500
Tags: data structures, trees

LuoTianyi is watching the anime Made in Abyss. She finds that making a Cartridge is interesting. To describe the process of making a Cartridge more clearly, she abstracts the original problem and gives you the following problem.

You are given a tree $$$T$$$ consisting of $$$n$$$ vertices. Each vertex has values $$$a_i$$$ and $$$b_i$$$ and each edge has values $$$c_j$$$ and $$$d_j$$$.

Now you are aim to build a tree $$$T'$$$ as follows:

- First, select $$$p$$$ vertices from $$$T$$$ ($$$p$$$ is a number chosen by yourself) as the vertex set $$$S'$$$ of $$$T'$$$.
- Next, select $$$p-1$$$ edges from $$$T$$$ one by one (you cannot select one edge more than once).
- May you have chosen the $$$j$$$-th edge connects vertices $$$x_j$$$ and $$$y_j$$$ with values $$$(c_j,d_j)$$$, then you can choose two vertices $$$u$$$ and $$$v$$$ in $$$S'$$$ that satisfy the edge $$$(x_j,y_j)$$$ is contained in the simple path from $$$u$$$ to $$$v$$$ in $$$T$$$, and link $$$u$$$ and $$$v$$$ in $$$T'$$$ by the edge with values $$$(c_j,d_j)$$$ ($$$u$$$ and $$$v$$$ shouldn't be contained in one connected component before in $$$T'$$$).

A tree with three vertices, $$$\min(A,C)=1,B+D=7$$$, the cost is $$$7$$$.

Selected vertices $$$2$$$ and $$$3$$$ as $$$S'$$$, used the edge $$$(1,2)$$$ with $$$c_j = 2$$$ and $$$d_j = 1$$$ to link this vertices, now $$$\min(A,C)=2,B+D=4$$$, the cost is $$$8$$$.

Let $$$A$$$ be the minimum of values $$$a_i$$$ in $$$T'$$$ and $$$C$$$ be the minimum of values $$$c_i$$$ in $$$T'$$$. Let $$$B$$$ be the sum of $$$b_i$$$ in $$$T'$$$ and $$$D$$$ be the sum of values $$$d_i$$$ in $$$T'$$$. Let $$$\min(A, C) \cdot (B + D)$$$ be the cost of $$$T'$$$. You need to find the maximum possible cost of $$$T'$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$3\le n \le 2\cdot 10^5$$$) — the number of vertices in the tree $$$T$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 2\cdot 10^5$$$), where the $$$i$$$-th integer represents the $$$a_i$$$ value of the $$$i$$$-th vertex.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1\le b_i\le 2\cdot 10^5$$$), where the $$$i$$$-th integer represents the $$$b_i$$$ value of the $$$i$$$-th vertex.

Then $$$n-1$$$ lines follow, the $$$j$$$-th of them contains four integers $$$x_j,y_j,c_j,d_j$$$ ($$$1\le x_j,y_j\le n,1\le c_j,d_j\le 2\cdot 10^5$$$) representing the edge $$$(x_j,y_j)$$$ and its values $$$c_j$$$ and $$$d_j$$$ respectively. It's guaranteed that edges form a tree.

Output format:
Print a single integer — the maximum possible cost of $$$T'$$$.

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

Note:
The tree from the first example is shown in the statement.

The tree from the second example is shown below:

$$$A = 1, B = 18, C = 1, D = 17$$$, so the cost is $$$\min(1,1) \cdot (18 + 17) = 35$$$.

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

Example output:
8

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

Example output:
35

Editorial:
Print a Pedestal (Codeforces logo?)
Contest: Codeforces Round 797 (Div. 3)
Difficulty rating: 800
Tags: constructive algorithms, greedy

Given the integer $$$n$$$ — the number of available blocks. You must use all blocks to build a pedestal.

The pedestal consists of $$$3$$$ platforms for $$$2$$$-nd, $$$1$$$-st and $$$3$$$-rd places respectively. The platform for the $$$1$$$-st place must be strictly higher than for the $$$2$$$-nd place, and the platform for the $$$2$$$-nd place must be strictly higher than for the $$$3$$$-rd place. Also, the height of each platform must be greater than zero (that is, each platform must contain at least one block).

Example pedestal of $$$n=11$$$ blocks: second place height equals $$$4$$$ blocks, first place height equals $$$5$$$ blocks, third place height equals $$$2$$$ blocks.

Among all possible pedestals of $$$n$$$ blocks, deduce one such that the platform height for the $$$1$$$-st place minimum as possible. If there are several of them, output any of them.

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

Each test case contains a single integer $$$n$$$ ($$$6 \le n \le 10^5$$$) — the total number of blocks for the pedestal. All $$$n$$$ blocks must be used.

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

Output format:
For each test case, output $$$3$$$ numbers $$$h_2, h_1, h_3$$$ — the platform heights for $$$2$$$-nd, $$$1$$$-st and $$$3$$$-rd places on a pedestal consisting of $$$n$$$ blocks ($$$h_1+h_2+h_3=n$$$, $$$0 < h_3 < h_2 < h_1$$$).

Among all possible pedestals, output the one for which the value of $$$h_1$$$ minimal. If there are several of them, output any of them.

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

Note:
In the first test case we can not get the height of the platform for the first place less than $$$5$$$, because if the height of the platform for the first place is not more than $$$4$$$, then we can use at most $$$4 + 3 + 2 = 9$$$ blocks. And we should use $$$11 = 4 + 5 + 2$$$ blocks. Therefore, the answer 4 5 2 fits.

In the second set, the only suitable answer is: 2 3 1.

Example input:
6
11
6
10
100000
7
8

Example output:
4 5 2
2 3 1
4 5 1
33334 33335 33331
2 4 1
3 4 1

Editorial:
In the $$$n \le 10^5$$$ constraints, the problem can be solved by brute force: we will go through the value for $$$h_1$$$ (the height for the first place), and then select suitable values for $$$h_2$$$ and $$$h_3$$$. Since $$$h_2 > h_3$$$, we divide the remaining $$$n - h_1$$$ blocks equally between $$$h_2$$$ and $$$h_3$$$. If it turns out that $$$h_2 = h_3$$$, then we try to decrease $$$h_3$$$ by $$$1$$$ and increase $$$h_2$$$ by 1. If we get the right answer ($$$h_1 > h_2 > h_3 > 1$$$), output the heights and stop the process. We will go through the value of $$$h_1$$$ in order of increasing.
Array Decrements
Contest: Codeforces Round 797 (Div. 3)
Difficulty rating: 800
Tags: greedy, implementation

Kristina has two arrays $$$a$$$ and $$$b$$$, each containing $$$n$$$ non-negative integers. She can perform the following operation on array $$$a$$$ any number of times:

- apply a decrement to each non-zero element of the array, that is, replace the value of each element $$$a_i$$$ such that $$$a_i > 0$$$ with the value $$$a_i - 1$$$ ($$$1 \le i \le n$$$). If $$$a_i$$$ was $$$0$$$, its value does not change.

Determine whether Kristina can get an array $$$b$$$ from an array $$$a$$$ in some number of operations (probably zero). In other words, can she make $$$a_i = b_i$$$ after some number of operations for each $$$1 \le i \le n$$$?

For example, let $$$n = 4$$$, $$$a = [3, 5, 4, 1]$$$ and $$$b = [1, 3, 2, 0]$$$. In this case, she can apply the operation twice:

- after the first application of the operation she gets $$$a = [2, 4, 3, 0]$$$;
- after the second use of the operation she gets $$$a = [1, 3, 2, 0]$$$.

Thus, in two operations, she can get an array $$$b$$$ from an array $$$a$$$.

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

The descriptions of the test cases follow.

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

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

The third line of each test case contains exactly $$$n$$$ non-negative integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \le 10^9$$$).

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

Output format:
For each test case, output on a separate line:

- YES, if by doing some number of operations it is possible to get an array $$$b$$$ from an array $$$a$$$;
- NO otherwise.

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:
The first test case is analyzed in the statement.

In the second test case, it is enough to apply the operation to array $$$a$$$ once.

In the third test case, it is impossible to get array $$$b$$$ from array $$$a$$$.

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

Example output:
YES
YES
NO
NO
YES
NO

Editorial:
For all elements of the arrays to become equal after subtraction of units, $$$a_i>=b_i$$$ for $$$1 \le i \le n$$$ must be satisfied. In addition, if there exists $$$b_i > 0$$$, then the equality $$$a_i = b_i$$$ can be obtained only by subtracting exactly $$$a_i - b_i$$$ units from $$$a_i$$$. Since the equality $$$a_i = b_i$$$ must be satisfied for all $$$i$$$, the problem is reduced to checking that for $$$b_i > 0$$$ all differences $$$a_i - b_i=dif$$$ are equal and for $$$b_i = 0$$$ the difference does not exceed $$$dif$$$.
Black and White Stripe
Contest: Codeforces Round 797 (Div. 3)
Difficulty rating: 1000
Tags: implementation, two pointers

You have a stripe of checkered paper of length $$$n$$$. Each cell is either white or black.

What is the minimum number of cells that must be recolored from white to black in order to have a segment of $$$k$$$ consecutive black cells on the stripe?

If the input data is such that a segment of $$$k$$$ consecutive black cells already exists, then print 0.

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

Next, descriptions of $$$t$$$ test cases follow.

The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2\cdot10^5$$$). The second line consists of the letters 'W' (white) and 'B' (black). The line length is $$$n$$$.

It is guaranteed that the sum of values $$$n$$$ does not exceed $$$2\cdot10^5$$$.

Output format:
For each of $$$t$$$ test cases print an integer — the minimum number of cells that need to be repainted from white to black in order to have a segment of $$$k$$$ consecutive black cells.

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

Note:
In the first test case, $$$s$$$="BBWBW" and $$$k=3$$$. It is enough to recolor $$$s_3$$$ and get $$$s$$$="BBBBW". This string contains a segment of length $$$k=3$$$ consisting of the letters 'B'.

In the second test case of the example $$$s$$$="BBWBW" and $$$k=5$$$. It is enough to recolor $$$s_3$$$ and $$$s_5$$$ and get $$$s$$$="BBBBB". This string contains a segment of length $$$k=5$$$ consisting of the letters 'B'.

In the third test case of the example $$$s$$$="BBWBW" and $$$k=1$$$. The string $$$s$$$ already contains a segment of length $$$k=1$$$ consisting of the letters 'B'.

Example input:
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W

Example output:
1
2
0
1

Editorial:
To obtain a segment of $$$k$$$ cells of black color, we need to paint all the white cells of the segment black. Then go through all the segments of length $$$k$$$ (there are only $$$n - k$$$) and choose such a segment among them that the number of white cells on it is minimal. You can quickly find out the number of white cells in the segment by prefix sums.
LLPS
Contest: Codeforces Round 127 (Div. 2)
Difficulty rating: 800
Tags: binary search, bitmasks, brute force, greedy, implementation, strings

This problem's actual name, "Lexicographically Largest Palindromic Subsequence" is too long to fit into the page headline.

You are given string s consisting of lowercase English letters only. Find its lexicographically largest palindromic subsequence.

We'll call a non-empty string s[p1p2... pk] = sp1sp2... spk (1  ≤  p1 < p2 < ... < pk  ≤  |s|) a subsequence of string s = s1s2... s|s|, where |s| is the length of string s. For example, strings "abcb", "b" and "abacaba" are subsequences of string "abacaba".

String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y| if either |x| > |y| and x1 = y1, x2 = y2, ..., x|y| = y|y|, or there exists such number r (r < |x|, r < |y|) that x1 = y1, x2 = y2, ..., xr = yr and xr  +  1 > yr  +  1. Characters in the strings are compared according to their ASCII codes. For example, string "ranger" is lexicographically larger than string "racecar" and string "poster" is lexicographically larger than string "post".

String s = s1s2... s|s| is a palindrome if it matches string rev(s) = s|s|s|s| - 1... s1. In other words, a string is a palindrome if it reads the same way from left to right and from right to left. For example, palindromic strings are "racecar", "refer" and "z".

Input format:
The only input line contains a non-empty string s consisting of lowercase English letters only. Its length does not exceed 10.

Output format:
Print the lexicographically largest palindromic subsequence of string s.

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

Note:
Among all distinct subsequences of string "radar" the following ones are palindromes: "a", "d", "r", "aa", "rr", "ada", "rar", "rdr", "raar" and "radar". The lexicographically largest of them is "rr".

Example input:
radar

Example output:
rr

Example input:
bowwowwow

Example output:
wwwww

Editorial:
Do Not Be Distracted!
Contest: Codeforces Round 719 (Div. 3)
Difficulty rating: 800
Tags: brute force, implementation

Polycarp has $$$26$$$ tasks. Each task is designated by a capital letter of the Latin alphabet.

The teacher asked Polycarp to solve tasks in the following way: if Polycarp began to solve some task, then he must solve it to the end, without being distracted by another task. After switching to another task, Polycarp cannot return to the previous task.

Polycarp can only solve one task during the day. Every day he wrote down what task he solved. Now the teacher wants to know if Polycarp followed his advice.

For example, if Polycarp solved tasks in the following order: "DDBBCCCBBEZ", then the teacher will see that on the third day Polycarp began to solve the task 'B', then on the fifth day he got distracted and began to solve the task 'C', on the eighth day Polycarp returned to the task 'B'. Other examples of when the teacher is suspicious: "BAB", "AABBCCDDEEBZZ" and "AAAAZAAAAA".

If Polycarp solved the tasks as follows: "FFGZZZY", then the teacher cannot have any suspicions. Please note that Polycarp is not obligated to solve all tasks. Other examples of when the teacher doesn't have any suspicious: "BA", "AFFFCC" and "YYYYY".

Help Polycarp find out if his teacher might be suspicious.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$). Then $$$t$$$ test cases follow.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 50$$$) — the number of days during which Polycarp solved tasks.

The second line contains a string of length $$$n$$$, consisting of uppercase Latin letters, which is the order in which Polycarp solved the tasks.

Output format:
For each test case output:

- "YES", if the teacher cannot be suspicious;
- "NO", otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

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

Example input:
5
3
ABA
11
DDBBCCCBBEZ
7
FFGZZZY
1
Z
2
AB

Example output:
NO
NO
YES
YES
YES

Editorial:
The simplest solution — go through the problem, because of which the teacher might have suspicions. Now you can find the first day when Polycarp solved this problem and the last such day. Between these two days, all problems should be the same. If this is not the case, the answer is "NO".
Ordinary Numbers
Contest: Codeforces Round 719 (Div. 3)
Difficulty rating: 800
Tags: brute force, math, number theory

Let's call a positive integer $$$n$$$ ordinary if in the decimal notation all its digits are the same. For example, $$$1$$$, $$$2$$$ and $$$99$$$ are ordinary numbers, but $$$719$$$ and $$$2021$$$ are not ordinary numbers.

For a given number $$$n$$$, find the number of ordinary numbers among the numbers from $$$1$$$ to $$$n$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

Each test case is characterized by one integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output format:
For each test case output the number of ordinary numbers among numbers from $$$1$$$ to $$$n$$$.

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

Example input:
6
1
2
3
4
5
100

Example output:
1
2
3
4
5
18

Editorial:
Note that every ordinary number can be represented as $$$d \cdot (10^0 + 10^1 + \ldots + 10^k)$$$. Therefore, to count all ordinary numbers among the numbers from $$$1$$$ to $$$ n $$$, it is enough to count the number of $$$(d, k)$$$ pairs such that $$$d \cdot (10^0 + 10^1 + \ldots + 10^k) \le n$$$. In the given constraints, it is enough to iterate over $$$d$$$ from $$$1$$$ to $$$9$$$ and $$$k$$$ from $$$0$$$ to $$$8$$$.