В лесу, в котором проживает наш медведь, есть клетчатое поле. Клетчатое поле представляет собой квадратную таблицу 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). Считайте, что на каждом кусте бесконечно много малины, и медведь никогда не сможет съесть ее всю.
Выходные данные
Выведите два целых числа — координаты клетки, в которой окажется медведь через t секунд.
Примечание
Операция a mod b обозначает взятие остатка от деления числа a на число b. Обратите внимание, что результат этой операции всегда не отрицательное число. Например, ( - 1) mod 3 = 2.
В первом примере перед первым ходом вектор скорости станет равным (3,4) и медведь окажется в клетке (4,1). Перед вторым ходом вектор скорости станет равным (9,10) и медведь окажется в клетке (3,1). Не забывайте, что на втором ходу количество кустов малины стало на единицу больше.
Во втором примере перед первым ходом вектор скорости станет равным (1,1) и медведь окажется в клетке (1,1). Перед вторым ходом вектор скорости станет равным (4,4) и медведь окажется в клетке (1,1). Не забывайте, что на втором ходу количество кустов малины стало на единицу больше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1 2 0 1 2
|
3 1
|
|
2
|
1 1 1 -1 -1 2
|
1 1
|