아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Rhyme

시간 제한2초메모리 제한1024 MB

요약
서로 다른 n개의 단어가 주어질 때, 두 쌍의 단어가 같은 모음 수를 가지며 각 쌍의 두 단어가 운율을 이루도록 하는 두 순서쌍을 출력하고, 불가능하면 Impossible을 출력한다.
난이도

보통10점 중 6점

유형
해시맵, 그리디, 문자열
정답자
아직 제출이 없습니다

문제

Dr. Sokolov is getting ready to introduce a new type of poetry --- sokku. A sokku poem consists of two lines. The words of each line should have exactly ss vowels in total. The lines should end with different words, which rhyme with each other.

To keep things simple, Sokolov considers two words to rhyme if their endings, starting from the last vowel, are the same. For example, pairs of words <<cat>> and <<rat>>, <<kitty>> and <<dizzy>>, <<string>> and <<sing>> do rhyme, whereas <<book>> and <<click>>, <<beast>> and <<cats>>, <<milk>> and <<bulk>> don't.

In order to prove his ideas, Sokolov decided to write а collection of sokku. For each sokku he has already created a list of words he is ready to include into it. He doesn't require sokku to contain all words of the list, but he doesn't allow other words in his sokku.

However he fails at creating sokku themselves. Your task is to help him.

입력

First line of the input file contains nn --- the number of words selected by Dr. Sokolov (0≤n≤100,0000 \le n \le 100\\,000) and kk --- the number of vowels each line should contain (1≤s≤100,0001 \le s \le 100\\,000).

Each of the following nn lines contains one word, consisting of lowercase English letters.

The length of each word does not exceed 3030 characters. Each word contains at least one vowel. Letters Dr. Sokolov considers to be vowels are <<a>>, <<e>>, <<i>>, <<o>>, <<u>> and <<y>>. There are no equal words.

출력

Output the desired sokku or <<Impossible>> in case of no solution. If there are multiple solutions, output any of them. Adhere to the format from the sample test.

예제2

  1. 예제 1

    입력
    7 6
    my
    food
    is
    tasty
    cat
    looks
    happy
    
    예상 출력
    cat food is tasty
    my cat looks happy
    
  2. 예제 2

    입력
    2 2
    bad
    case
    
    예상 출력
    Impossible