TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

幼稚國的計算機中心最近發生了一個大麻煩...

起因是有一個幼稚鬼在電腦中心灌起了熱門的線上遊戲 World of Warcraft - Wrath of the Lich King(以下簡稱 WotLK),大家就開始在計算機中心裡面打起了電動。因為 WotLK 實在是太好玩了,於是這群幼稚鬼幾乎每天都不停的玩,一
天 25 小時裡面大部分的時間幾乎都在電腦主機面前。而由於 WotLK 實在太好
玩了,這群幼稚鬼甚至組成了一個幼稚鬼公會,在英明的幼稚會長睿智的領導
下,帶領這群幼稚鬼們日益茁壯。

在 WotLK 裡面,有一個遊戲要素 : 團隊 RAID,RAID 通常由公會內的 25
人組成,由 Raid Leader (RL)帶領下,率眾攻入地下城副本,在大家的齊心協力
與幼稚的 RL 英明的領導下,擊敗地下城最後的頭目,順便洗劫地下城頭目的
寶物(疑?)。

每次出 Raid 的時候總是會發生很多幼稚的事情,有過獵人耍帥拿刀衝到第
一線拼命砍,有牧師拿個火焰魔仗丟火球裝成法師,更可憐的是有個法師自從某
次輸給那位牧師之後受到衝擊太大,現在只會製作魔法麵包當廚師....

很不幸的是,公會裡面恰好有26 個幼稚鬼,並不是每個幼稚鬼都可以參加
RAID,所以不管怎樣都得會有一個幼稚鬼沒辦法跟著一起出團,於是英明的 RL
幾乎每個星期都在為要讓哪些幼稚鬼可以一起出團而傷透了腦筋。英明的 RL
於是把幼稚公會內的所有幼稚鬼從 1 到 25 都編上了編號(不含 RL,因為他是英
明的 RL),先從 2 開始,讓所有編號是 2 的倍數的幼稚鬼先全部加入 Raid,再
讓所有編號是 3 的倍數的幼稚鬼加入,接著再讓編號是 4 的倍數的幼稚鬼加入,
以此類推,直到隊伍裡面有25個人為止,剩下最後一位沒加入的幼稚鬼只好站
在地下城門口幫大家做麵包。

看到這裡,編號 1 號的幼稚鬼發現不對了,大叫說: 『不對吧!這樣不就每次
都是我要站在門口!!!!!』

這真的是太幼稚了............

由於這群幼稚鬼每天都在計算機中心裡面吵吵鬧鬧,計算機中心的幼稚管理
員不高興了,於是在網路上請了一群會最寫程式的人幫忙寫了一隻病毒,想要讓
計算機中心裡面的電腦再也打不了電動。

所以幼稚國的計算機中心最近發生了一個大麻煩...他們中毒了( ̄▽ ̄#)﹏﹏

這個病毒的傳染力遠遠超出了計算機中心幼稚管理員的想像,他每秒都會不
斷的在每一台電腦之間移動,並且每次從一台主機跳到另外一台主機上的時候,
都會更改程式內部的識別碼,所以計算機中心的幼稚管理員不知道如何去抓到這
支病毒。

現在,計算機中心幼稚管理員再次把這個問題放到了網路上面,想請這群最
會寫程式的人來幫他想辦法,計算出病毒到底藏身再哪一台電腦。

Input Format

第一行有一個數字 k , 1 <= k <= 10 代表共有 k 筆測資


每筆測資第一行有四個整數 N , M , D , T


1 <= N<= 60000 代表計算機中心共有 N台主機,編號從 0 ~ N-1
0 <= M < N 代表這隻病毒第零秒時藏在編號 M 的主機中
0 <= D <=100000 代表這隻病毒第零秒時的識別碼
0 <= T <= 2,000,000,000 代表最後的時間

假設病毒在第 t 秒的時候在編號為 m的主機,識別碼是 d,則第 t+1秒的時候病毒會跳到編號 (d mod N)的電腦,並把識別碼改為 (d + 2m + (d mod N))

Output Format

每筆測資輸出一行,每行有兩個整數 M P
代表 T秒過後病毒在編號 M 的電腦識別碼是 D

P = D mod N

Sample Input 1

3 
5 1 2 10 
8322 1787 21690 956606923 
36293 30135 2735 422800487 

Sample Output 1

2 0 
5874 6100 
4942 28648 

Hints

Problem Source

Migrated from old NTUJ.

NPSC預賽

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 200