meetforever/GRPO_CL huggingface dataset:
user: You are given two strings $s$ and $t$, each of length $n$ and consisting of lowercase Latin alphabets. You want to make $s$ equal to $t$. 

You can perform the following operation on $s$ any number of times to achieve it —   Choose any substring of $s$ and rotate it clockwise once, that is, if the selected substring is $s[l,l+1...r]$, then it becomes $s[r,l,l + 1 ... r - 1]$. All the remaining characters of $s$ stay in their position. 

For example, on rotating the substring $[2,4]$ , string "abcde" becomes "adbce". 

A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Find the minimum number of operations required to convert $s$ to $t$, or determine that it's impossible.


-----Input-----

The first line of the input contains a single integer $t$ $(1\leq t \leq 2000)$ — 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\leq n \leq 2000)$ — the length of the strings. 

The second and the third lines contain strings $s$ and $t$ respectively.

The sum of $n$ over all the test cases does not exceed $2000$.


-----Output-----

For each test case, output the minimum number of operations to convert $s$ to $t$. If it is not possible to convert $s$ to $t$, output $-1$ instead.


-----Example-----
Input
6
1
a
a
2
ab
ba
3
abc
cab
3
abc
cba
4
abab
baba
4
abcc
aabc

Output
0
1
1
2
1
-1



-----Note-----

For the $1$-st test case, since $s$ and $t$ are equal, you don't need to apply any operation.

For the $2$-nd test case, you only need to apply one operation on the entire string ab to convert it to ba.

For the $3$-rd test case, you only need to apply one operation on the entire string abc to convert it to cab.

For the $4$-th test case, you need to apply the operation twice: first on the entire string abc to convert it to cab and then on the substring of length $2$ beginning at the second character to convert it to cba.

For the $5$-th test case, you only need to apply one operation on the entire string abab to convert it to baba.

For the $6$-th test case, it is not possible to convert string $s$ to $t$.
user: The problem was inspired by Pied Piper story. After a challenge from Hooli's compression competitor Nucleus, Richard pulled an all-nighter to invent a new approach to compression: middle-out.

You are given two strings $s$ and $t$ of the same length $n$. Their characters are numbered from $1$ to $n$ from left to right (i.e. from the beginning to the end).

In a single move you can do the following sequence of actions:

  choose any valid index $i$ ($1 \le i \le n$),  move the $i$-th character of $s$ from its position to the beginning of the string or move the $i$-th character of $s$ from its position to the end of the string. 

Note, that the moves don't change the length of the string $s$. You can apply a move only to the string $s$.

For example, if $s=$"test" in one move you can obtain:

  if $i=1$ and you move to the beginning, then the result is "test" (the string doesn't change),  if $i=2$ and you move to the beginning, then the result is "etst",  if $i=3$ and you move to the beginning, then the result is "stet",  if $i=4$ and you move to the beginning, then the result is "ttes",  if $i=1$ and you move to the end, then the result is "estt",  if $i=2$ and you move to the end, then the result is "tste",  if $i=3$ and you move to the end, then the result is "tets",  if $i=4$ and you move to the end, then the result is "test" (the string doesn't change). 

You want to make the string $s$ equal to the string $t$. What is the minimum number of moves you need? If it is impossible to transform $s$ to $t$, print -1.


-----Input-----

The first line contains integer $q$ ($1 \le q \le 100$) — the number of independent test cases in the input.

Each test case is given in three lines. The first line of a test case contains $n$ ($1 \le n \le 100$) — the length of the strings $s$ and $t$. The second line contains $s$, the third line contains $t$. Both strings $s$ and $t$ have length $n$ and contain only lowercase Latin letters.

There are no constraints on the sum of $n$ in the test (i.e. the input with $q=100$ and all $n=100$ is allowed).


-----Output-----

For every test print minimum possible number of moves, which are needed to transform $s$ into $t$, or -1, if it is impossible to do.


-----Examples-----
Input
3
9
iredppipe
piedpiper
4
estt
test
4
tste
test

Output
2
1
2

Input
4
1
a
z
5
adhas
dasha
5
aashd
dasha
5
aahsd
dasha

Output
-1
2
2
3



-----Note-----

