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=a0a1a2aN1,其Rabin fingerprint f(A)定義為:
f(A)=i=0N1g(ai)pNi1modM
其中p,MN;gcd(p,M)=1g:ΣN[0,p)是單射函數且Σ是字串A的字元集。

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

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

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

Input Format

輸入只有一個正整數m256,代表Nibar所使用的M=2m

子任務(測資) 額外限制 分數
1 (0~2) m4 17
2 (0~5) m15 31
3 (0~8) 無限制 52

Output Format

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

如果你輸出了超過上述保證長度的字串,你會得到一個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