Задача B. Чёрно-белый поворот

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

Условие

Чёрно-белое изображение состоит из h строк по w пикселей. Каджый пиксель имеет значение 0 или 1. С целью экономии памяти изображение было сжато следующим образом: для каждой строки сначала записывается значение первого пикселя, затем длины цепочек подряд идущих нулей и единиц. Например, строка 00100001110 будет закодирована последовательностью 0, 2, 1, 4, 3, 1.

Данное сжатое чёрно-белое изображение требуется повернуть на 90 градусов по часовой стрелке, и вывести, используя тот же метод сжатия.

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

Входной файл содержит числа w h, за которыми следует последовательность чисел, описывающая исходное изображение.

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

Выходной файл должен содержать последовательность чисел, описывающую повёрнутое изображение.

Ограничения

w, h ≥ 1, w × h ≤ 108, гарантируется, как исходное, так и повёрнутое изображение содержат в сжатом виде не более 106 чисел.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
1 3
1 1 1 1
0 2 1
0 1 2
0 2 1
1 3
2
2 4
1 2  1 2  0 2  0 2
0 2 2
0 2 2

0.135s 0.021s 15