In the first example, the moves in one of the optimal answers are:

  for the first test case $s=$"iredppipe", $t=$"piedpiper": "iredppipe" $\rightarrow$ "iedppiper" $\rightarrow$ "piedpiper";  for the second test case $s=$"estt", $t=$"test": "estt" $\rightarrow$ "test";  for the third test case $s=$"tste", $t=$"test": "tste" $\rightarrow$ "etst" $\rightarrow$ "test".
user: You have a string $s$ of length $n$ consisting of only characters > and <. You may do some operations with this string, for each operation you have to choose some character that still remains in the string. If you choose a character >, the character that comes right after it is deleted (if the character you chose was the last one, nothing happens). If you choose a character <, the character that comes right before it is deleted (if the character you chose was the first one, nothing happens).

For example, if we choose character > in string > > < >, the string will become to > > >. And if we choose character < in string > <, the string will become to <.

The string is good if there is a sequence of operations such that after performing it only one character will remain in the string. For example, the strings >, > > are good. 

Before applying the operations, you may remove any number of characters from the given string (possibly none, possibly up to $n - 1$, but not the whole string). You need to calculate the minimum number of characters to be deleted from string $s$ so that it becomes good.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) – the number of test cases. Each test case is represented by two lines.

The first line of $i$-th test case contains one integer $n$ ($1 \le n \le 100$) – the length of string $s$.

The second line of $i$-th test case contains string $s$, consisting of only characters > and <.


-----Output-----

For each test case print one line.

For $i$-th test case print the minimum number of characters to be deleted from string $s$ so that it becomes good.


-----Example-----
Input
3
2
<>
3
><<
1
>

Output
1
0
0



-----Note-----

In the first test case we can delete any character in string <>.

In the second test case we don't need to delete any characters. The string > < < is good, because we can perform the following sequence of operations: > < < $\rightarrow$ < < $\rightarrow$ <.
user: Вам задано прямоугольное клетчатое поле, состоящее из n строк и m столбцов. Поле содержит цикл из символов «*», такой что:  цикл можно обойти, посетив каждую его клетку ровно один раз, перемещаясь каждый раз вверх/вниз/вправо/влево на одну клетку;  цикл не содержит самопересечений и самокасаний, то есть две клетки цикла соседствуют по стороне тогда и только тогда, когда они соседние при перемещении вдоль цикла (самокасание по углу тоже запрещено). 

Ниже изображены несколько примеров допустимых циклов: [Image] 

Все клетки поля, отличные от цикла, содержат символ «.». Цикл на поле ровно один. Посещать клетки, отличные от цикла, Роботу нельзя.

В одной из клеток цикла находится Робот. Эта клетка помечена символом «S». Найдите последовательность команд для Робота, чтобы обойти цикл. Каждая из четырёх возможных команд кодируется буквой и обозначает перемещение Робота на одну клетку:  «U» — сдвинуться на клетку вверх,  «R» — сдвинуться на клетку вправо,  «D» — сдвинуться на клетку вниз,  «L» — сдвинуться на клетку влево. 

Робот должен обойти цикл, побывав в каждой его клетке ровно один раз (кроме стартовой точки — в ней он начинает и заканчивает свой путь).

Найдите искомую последовательность команд, допускается любое направление обхода цикла.


-----Входные данные-----

В первой строке входных данных записаны два целых числа n и m (3 ≤ n, m ≤ 100) — количество строк и столбцов прямоугольного клетчатого поля соответственно.

В следующих n строках записаны по m символов, каждый из которых — «.», «*» или «S». Гарантируется, что отличные от «.» символы образуют цикл без самопересечений и самокасаний. Также гарантируется, что на поле ровно одна клетка содержит «S» и что она принадлежит циклу. Робот не может посещать клетки, помеченные символом «.».


-----Выходные данные-----

В первую строку выходных данных выведите искомую последовательность команд для Робота. Направление обхода цикла Роботом может быть любым.


-----Примеры-----
Входные данные
3 3
***
*.*
*S*

Выходные данные
LUURRDDL

Входные данные
6 7
.***...
.*.*...
.*.S**.
.*...**
.*....*
.******

Выходные данные
UULLDDDDDRRRRRUULULL



-----Примечание-----

