Dr.Su 带着 5 位参赛选手到北京去参加蓝桥杯了，他们一行人因为日常没有经费所以只能坐绿皮车硬卧。在火车上没有信号实在太无聊了，于是 HT 决定和 WZM 玩密码接龙游戏。他们选择了两个整数 a 和 b，写出一个序列 x 使得 x[i]=(x[i-1] \times a+b) \ \% \ 10001，并相互接龙下去。

正玩到兴起之时，作为参赛选手中唯一一位脱团狗的 WZM 接到了来自女朋友的夺命连环 call，于是 WZM 拜托 LXY 帮他先玩一会就秀恩爱去了（一会肯定是假的，跟女朋友通电话至少一小时）。HT 为了刁难 LXY，打算不把 a 和 b 的值告诉 LXY，并且把 WZM 刚才写下的全部擦掉了，只留下自己写的。LXY 作为 OEIS 大师，对这种推数列的题不屑一顾，于是丢给了你，让你把被擦掉的密文全部复原。HT 骑虎难下，于是偷偷暗示你 0≤a,b≤6000。

第一行一个正整数 t \ (2≤t≤100)，表示当前数列的长度为 t。

接下来有 t 行，每行一个正整数，表示 HT 写的第 i 个密码。

输出 t 行，每行一个正整数，表示 WZM 本来可能的序列。

可能有多种结果，只输出 a 较小的情况下的序列。

样例中，有 a=1096,b=1096，使得：

• (17 \times 1096+1096) \ \% \ 10001=9727
• (9727 \times 1096+1096) \ \% \ 10001=822
• (822 \times 1096+1096) \ \% \ 10001=1918
• (1918 \times 1096+1096) \ \% \ 10001=3014
• (3014*1096+1096) \ \% \ 10001=4110

且此时 a 与 b 在所有可行解中最小。