You are given some text t and a set of n strings .
In one step, you can choose any occurrence of any string in the text and color the corresponding characters of the text in red. For example, if and , , you can get , or in one step.
You want to color all the letters of the text t in red. When you color a letter in red again, it stays red.
In the example above, three steps are enough:
Let’s color in red, we get ;
Let’s color in red, we get ;
Let’s color in red, we get . Each string can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily.
Determine the minimum number of steps needed to color all letters t in red and how to do it. If it is impossible to color all letters of the text t in red, output -1.
The first line of the input contains an integer —the number of test cases in the test.
The descriptions of the test cases follow.
The first line of each test case contains the text , consisting only of lowercase Latin letters, where is the length of the text t.
The second line of each test case contains a single integer — the number of strings in the set.
This is followed by n lines, each containing a string consisting only of lowercase Latin letters, where — the length of string .
For each test case, print the answer on a separate line.
If it is impossible to color all the letters of the text in red, print a single line containing the number -1.
Otherwise, on the first line, print the number m — the minimum number of steps it will take to turn all the letters t red.
Then in the next m lines print pairs of indices: and , which denote that the string with index was used as a substring to cover the occurrences starting in the text t from position . The pairs can be output in any order.
You can apply the following operation an arbitrary number of times:
select an index and replace the value of the element with the value , where is the remainder of the integer dividing by .
For a single index (value ), this operation can be applied multiple times. If the operation is applied repeatedly to the same index, then the current value of is taken into account each time. For example, if then after the first operation we get , and after the second operation we get .
Check if it is possible to make all array elements equal by applying multiple (possibly zero) operations.
For example, you have an array .
Let’s apply this operation to the first element of the array. Let’s replace with . We get the array .
Then apply this operation to the second element of the array. Let’s replace with . We get the array .
Thus, by applying 2 operations, you can make all elements of an array equal.
The first line contains one integer — the number of test cases. What follows is a description of each test case.
The first line of each test case contains one integer — the size of the array.
The second line of each test case contains n integers — array elements.
It is guaranteed that the sum of n over all test cases does not exceed .
For each test case print:
YES if it is possible to make all array elements equal;
You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer) .
You are given a rooted tree. It contains vertices, which are numbered from to . The root is the vertex .
Each edge has two positive integer values. Thus, two positive integers and are given for each edge.
Output numbers , where $r_i is defined as follows.
Consider the path from the root (vertex ) to . Let the sum of the costs of along this path be . Then is equal to the length of the maximum prefix of this path such that the sum of along this prefix does not exceed .