Under construction

Still being built. Things may change

Haiku

Interview

Time limit1sMemory limit512 MB

Summary
Given a set of syllables, decide whether the three input phrases can each be split into syllables so their syllable counts are 5, 7, and 5.
Level

Medium6 of 10

Topics
Dynamic programming, String, Hash map, Trie
Solved
No attempts yet

Problem

A haiku is a Japanese form of poetry. It consists of three phrases of 55, 77 and 55 syllables each.

Once a year, HiQ has a haiku contest, where employees submit their best poems. The poems are then judged on a wide range of aspects, such as

  • creativity
  • simplicity
  • beauty
  • whether the poem is actually a haiku

This last point turned out to be quite a challenge for the judges. Many problems arose when half the judges indexed syllables starting at 00 and the other half at 11.

Can you help the judges determine whether a submitted poem is a haiku, given a set of syllables? Note that there may exist multiple decompositions of a single word in the poem into syllables. In this case, you should determine whether some decomposition is a haiku.

Input

The first line of input contains a single integer 1≤S≤1001 \le S \le 100, the number of syllables. The next line contains SS words separated by spaces (the syllables). Each syllable contains at most 77 lowercase letters a-z.

Then, three lines containing the poem follow. Each line contains a (non-empty) list of words separated by spaces, representing a phrase. The words contain only lowercase letters a-z. The length of each line is at most 100100 characters (including spaces).

It is guaranteed that there exists at least one decomposition of the poem into the given syllables.

Output

Output "haiku" if the given poem is a haiku, and "come back next year" otherwise (without the quotes).

Examples3

  1. Example 1

    Input
    20
va
fi
ve
mor
lling
spe
in
i
sh
ti
hard
cov
ear
fe
red
ja
ry
need
ly
ning
spelling very hard
early in morning tired
i need covfefe
    Expected output
    haiku

  2. Example 2

    Input
    22
q
c
da
plus
to
the
e
thee
un
late
ci
a
shall
by
com
i
ru
pare
temp
ble
hi
de
shall i compare thee
to a c plus plus template
undecidable
    Expected output
    haiku

  3. Example 3

    Input
    19
ju
win
soft
it
east
sun
and
light
der
the
is
through
li
but
yon
what
breaks
et
dow
but soft what light through
yonder window breaks it is
the east and juliet is the sun
    Expected output
    come back next year