Специальный терминал, разработанный в лаборатории, где работает Дима, представляет собой горизонтальный прямоугольник, состоящий из 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\)).

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

Васин жесткий диск состоит из \(M\) секторов. Вася последовательно устанавливал на него различные операционные системы следующим методом: он создавал новый раздел диска из последовательных секторов, начиная с сектора номер \(a_i\) и до сектора \(b_i\) включительно, и устанавливал на него очередную систему. При этом если очередной раздел хотя бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее созданный раздел «затирается», и операционная система, которая на него была установлена, больше не может быть загружена.

Напишите программу, которая по информации о том, какие разделы на диске создавал Вася, определит, сколько в итоге работающих операционных систем установлено и в настоящий момент работает на Васином компьютере.

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

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

Инженер Джио проводит испытания новых сверхскоростных поездов. Поскольку поезда экспериментальные, у них не должно возникать трудностей при проезде через промежуточные города. Поэтому инженер Джио требует, чтобы ни в каком городе на пути поезда, кроме, может быть, начального и конечного, не было развилок. Точнее, из любого промежуточного города на пути поезда должны выходить либо ровно две дороги, ведущие в другие города (возможно, в один и тот же), либо ровно одна дорога, начинающаяся и заканчивающаяся в этом городе.

Естественно, что Джио желает испытать поезд на максимальной возможной скорости, и поэтому после каждого изменения в системе путей он хочет знать максимальную длину пути, по которому может ехать поезд. Поскольку в доисторические времена не умели добывать железо, в начале никаких дорог между городами нет.