## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Color with Occurrences Codeforces Solution

D. Color with Occurrences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given some text $t$ and a set of $n$ strings ${s}_{1},{s}_{2},\dots ,{s}_{n}$.

In one step, you can choose any occurrence of any string ${s}_{i}$ in the text $t$ and color the corresponding characters of the text in red. For example, if $t=\mathtt{\text{bababa}}$ and ${s}_{1}=\mathtt{\text{ba}}$${s}_{2}=\mathtt{\text{aba}}$, you can get $t=\mathtt{\text{ba}}\mathtt{\text{baba}}$$t=\mathtt{\text{b}}\mathtt{\text{aba}}\mathtt{\text{ba}}$ or $t=\mathtt{\text{bab}}\mathtt{\text{aba}}$ 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 $t\left[2\dots 4\right]={s}_{2}=\mathtt{\text{aba}}$ in red, we get $t=\mathtt{\text{b}}\mathtt{\text{aba}}\mathtt{\text{ba}}$;
• Let's color $t\left[1\dots 2\right]={s}_{1}=\mathtt{\text{ba}}$ in red, we get $t=\mathtt{\text{baba}}\mathtt{\text{ba}}$;
• Let's color $t\left[4\dots 6\right]={s}_{2}=\mathtt{\text{aba}}$ in red, we get $t=\mathtt{\text{bababa}}$.

Each string ${s}_{i}$ can be applied any number of times (or not at all). Occurrences for coloring can intersect

Solution Click Below:-  👉

👇👇👇👇👇

occupied

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 $q$ ($1\le q\le 100$) —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 $t$ ($1\le |t|\le 100$), consisting only of lowercase Latin letters, where $|t|$ is the length of the text $t$.

The second line of each test case contains a single integer $n$ ($1\le n\le 10$) — the number of strings in the set.

This is followed by $n$ lines, each containing a string ${s}_{i}$ ($1\le |{s}_{i}|\le 10$) consisting only of lowercase Latin letters, where $|{s}_{i}|$ — the length of string ${s}_{i}$.

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: ${w}_{j}$ and ${p}_{j}$ ($1\le j\le m$), which denote that the line with index ${w}_{j}$ was used as a substring to cover the occurrences starting in the text $t$ from position ${p}_{j}$. The pairs can be output in any order.

If there are several answers, output any of them.