В первом тестовом примере для обхода по часовой стрелке последовательность посещенных роботом клеток выглядит следующим образом:  клетка (3, 2);  клетка (3, 1);  клетка (2, 1);  клетка (1, 1);  клетка (1, 2);  клетка (1, 3);  клетка (2, 3);  клетка (3, 3);  клетка (3, 2).
user: Miyako came to the flea kingdom with a ukulele. She became good friends with local flea residents and played beautiful music for them every day.

In return, the fleas made a bigger ukulele for her: it has $n$ strings, and each string has $(10^{18} + 1)$ frets numerated from $0$ to $10^{18}$. The fleas use the array $s_1, s_2, \ldots, s_n$ to describe the ukulele's tuning, that is, the pitch of the $j$-th fret on the $i$-th string is the integer $s_i + j$.

Miyako is about to leave the kingdom, but the fleas hope that Miyako will answer some last questions for them.

Each question is in the form of: "How many different pitches are there, if we consider frets between $l$ and $r$ (inclusive) on all strings?"

Miyako is about to visit the cricket kingdom and has no time to answer all the questions. Please help her with this task!

Formally, you are given a matrix with $n$ rows and $(10^{18}+1)$ columns, where the cell in the $i$-th row and $j$-th column ($0 \le j \le 10^{18}$) contains the integer $s_i + j$. You are to answer $q$ queries, in the $k$-th query you have to answer the number of distinct integers in the matrix from the $l_k$-th to the $r_k$-th columns, inclusive.


-----Input-----

The first line contains an integer $n$ ($1 \leq n \leq 100\,000$) — the number of strings.

The second line contains $n$ integers $s_1, s_2, \ldots, s_n$ ($0 \leq s_i \leq 10^{18}$) — the tuning of the ukulele.

The third line contains an integer $q$ ($1 \leq q \leq 100\,000$) — the number of questions.

The $k$-th among the following $q$ lines contains two integers $l_k$，$r_k$ ($0 \leq l_k \leq r_k \leq 10^{18}$) — a question from the fleas.


-----Output-----

Output one number for each question, separated by spaces — the number of different pitches.


-----Examples-----
Input
6
3 1 4 1 5 9
3
7 7
0 2
8 17

Output
5 10 18

Input
2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000

Output
2 1500000000000000000



-----Note-----

For the first example, the pitches on the $6$ strings are as follows.

$$ \begin{matrix} \textbf{Fret} & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \ldots \\ s_1: & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ s_2: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_3: & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \dots \\ s_4: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_5: & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \dots \\ s_6: & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \dots \end{matrix} $$

There are $5$ different pitches on fret $7$ — $8, 10, 11, 12, 16$.

There are $10$ different pitches on frets $0, 1, 2$ — $1, 2, 3, 4, 5, 6, 7, 9, 10, 11$.
user: Palindromic characteristics of string s with length |s| is a sequence of |s| integers, where k-th number is the total number of non-empty substrings of s which are k-palindromes.

A string is 1-palindrome if and only if it reads the same backward as forward.

A string is k-palindrome (k > 1) if and only if:   Its left half equals to its right half.  Its left and right halfs are non-empty (k - 1)-palindromes. 

The left half of string t is its prefix of length ⌊|t| / 2⌋, and right half — the suffix of the same length. ⌊|t| / 2⌋ denotes the length of string t divided by 2, rounded down.

Note that each substring is counted as many times as it appears in the string. For example, in the string "aaa" the substring "a" appears 3 times.


-----Input-----

The first line contains the string s (1 ≤ |s| ≤ 5000) consisting of lowercase English letters.


-----Output-----

Print |s| integers — palindromic characteristics of string s.


-----Examples-----
Input
abba

Output
6 1 0 0 

Input
abacaba

Output
12 4 1 0 0 0 0 



-----Note-----

In the first example 1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.
user: You are given two positive integer numbers x and y. An array F is called an y-factorization of x iff the following conditions are met:  There are y elements in F, and all of them are integer numbers;  $\prod_{i = 1}^{y} F_{i} = x$. 

You have to count the number of pairwise distinct arrays that are y-factorizations of x. Two arrays A and B are considered different iff there exists at least one index i (1 ≤ i ≤ y) such that A_{i} ≠ B_{i}. Since the answer can be very large, print it modulo 10^9 + 7.


-----Input-----

