На координатній площині задано прямокутник, висота якого \textbf{h}, а ширина \textbf{w}. Всередині прямокутника задано відрізки, паралельні осям координат і з кінцями, які мають цілочисельні координати. Прямокутник планується розрізати на декілька частин горизонтальними або вертикальними розрізами. За один крок дозволяється розрізати на дві не порожні прямокутні частини лише один з наявних на цьому кроці прямокутників. При цьому забороняється при розрізі перетинати довільний з заданих відрізків. Потрібно написати програму, яка дозволить знайти кількість способів розрізання заданого прямокутника на \textbf{k }частин вертикальними і горизонтальними розрізами. Способи, які відрізняються порядком проведення розрізів, вважаються різними. \InputFile Перший рядок містить розміри прямокутника - цілі числа \textbf{h} та \textbf{w}\textit{ }(\textbf{1 }≤ \textbf{h}, \textbf{w }≤ \textbf{8}). Другий рядок містить кількість частин \textbf{k}, на які потрібно розрізати прямокутник (\textbf{1} ≤ \textbf{k }≤ \textbf{hw}). Третій рядок містить кількість \textbf{cnt }(\textbf{0 }≤ \textbf{cnt }≤ \textbf{10}) заданих всередині прямокутника відрізків. Наступні \textbf{cnt }рядків містять опис цих відрізків, тобто, кажен рядок містить чотири цілих числа \textbf{x_1}, \textbf{y_1}, \textbf{x_2}, \textbf{y_2} (\textbf{0 }≤ \textbf{x_1}\textit{ ≤ }\textbf{x_2} ≤ \textbf{w}, \textbf{0 }≤ \textbf{y_1} ≤ \textbf{y_2} ≤ \textbf{h}) - координати кінців відрізка. \OutputFile Вивести шукану кількість способів розрізання заданого прямокутника. Відповідь вивести за модулем \textbf{2^30}.