Under construction

Still being built. Things may change

K-Words Problem

Time limit3sMemory limit1024 MB

Summary
Given sentences, merge each 'Korea' with the word after it or the word before 'of' into a K-word by the stated rules, then print the result.
Level

Medium4 of 10

Topics
String, Simulation
Solved
No attempts yet

Problem

Artichoke is taking the elective 'Programming Language Theory through Korean Culture'.

Last week Artichoke wrote a 5 0005\,000-word report on 'The Influence of Aheui on Korean Culture' for an assignment. This week the assignment is to write a short summary of that report.

This semester Artichoke is taking seven major courses, so there is no time to write the summary by hand. Artichoke decided to write a program that summarizes the report using the rules below.

  1. If the word 'Korea' appears in the report, merge it with the word that follows it into a 'K-word'. (ex. Korea language → K-Language)

    • The word 'Korea' is case-sensitive.
    • If the first letter of the word after 'Korea' is lowercase, change it to uppercase.
    • If this rule can be applied several times in a row, apply it from the back.
    • If the word 'Korea' is followed by punctuation, this rule cannot be applied.

  2. If the word 'Korea' appears immediately after the word 'of', merge it with the word immediately before 'of' into a K-word. (ex. Language of Korea → K-Language)

    • The words 'of' and 'Korea' are case-sensitive.
    • If the first letter of the word before 'of' is lowercase, change it to uppercase.
    • If this rule can be applied several times in a row, apply it from the front.
    • If the word 'of' is followed by punctuation, this rule cannot be applied.
    • If there is no word before 'of', or the word immediately before 'of' has punctuation, this rule cannot be applied.
    • If 'Korea' is followed by punctuation, move that punctuation to the end of the word immediately before 'of'.

  3. If rule 1 and rule 2 can both be applied in the same sentence, apply rule 2 first.

Input

The first line contains the number of sentences NN (1≤N≤5 0001 \le N \le 5\,000).

Each of the next NN lines contains one sentence made of uppercase and lowercase English letters and the punctuation marks ! ? , and . .

Each sentence has one or more words, and each word has at least one letter.

Each word is at most 50 characters long, and the total number of words in the input does not exceed 5,000.

Words are separated by a single space, and sentences are separated by newlines.

Punctuation appears only at the end of a word, and each word has at most one punctuation mark. A period appears only at the end of the last word of a sentence and nowhere else.

Output

Print NN lines, each containing the summarized report according to the rules above.

Examples1

  1. Example 1

    Input
    7
Artichoke in Korea Army uses Aheui.
Aheui, the best language of Korea.
Korea is our country.
of Korea? Korea Korea Aheui of Korea.
Language of, Korea Korea.
Aheui has shown the greatness of Korea of Korea.
korea Korea! koRea Of Korea of Korea oF kORea.
    Expected output
    Artichoke in K-Army uses Aheui.
Aheui, the best K-Language.
K-Is our country.
of Korea? K-K-K-Aheui.
Language of, K-Korea.
Aheui has shown the K-K-Greatness.
korea Korea! koRea Of K-Korea oF kORea.