Let’s define a multiplication operation between a string a and a positive integer x: a⋅x is the string that is a result of writing x copies of a one after another. For example, “abc” ⋅2= “abcabc”, “a” ⋅5= “aaaaa”.
A string a is divisible by another string b if there exists an integer x such that b⋅x=a. For example, “abababab” is divisible by “ab”, but is not divisible by “ababab” or “aa”.
LCM of two strings s and t (defined as LCM(s,t)) is the shortest non-empty string that is divisible by both s and t.
You are given two strings s and t. Find LCM(s,t) or report that it does not exist. It can be shown that if LCM(s,t) exists, it is unique.
The first line contains one integer q (1≤q≤2000) — the number of test cases.
Each test case consists of two lines, containing strings s and t (1≤∣s∣,∣t∣≤20). Each character in each of these strings is either ‘a’ or ‘b’.
For each test case, print LCM(s,t) if it exists; otherwise, print -1 . It can be shown that if LCM(s,t) exists, it is unique.
1 2 3 4 5 6 7
3 baba ba aa aaa aba ab
1 2 3
baba aaaaaa -1
In the first test case, “baba” = “baba” ⋅1= “ba” ⋅2.
In the second test case, “aaaaaa” = “aa” ⋅3= “aaa” ⋅2.
You have a sequence a with n elements 1,2,3,…,k−1,k,k−1,k−2,…,k−(n−k) (k≤n<2k).
Let’s call as inversion in a a pair of indices i<j such that a[i]>a[j].
Suppose, you have some permutation p of size k and you build a sequence b of size n in the following manner: b[i]=p[a[i]].
Your goal is to find such permutation p that the total number of inversions in b doesn’t exceed the total number of inversions in a, and b is lexicographically maximum .
Small reminder: the sequence of k integers is called a permutation if it contains all integers from 1 to k exactly once.
Another small reminder: a sequence s is lexicographically smaller than another sequence t, if either s is a prefix of t, or for the first i such that si=ti, si<ti holds (in the first position that these sequences are different, s has smaller number than t).
The first line contains a single integer t (1≤t≤1000) — the number of test cases.
The first and only line of each test case contains two integers n and k (k≤n<2k; 1≤k≤105) — the length of the sequence a and its maximum.
It’s guaranteed that the total sum of k over test cases doesn’t exceed 105.
For each test case, print k integers — the permutation p which maximizes b lexicographically without increasing the total number of inversions.
It can be proven that p exists and is unique.
1 2 3 4 5
4 1 1 2 2 3 2 4 3
1 2 3 4
1 1 2 2 1 1 3 2
In the first test case, the sequence a=, there is only one permutation p=.
In the second test case, the sequence a=[1,2]. There is no inversion in a, so there is only one permutation p=[1,2] which doesn’t increase the number of inversions.
In the third test case, a=[1,2,1] and has 1 inversion. If we use p=[2,1], then b=[p[a],p[a],p[a]]=[2,1,2] and also has 1 inversion.
In the fourth test case, a=[1,2,3,2], and since p=[1,3,2] then b=[1,3,2,3]. Both a and b have 1 inversion and b is the lexicographically maximum.
考虑到 a 中的逆序列数目共有 i=1∑n−k=2(n−k)(n−k+1) 个，全部由序列的后半部分 k,(k−1),⋯,k−(n−k) 所贡献，因此只需要保证 b 中的逆序列构造方式和 a 相同即可。
因此构造 p=[1,2,⋯,(2k−n−1),k,(k−1),⋯,k−(n−k)] 即可。容易发现 b 序列中的逆序列部分和 p 相同。
You are given a program that consists of n instructions. Initially a single variable x is assigned to 0. Afterwards, the instructions are of two types:
increase x by 1;
decrease x by 1.
You are given m queries of the following format:
query lr — how many distinct values is x assigned to if all the instructions between the l-th one and the r-th one inclusive are ignored and the rest are executed without changing the order?
The first line contains a single integer t (1≤t≤1000) — the number of testcases.
Then the description of t testcases follows.
The first line of each testcase contains two integers n and m (1≤n,m≤2⋅105) — the number of instructions in the program and the number of queries.
The second line of each testcase contains a program — a string of n characters: each character is either ‘+’ or ‘-’ — increment and decrement instruction, respectively.
Each of the next m lines contains two integers l and r (1≤l≤r≤n) — the description of the query.
The sum of n over all testcases doesn’t exceed 2⋅105. The sum of m over all testcases doesn’t exceed 2⋅105.
For each testcase print m integers — for each query l, r print the number of distinct values variable x is assigned to if all the instructions between the l-th one and the r-th one inclusive are ignored and the rest are executed without changing the order.