← 返回题目列表

Codeforces · 385/E

E. 熊在田野里

中文机器翻译题面 查看原题

我们的熊森林里有一片格子田。方格字段是一个n×n的表,行从上到下编号为1到n,列从左到右编号为1到n。让我们用记录 (x, y) 表示 x 行和 y 列交叉处的字段单元格。田地的每个单元格都包含正在生长的覆盆子,因此田地的单元格 (x, y) 包含 x + y 个覆盆子灌木丛。

熊出来走过田野。在步行开始时,他的速度是(dx,dy)。那么熊在场上正好呆了 t 秒。每一秒都会发生以下事件:

- 假设当前熊位于单元格 (x, y) 中。
- 首先,熊吃掉了当前牢房中所有灌木丛中的覆盆子。熊吃掉 k 个灌木丛中的覆盆子后,他的速度的每个分量都会增加 k。换句话说,如果在吃掉 k 丛覆盆子之前他的速度是 (dx, dy),那么吃完浆果之后他的速度就等于 (dx + k, dy + k)。
- 让我们表示熊的当前速度 (dx, dy)(在上一步之后增加)。然后熊从单元格 (x, y) 移动到单元格 (((x + dx - 1) mod n) + 1, ((y + dy - 1) mod n) + 1)。
- 然后田地的每个单元格中都会长出一棵额外的覆盆子灌木。

你的任务是预测熊的行为。如果他从单元格 (sx, sy) 开始,找到他最终所在的单元格。假设每个灌木丛都有无限多的覆盆子,而熊永远不会吃完它。

输入

输入的第一行包含六个空格分隔的整数:n、sx、sy、dx、dy、t (1 ≤ n ≤ 109;1 ≤ sx,sy ≤ n;- 100 ≤ dx,dy ≤ 100;0 ≤ t ≤ 1018)。

输出

打印两个整数 — t 秒后熊最终到达的单元格的坐标。

示例

输入 #1

5 1 2 0 1 2

输出 #1

3 1

输入 #2

1 1 1 -1 -1 2

输出 #2

1 1

注意

运算 a mod b 表示取 a 除以 b 后的余数。请注意,运算结果始终为非负数。例如,( - 1) mod 3 = 2。

在第一次移动之前的第一个样本中,速度向量将等于 (3,4) 并且熊将到达单元格 (4,1)。在第二次移动之前,速度矢量将等于 (9,10),并且熊将到达单元格 (3,1)。不要忘记,在第二步时,浆果丛的数量增加了 1 个。

在第一次移动之前的第二个样本中,速度矢量将等于 (1,1) 并且熊将到达单元格 (1,1)。在第二次移动之前,速度矢量将等于 (4,4),熊将到达单元格 (1,1)。不要忘记,在第二步时,浆果丛的数量增加了 1 个。