eolymp
bolt
Try our new interface for solving problems
Problems

Покупки Степана

Покупки Степана

Time limit 0.5 seconds
Memory limit 64 MiB

Рутенія - чудова країна. В країні дуже цікава грошова система! У них в ходу золоті, срібні та бронзові монети, звані відповідно галеони, сиклі, і кнати. Один галеон містить сімнадцять сиклів, а один сикль - двадцять дев'ять кнатів. Всі грошові дані (ціни, готівка) формулюються в галеонах, сиклях і кнатах, причому кількість сиклів не перевищує 16, а кількість кнатів - 28.

У Степана сьогодні свято - він отримав першу стипендію. Однак святкувати зарано - вступникам треба купити абсолютно необхідні для навчання речі: студентський рюкзак, будильник, подушку ...

Скільки грошей виявиться у Степана після усіх покупок?

Input data

Перший рядок містить кількість грошей, отриманих Степаном (три числа - кількість галеонів, сиклів і кнатів, записані через пропуски. Нагадаємо, що кількість сиклів не перевищує 16, а кількість кнатів - 28).

У другому рядку записано число N (0 ≤ N ≤ 100000) – кількість предметів, які необхідно купити. Далі йдуть N рядків з цінами кожного предмета (в такому ж форматі, що й перший рядок). Кожен куплений предмет коштує не менше одного кната.

Обмеження на дані: кількість галеонів в кожному з рядків не перевищує 100 000.

Output data

Єдиний рядок має містити інформацію про кількість грошей, що залишилися у Степана після здійснення всіх покупок (в такому ж форматі, що й перший рядок вхідних даних). Якщо грошей не вистачить, виведіть число -1.

Examples

Input example #1
5 16 10
2
3 9 21
0 4 0
Output example #1
2 2 18
Source ACM-ICPC Ukraine 2014, Перший етап, 26 квітня 2014 року