TopCoder

User's AC Ratio

70.6% (12/17)

Submission's AC Ratio

49.5% (46/93)

Tags

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 1

3

Sample Output 1

cb
cj

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0~2 17
2 0~5 31
3 0~8 52

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 500 65536 262144 1 2 3
1 500 65536 262144 1 2 3
2 500 65536 262144 1 2 3
3 500 65536 262144 2 3
4 500 65536 262144 2 3
5 500 65536 262144 2 3
6 500 65536 262144 3
7 500 65536 262144 3
8 500 65536 262144 3