Lester is imprisoned for the purpose of this problem. He can write letters to Sunny, but he will encode a secret message inside that cannot be read by the prison staff. He will hide each character of his secret message in a word. He told Sunny to decipher his message in the following way:
Let $P_i$ be the $i$-th prime number. For the $i$-th word in the letter, let $W_i$ be its length. Take the $(P_i \mod W_i)$-th character (0-indexed) of the word and append it to the secret message.
Sunny has just received a new letter from Letser. Help him decipher the secret message.
Input
The first line of input contains an integer $N$, the number of words in the secret message.
The second line of input contains $N$ words, which is the content of Lester's letter.
Each word consists of at most 100 lowercase English letters.
Output
Output Lester's secret mesage.
Constraints
Subtask 1 (40%): $1 \le N \le 10^3$
Subtask 2 (60%): $1 \le N \le 4 \times 10^5$
Sample Test Cases
| Input | Output | |
|---|---|---|
| 5 most thoughts man since monotonicity |
sunny | |
| The first 5 prime numbers are $2, 3, 5, 7, 11$. With 0-indexing, The $(2 \mod 4)$-th letter of "most" is "s". The $(3 \mod 8)$-th letter of "thoughts" is "u". The $(5 \mod 3)$-th letter of "man" is "n". The $(7 \mod 5)$-th letter of "since" is "n". The $(11 \mod 12)$-th letter of "monotonicity" is "y". |
||
Scoring: Per Subtask
Authored by s16f22
Appeared in 2022 Mini Contest 3 (Pre-HKOI Junior)