TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

60.0% (6/10)

Submission's AC Ratio

11.8% (24/203)

Tags

Description

貝塔是一個有雄心壯志的人,他苦苦鑽研各類演算法,終於在公元 20XX 年 Y 月 Z 日通過了「天下第一資料結構挑戰大賽」的重重難關,獲得「十萬序列王」的稱號,號稱通曉各類樹形結構、鍊形結構、持久化結構與各種離線法則,無所不能!

貝塔獲得這個稱號之後,變得十分狂傲,因此號稱「數論女王」的?皮決定挫挫他的銳氣,而向貝塔發出了挑戰。

?皮決定用「線性同餘」的方式產生一條長度為 N 的序列 D0N1,並叫貝塔依照非遞減順序排好序。但是因為排序出來的數字太多了,?皮也沒有耐心看完,而且?皮通曉傳說中的「真-?皮.轉 EX」神功,所以他只需要檢查排序結果的最前面、最中間和最後面各 K 個數字,就可以知道貝塔到底有沒有真正做出來。

?皮知道貝塔對線性同餘毫不知情,為了使貝塔無法找到藉口逃避挑戰,索性把線性同餘的計算式公開:
Di+1=(Di×A+B) % Mx % y 代表 x÷y 的餘數。

貝塔欣然接受了挑戰。然而他很快就發現,?皮所要求的序列長度實在太長了,他用了各種不同的方式,卻一次次地TLEMLE。此時這題的時限和記憶體限制居然開始慢慢減少!眼看著題目愈來愈困難,走投無路的貝塔只好求助於你。

現在你有一堆?皮給的 N,A,B,M,D0K。你能不能算出?皮所指定的數字,幫助貝塔獲得AC呢?

Input Format

本題有多筆測資。第一行有一個正整數 T,代表測資的筆數。
接下來 T 行,每題有六個非負整數,依序代表 N,A,B,M,D0K

對於 1% 的測資,A=0
對於 2% 的測資,KN90001M1.5×104
對於 20% 的測資,KN1.5×1051M1.5×106
對於 20% 的測資,1K3
對於所有的測資,T6KN9×1061K40001M1.5×107A,B,D0<MNK(mod2)

Output Format

請對每筆測資輸出三行,每行有以空白分隔的 K 個數字,分別代表最小、最中間、最大的 K 個數字。
(假設排完序的序列是S0N1,則第一行是S0K1,第二行是SNK2N+K21,第三行是SNKN1。)

順帶一提,TIOJ 是不會判斷行尾空白的。

Sample Input 1

2
12 13 21 60 7 2
15000 2331 3292 6534 7 8

Sample Output 1

7 7
22 37
52 52
7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7

Hints

如果你想知道的話,TIOJ不是Big-Endian喔。

Problem Source

Problem set / Description by Yihda Yol

Subtasks

No. Testdata Range Score
1 0 1
2 1 2
3 2~3 20
4 4~5 20
5 6~8 57

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 32768 262144 1
1 1000 32768 262144 2
2 1000 32768 262144 3
3 1000 32768 262144 3
4 8000 32768 262144 4
5 8000 32768 262144 4
6 8000 32768 262144 5
7 8000 32768 262144 5
8 8000 32768 262144 5