Lục bát poem

View as PDF

Submit solution

Points: 0.80 (partial)
Time limit: 3.0s
Memory limit: 1G
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Lục bát is a Vietnamese form of poem. As its Sino-Vietnamese namesake implies, a pair of lines in this poem contains one six-syllable line, and one eight-syllable line, rhyming with each other. A lục bát poem consists of many pairs of lines following said rule, without limits on the number of lines. Lục bát poem is a very popular form of poem in Vietnam, due to having simple rules, but is very easy to reminiscent in one's memory.

Specifically, in this problem, we define a lục bát poem as follow:

  • The poem has ~2 \cdot n~ lines, in which ~n~ of the lines are six-syllable, and ~n~ of the lines are eight-syllable.

  • The six-syllable lines will be in positions 1, 3, 5, ~\ldots~

  • The eight-syllable lines will be in positions 2, 4, 6, ~\ldots~

  • Each line's last syllable must rhyme with the sixth syllable of its following line.

  • Two lines are considered to rhyme with each other if the multiset of vowels (the letters a, e, i, ou) of those two words are the same.

You are given ~n~ six-syllable lines and ~n~ eight-syllable lines, arrange these lines into a lục bát poem.

Input

The first line contains a single integer ~n~ (~1 \le n \le 10^5~), denoting the number of six-syllable lines and eight-syllable lines.

The ~i~-th line out of the next ~n~ lines each contain ~6~ words belonging to a six-syllable line.

The ~i~-th line out of the next ~n~ lines each contain ~8~ words belonging to a eight-syllable line.

Each word consists of only lowercase latin letters. The sum of length of all words do not exceed ~10^7~.

Output

If it is impossible to arrange these ~2n~ lines into a single poem following the rule, output NO.

Otherwise, output YES on the first line. On the following ~2n~ lines, output the poem.

Scoring

  • Subtask 1 (~10~ points): ~n \le 6~.

  • Subtask 2 (~90~ points): No additional constraints

The total score for this problem is ~100~.

Sample Input 1

2
nhi vang bong trang la xanh
trong dam gi dep bang sen
gan bun ma chang hoi tanh mui bun
la xanh bong trang lai chen nhi vang

Sample Output 1

YES
trong dam gi dep bang sen 
la xanh bong trang lai chen nhi vang 
nhi vang bong trang la xanh 
gan bun ma chang hoi tanh mui bun

Sample Input 2

3
trai qua mot cuoc be dau
la gi bi sac tu phong
tram nam trong coi nguoi ta
troi xanh quen thoi ma hong danh ghen
chu tai chu menh kheo la ghet nhau
nhung dieu trong thay ma dau don long

Sample Output 2

YES
tram nam trong coi nguoi ta 
chu tai chu menh kheo la ghet nhau 
trai qua mot cuoc be dau 
nhung dieu trong thay ma dau don long 
la gi bi sac tu phong 
troi xanh quen thoi ma hong danh ghen

Comments

Please read the guidelines before commenting.


There are no comments at the moment.