eolymp
Competitions

XIII Всеукраинская олимпиада по информатике, Киев, Март 27 - Апрель 1, 2000

Виртуляндия

В стране Виртуляндии очень популярна следующая головоломка. Таблица состоит из M + 1 -й строчки. Первые M строк зеленые, а последняя, M + 1 -я, строка - синяя. Каждая строчка состоит из N чисел, каждое из которых - целое число из диапазона 0..P-1 включительно. Возможное действие при решении головоломки - прибавить зеленую строку к синей покомпонентно, при этом каждое число в синей строке, большее P - 1, уменьшается на P. Головоломка считается решенной, если синяя строчка состоит только из нулей.

Напишите программу, решающую описанную головоломку.

Входные данные

Первая строка содержит количество тестов. Первая строка каждого теста содержит числа P, N, M (1 N, M 100, 2 P 255). Следующие M строк содержат по N чисел - зеленые строчки. Следующая строка из N чисел - синяя строчка.

Выходные данные

Ответ на каждый тест следует вывести в отдельной строке. Ответ - это число 0, если не удалось решить головоломку. Если же головоломку решить удалось, то ответ - число 1 и в этой же строке N чисел - для каждой зеленой строчки сколько раз ее нужно прибавить к синей.

Time limit 1 second
Memory limit 64 MiB
Input example #1
2
4 2 2
2 2
2 2
3 3
3 2 4
1 0
2 0
0 0
0 1
2 1
Output example #1
0
1 1 0 0 2 
Source 2000 XIII All-Ukrainian Informatics Olympiad, Kiev, March 27 - April 1, Round 2