## D. Color with Occurrences

You are given some text t and a set of n strings

In one step, you can choose any occurrence of any string

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 stringcan 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.

**Input**

The first line of the input contains an integer

The descriptions of the test cases follow.

The first line of each test case contains the text

The second line of each test case contains a single integer

This is followed by n lines, each containing a string

**Output**

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:

If there are several answers, output any of them.

### 解法一

题目核心其实是一个区间覆盖的问题，每个

代码实现如下：

import java.util.*; |

## E. Add Modulo 10

You are given an array of n integers

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

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.

**Input**

The first line contains one integer

The first line of each test case contains one integer

The second line of each test case contains n integers

It is guaranteed that the sum of n over all test cases does not exceed

**Output**

For each test case print:

- YES if it is possible to make all array elements equal;
- NO otherwise.

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) .

### 解法一

找规律，题目大意是给定一组数组，尝试替换

我们可以将元素替换序列都列出来，然后找规律，进行分组，具体见代码：

import java.util.*; |

## G. Path Prefixes

You are given a rooted tree. It contains

Each edge has two positive integer values. Thus, two positive integers

Output

Consider the path from the root (vertex

… 题目太长，懒得copy，去看原题吧

### 解法一

dfs栈上二分，如果这题放在D或者E我肯定能写出来，放在后面并且题目这么长，让人有点畏惧，不过说到底还是太菜了。

import java.util.*; |

### 解法二

倍增的做法，学习下

import java.util.*; |