Prefix-Suffix Dictionary#374

Prefix-Suffix Dictionary

1 seconde
256 mégaoctets
Hard

Sakurako just found the oldest dictionary in the whole universe. It contains more than words. Sakurako can create new words based on these words.

Every new word can be constructed by taking a prefix of some word from the dictionary and concatenating it with a suffix of some word (can be the same word). The length of the newly constructed word should be at most 10^3. It is possible to choose empty prefixes and suffixes.

Each time, Sakurako can create a new word, choosing any two existing words (even those that she has created).

Sakurako wonders if it is possible to create her favorite word without creating more than new words.

Input

The first line contains one string (1\le |s|\le 10^3) — the word Sakurako is interested in. The string contains only lower case English letters.

The second line contains one integer (1\le n\le 10^5) — the number of words in the dictionary initially.

Each of the next lines contains one string a_i (1\le |a_i|\le 10^3) — first words that were in the dictionary, which contain only lower case English letters. It is guaranteed that the sum of all the lengths does not exceed 2 \cdot 10^5.

Output

Output "No" if it is not possible and "Yes" otherwise.

If it is possible, output integer (0\le k\le 2\,000), the number of operations you need to do to get string and next lines describe operations. Note that there is no need to minimize this value.

Each line contains four integers:

  • i_p (1 \leq i_p \leq t, where is the number of strings at that time) is the index of the string from which we are taking a prefix;

  • l_p (0 \leq l_p \leq |a_{i_p}|, where |a_{i_p}| is the length of the i_p-th string) is the length of the prefix we want to take;

  • i_s (1 \leq i_s \leq t, where is the number of strings at that time) is the index of the string from which we are taking a suffix;

  • l_s (0 \leq l_s \leq |a_{i_s}|, 1 \leq l_p + l_s \leq 10^3, where |a_{i_s}| is the length of the i_s-th string) is the length of the suffix we want to take.

The -th word will be having index n+i.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Note that testing is going test by test, but not by blocks.

  1. ( points): and a_i for all contain only letters and ;

  2. ( points): n\le 1\,000;

  3. ( points): without additional constraints.