Задача U. Автостоянка на улице Кантора

Автор:В. Степанец, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Автостоянка, находящаяся поблизости от улицы имени Г. Кантора, ограничена с севера и запада домами, а с востока и юга открыта в большое поле.

Чтобы упорядочить размещение автомобилей, владелец стоянки решил пронумеровать места на ней и выделить каждому клиенту номер и соответствующее место. Нумерацию решено производить так: месту в углу стоянки присвоен номер ноль, далее нумерация идёт по диагоналям в направлении с северо-востока на юго-запад.

013610
24711
5812
913
14

Координаты каждого места на стоянке определяются числами (x; y), где x — количество мест, расположенных западнее данного, y — количество мест, расположенных севернее. Например, место номер 7 имеет координаты (2; 1).

Требуется написать программу, которая для каждого из N данных номеров мест определит их координаты.

Рекомендуется рассмотреть частичные решения

N = 1

C ≤ 106

Формат входного файла

Входной файла содержит число N, за которым следуют N целых чисел Ci — номера мест.

Формат выходного файла

Выходной файл должен содержать N пар чисел xi yi — координаты мест, соответствующие номерам во входном файле.

Ограничения

1 ≤ N ≤ 105

0 ≤ Ci ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
1 0
2
2
20101204
226
6106 234
4 16

0.079s 0.017s 13