Специальный терминал, разработанный в лаборатории, где работает Дима, представляет собой горизонтальный прямоугольник, состоящий из m×n ячеек, каждая из которых может содержать произвольное целое число. Ячейки занумерованы парами чисел, левая верхняя ячейка имеет номер (1, 1), правая нижняя – (\(m\), \(n\)).

Специальное устройство ввода, сконструированное специально для этого терминала, позволяет отправлять терминалу две команды: \(A\)(\(r\), \(c\), \(d\), \(v\)) и \(B\)(\(r_1\), \(c_1\), \(r_2\), \(c_2\), \(d\), \(v\)).

Рассмотрим сначала команду \(A\). Параметры \(r\) и \(c\) изменяются в пределах от 1 до \(m\) и от 1 до \(n\) соответственно и указывают, к какой ячейке применяется команда. Параметр \(d\) может принимать значение из множества {\(L\), \(R\), \(U\), \(D\)} и задает направление, в котором применяется команда: влево, вправо, вверх или вниз соответственно. Параметр \(v\) представляет собой целое неотрицательное число. В результате выполнения команды значения во всех ячейках, находящихся в направлении \(d\) от ячейки (\(r\), \(c\)), включая эту ячейку, увеличиваются на \(v\).

Например, если терминал имеет размер 5×4, то после выполнения команды \(A\)(3, 2, \(R\), 3) значения в ячейках (3, 2), (3, 3) и (3, 4) увеличатся на 3, а после команды \(A\)(2, 1, \(U\), 2) значения в ячейках (2, 1) и (1, 1) увеличатся на 2.

Рассмотрим теперь команду \(B\). Первые четыре ее параметра являются целыми числами и удовлетворяют условиям 1\( \le\) \(r_1\) \(\le\) \(r_2\) \(\le\) \(m\) и 1\( \le\) \(c_1\) \(\le\) \(c_2\) \(\le\) \(n\). Параметры \(d\) и \(v\) могут принимать те же значения, что и соответствующие параметры команды \(A\). Команда \(B\) выполняется следующим образом: для всех пар (\(r\), \(c\)), таких, что \(r_1\) \(\le\) \(r\) \(\le\) \(r_2\) и \(c_1\) \(\le\) \(c\) \(\le\) \(c_2\) выполняется команда \(A\)(\(r\), \(c\), \(d\), \(v\)).

Исходно все ячейки терминала содержат нули. Выведите содержимое терминала после выполнения заданной последовательности команд.

Сергей работает системным администратором в очень крупной компании. Естественно, в круг его обязанностей входит резервное копирование информации, хранящейся на различных серверах и «откат» к предыдущей версии в случае возникновения проблем.

В данный момент Сергей борется с проблемой недостатка места для хранения информации для восстановления. Он решил перенести часть информации на новые сервера. К сожалению, если что-то случится во время переноса, он не сможет произвести откат, поэтому процедура переноса должна быть тщательно спланирована.

На данный момент у Сергея хранятся \(n\) точек восстановления различных серверов, пронумерованных от 1 до \(n\). Точка восстановления с номером \(i\) позволяет произвести откат для сервера \(a_i\). Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами \(l, l + 1, \ldots, r\) для некоторых \(l\) и \(r\).

Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного \(l\), при каком минимальном \(r\) в процессе переноса будут доступны точки восстановления не менее чем \(k\) различных серверов.

Помогите Сергею.