The first line contains one integer q (1 ≤ q ≤ 10^5) — the number of testcases to solve.

Then q lines follow, each containing two integers x_{i} and y_{i} (1 ≤ x_{i}, y_{i} ≤ 10^6). Each of these lines represents a testcase.


-----Output-----

Print q integers. i-th integer has to be equal to the number of y_{i}-factorizations of x_{i} modulo 10^9 + 7.


-----Example-----
Input
2
6 3
4 2

Output
36
6



-----Note-----

In the second testcase of the example there are six y-factorizations:  { - 4,  - 1};  { - 2,  - 2};  { - 1,  - 4};  {1, 4};  {2, 2};  {4, 1}.
user: The sequence of integers $a_1, a_2, \dots, a_k$ is called a good array if $a_1 = k - 1$ and $a_1 > 0$. For example, the sequences $[3, -1, 44, 0], [1, -99]$ are good arrays, and the sequences $[3, 7, 8], [2, 5, 4, 1], [0]$ — are not.

A sequence of integers is called good if it can be divided into a positive number of good arrays. Each good array should be a subsegment of sequence and each element of the sequence should belong to exactly one array. For example, the sequences $[2, -3, 0, 1, 4]$, $[1, 2, 3, -3, -9, 4]$ are good, and the sequences $[2, -3, 0, 1]$, $[1, 2, 3, -3 -9, 4, 1]$ — are not.

For a given sequence of numbers, count the number of its subsequences that are good sequences, and print the number of such subsequences modulo 998244353.


-----Input-----

The first line contains the number $n~(1 \le n \le 10^3)$ — the length of the initial sequence. The following line contains $n$ integers $a_1, a_2, \dots, a_n~(-10^9 \le a_i \le 10^9)$ — the sequence itself.


-----Output-----

In the single line output one integer — the number of subsequences of the original sequence that are good sequences, taken modulo 998244353.


-----Examples-----
Input
3
2 1 1

Output
2

Input
4
1 1 1 1

Output
7



-----Note-----

In the first test case, two good subsequences — $[a_1, a_2, a_3]$ and $[a_2, a_3]$.

In the second test case, seven good subsequences — $[a_1, a_2, a_3, a_4], [a_1, a_2], [a_1, a_3], [a_1, a_4], [a_2, a_3], [a_2, a_4]$ and $[a_3, a_4]$.
user: The last contest held on Johnny's favorite competitive programming platform has been received rather positively. However, Johnny's rating has dropped again! He thinks that the presented tasks are lovely, but don't show the truth about competitors' skills.

The boy is now looking at the ratings of consecutive participants written in a binary system. He thinks that the more such ratings differ, the more unfair is that such people are next to each other. He defines the difference between two numbers as the number of bit positions, where one number has zero, and another has one (we suppose that numbers are padded with leading zeros to the same length). For example, the difference of $5 = 101_2$ and $14 = 1110_2$ equals to $3$, since $0101$ and $1110$ differ in $3$ positions. Johnny defines the unfairness of the contest as the sum of such differences counted for neighboring participants.

Johnny has just sent you the rating sequence and wants you to find the unfairness of the competition. You have noticed that you've got a sequence of consecutive integers from $0$ to $n$. That's strange, but the boy stubbornly says that everything is right. So help him and find the desired unfairness for received numbers.


-----Input-----

The input consists of multiple test cases. The first line contains one integer $t$ ($1 \leq t \leq 10\,000$) — the number of test cases. The following $t$ lines contain a description of test cases.

The first and only line in each test case contains a single integer $n$ ($1 \leq n \leq 10^{18})$.


-----Output-----

Output $t$ lines. For each test case, you should output a single line with one integer — the unfairness of the contest if the rating sequence equals to $0$, $1$, ..., $n - 1$, $n$.


-----Example-----
Input
5
5
7
11
1
2000000000000

Output
8
11
19
1
3999999999987



-----Note-----

For $n = 5$ we calculate unfairness of the following sequence (numbers from $0$ to $5$ written in binary with extra leading zeroes, so they all have the same length):   $000$  $001$  $010$  $011$  $100$  $101$ 

The differences are equal to $1$, $2$, $1$, $3$, $1$ respectively, so unfairness is equal to $1 + 2 + 1 + 3 + 1 = 8$.
user: At first, there was a legend related to the name of the problem, but now it's just a formal statement.

