401462: GYM100460 H A Ballad about the Tear

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. A Ballad about the Teartime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

As usual, in the royal palace of Enia, alone with the evil dark magician Deimos occupied the throne the beautiful elven princess called Alatiel is languishing. Deimos hasn't killed her yet because he has plans to persuade the lady to marry him, and in case of refusal to use her blood at the night of Superposition to open gates to his frozen world.

Alatiel is the old friend of Desmond, who was sent out from Enia because of a known kind of relations with her. But since everything is going on in the fairyland she hasn't forgotten her lover and has been dreaming only about him all the time. Even now she is sitting near the window at night and remembering how great it was for them to be together, while stars are miraculously drawing his name on the sky.

There are total of 26 letters in Elven alphabet, which we denote by lowercase latin letters. Constellations on the sky are aligned as a line one after another, each becoming similar to one letter, then another, until Alatiel becomes able to read the word «desmond» from the sequence of seven adjacent constellations. Your task is to determine how many times the constellations change their form before it happens.

Input

The first line consist of n lowercase latin letters (1 ≤ n ≤ 105). It denotes the letters that the corresponding constellations were similar to at the start.

The second line contains one integer m (1 ≤ m ≤ 105) — the number of times constellations changed their form. Each of the next m lines contains the integer and the lowercase latin letter separated by the space: aj and cj (1 ≤ aj ≤ n) — the number of constellation which changed the form and the letter it became similar to (possibly the same letter it was similar to before changing form). Constellations are numbered starting by one from left to right.

Output

In the first line output «I love you, Desmond!» (without quotes) if at some moment seven adjacent constellations made the word «desmond». In this case in the second line output one integer — the number of changes of constellation's forms after that this word firstly appeared. If this word has not appeared at all, in the only line output «Goodbye, my love!» (without quotes).

ExamplesInput
diamond
2
2 e
3 s
Output
I love you, Desmond!
2
Input
diamond
1
2 e
Output
Goodbye, my love!

加入题单

上一题 下一题 算法标签: