TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

66.7% (8/12)

Submission's AC Ratio

32.7% (17/52)

Description

有一天,一個叫做Prak Nibar的人想要用Rabin fingerprint來對字串做雜湊。

你應該已經要知道Rabin fingerprint是甚麼了,因為培訓有講過。如果你沒參加培訓,可以看以下的定義:
對於一個字串$A=a_0a_1a_2\cdots a_{N-1}$,其Rabin fingerprint $f(A)$定義為:
$\displaystyle f(A)=\sum_{i=0}^ {N-1}g(a_i)p^ {N-i-1} \mod M$
其中$p, M\in\mathbb{N}; gcd(p, M)=1$,$g : \Sigma\rightarrow\mathbb{N}\cap[0,p)$是單射函數且$\Sigma$是字串$A$的字元集。

然而,因為Nibar覺得模運算常數太大了,所以他想要用位元運算解決一切:只取結果的後$m$個位元不就是模$2^ m$嗎!
雖然他人品沒有很好,但是他知道M取愈大結果會愈好,而他不滿足於現有的資料結構,因此自己實作了一個$m$位元的整數結構。

你對雜湊函數有深刻的了解,所以知道這其實超乎人品之外,但是你必須要說服Nibar。
所以你得構造兩個相異且由小寫英文字母組成的字串,使得不管他選取什麼樣的$p$(當然要符合$gcd(p, M)=1$),這兩個字串的雜湊值永遠相同。

保證他使用的$g(c)$一定會把英文字母按照順序對應到連續的正整數上。(也就是說,如果$g(^ \backprime a')=k$,那麼$g(^ \backprime b')=k+1$,以此類推。)

Input Format

輸入只有一個正整數$m\leq 256$,代表Nibar所使用的$M=2^ m$。

子任務(測資) 額外限制 分數
1 (0~2) $m \leq 4$ 17
2 (0~5) $m \leq 15$ 31
3 (0~8) 無限制 52

Output Format

輸出兩行相異的字串,每行一個字串,代表這兩個字串不管選取什麼$p$,在模$M$之下雜湊值永遠相同。
保證一定存在這樣的字串,且如果$m<=32$,長度不超過$10^ 5$;其它情況長度不超過$10^ 7$。

如果你輸出了超過上述保證長度的字串,你會得到一個WA。

Sample Input

3

Sample Output

cb
cj

Hints

Problem Source

Problem set / Description by Yihda Yol
建國中學105學年度校內第二次模擬賽 pE

Subtasks

For Testdata: 0 ~ 2, Score: 17
For Testdata: 0 ~ 5, Score: 31
For Testdata: 0 ~ 8, Score: 52
No. Time Limit (ms) Memory Limit (KiB)
0 500 65536
1 500 65536
2 500 65536
3 500 65536
4 500 65536
5 500 65536
6 500 65536
7 500 65536
8 500 65536