You are given $n$ points $a_1, a_2, \dots, a_n$ on the $OX$ axis. Now you are asked to find such an integer point $x$ on $OX$ axis that $f_k(x)$ is minimal possible.

The function $f_k(x)$ can be described in the following way:   form a list of distances $d_1, d_2, \dots, d_n$ where $d_i = |a_i - x|$ (distance between $a_i$ and $x$);  sort list $d$ in non-descending order;  take $d_{k + 1}$ as a result. 

If there are multiple optimal answers you can print any of them.


-----Input-----

The first line contains single integer $T$ ($ 1 \le T \le 2 \cdot 10^5$) — number of queries. Next $2 \cdot T$ lines contain descriptions of queries. All queries are independent. 

The first line of each query contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k < n$) — the number of points and constant $k$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 < a_2 < \dots < a_n \le 10^9$) — points in ascending order.

It's guaranteed that $\sum{n}$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $T$ integers — corresponding points $x$ which have minimal possible value of $f_k(x)$. If there are multiple answers you can print any of them.


-----Example-----
Input
3
3 2
1 2 5
2 1
1 1000000000
1 0
4

Output
3
500000000
4
user: You have a set of $n$ discs, the $i$-th disc has radius $i$. Initially, these discs are split among $m$ towers: each tower contains at least one disc, and the discs in each tower are sorted in descending order of their radii from bottom to top.

You would like to assemble one tower containing all of those discs. To do so, you may choose two different towers $i$ and $j$ (each containing at least one disc), take several (possibly all) top discs from the tower $i$ and put them on top of the tower $j$ in the same order, as long as the top disc of tower $j$ is bigger than each of the discs you move. You may perform this operation any number of times.

For example, if you have two towers containing discs $[6, 4, 2, 1]$ and $[8, 7, 5, 3]$ (in order from bottom to top), there are only two possible operations:

  move disc $1$ from the first tower to the second tower, so the towers are $[6, 4, 2]$ and $[8, 7, 5, 3, 1]$;  move discs $[2, 1]$ from the first tower to the second tower, so the towers are $[6, 4]$ and $[8, 7, 5, 3, 2, 1]$. 

Let the difficulty of some set of towers be the minimum number of operations required to assemble one tower containing all of the discs. For example, the difficulty of the set of towers $[[3, 1], [2]]$ is $2$: you may move the disc $1$ to the second tower, and then move both discs from the second tower to the first tower.

You are given $m - 1$ queries. Each query is denoted by two numbers $a_i$ and $b_i$, and means "merge the towers $a_i$ and $b_i$" (that is, take all discs from these two towers and assemble a new tower containing all of them in descending order of their radii from top to bottom). The resulting tower gets index $a_i$.

For each $k \in [0, m - 1]$, calculate the difficulty of the set of towers after the first $k$ queries are performed.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($2 \le m \le n \le 2 \cdot 10^5$) — the number of discs and the number of towers, respectively.

The second line contains $n$ integers $t_1$, $t_2$, ..., $t_n$ ($1 \le t_i \le m$), where $t_i$ is the index of the tower disc $i$ belongs to. Each value from $1$ to $m$ appears in this sequence at least once.

Then $m - 1$ lines follow, denoting the queries. Each query is represented by two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le m$, $a_i \ne b_i$), meaning that, during the $i$-th query, the towers with indices $a_i$ and $b_i$ are merged ($a_i$ and $b_i$ are chosen in such a way that these towers exist before the $i$-th query).


-----Output-----

Print $m$ integers. The $k$-th integer ($0$-indexed) should be equal to the difficulty of the set of towers after the first $k$ queries are performed.


-----Example-----
Input
7 4
1 2 3 3 1 4 3
3 1
2 3
2 4

Output
5
4
2
0



-----Note-----

The towers in the example are:

  before the queries: $[[5, 1], [2], [7, 4, 3], [6]]$;  after the first query: $[[2], [7, 5, 4, 3, 1], [6]]$;  after the second query: $[[7, 5, 4, 3, 2, 1], [6]]$;  after the third query, there is only one tower: $[7, 6, 5, 4, 3, 2, 1]$.