User's AC Ratio

50.0% (4/8)

Submission's AC Ratio

25.1% (46/183)

Tags

Description

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

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

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

?皮知道貝塔對線性同餘毫不知情,為了使貝塔無法找到藉口逃避挑戰,索性把線性同餘的計算式公開:
$D_{i+1}=(D_i \times A+B)\ \%\ M $ , $ x\ \%\ y $ 代表 $ x \div y $ 的餘數。

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

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

Input Format

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

對於1%的測資,$A=0$。
對於2%的測資,$K\leq N\leq 9000$,$1\leq M\leq 1.5\times 10^ 4$。
對於20%的測資,$K\leq N\leq 1.5\times 10^ 5$,$1\leq M\leq 1.5\times 10^ 6$。
對於20%的測資,$1\leq K\leq 3$。
對於所有的測資,$T\leq 6$, $K\leq N\leq 9\times 10^ 6$, $1\leq K\leq 4000$, $1\leq M\leq 1.5\times 10^ 7$, $A, B, D_0<M$, $N\equiv K \pmod {2}$。

Output Format

請對每筆測資輸出三行,每行有以空白分隔的K個數字,分別代表最小、最中間、最大的K個數字。
(假設排完序的序列是$S_{0 \ldots N-1}$,則第一行是$S_{0 \ldots K-1}$,第二行是$S_{\frac{N-K}{2} \ldots \frac{N+K}{2}-1}$,第三行是$S_{N-K \ldots N-1}$。)

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

Sample Input

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

Sample Output

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

For Testdata: 0 ~ 0, Score: 1
For Testdata: 1 ~ 1, Score: 2
For Testdata: 2 ~ 3, Score: 20
For Testdata: 4 ~ 5, Score: 20
For Testdata: 6 ~ 8, Score: 57
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 32768 262144
1 1000 32768 262144
2 1000 32768 262144
3 1000 32768 262144
4 8000 32768 262144
5 8000 32768 262144
6 8000 32768 262144
7 8000 32768 262144
8 8000 32768 262144