E. Хаалтууд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нүд бүр нь боломжит хоёр "(" эсвэл ")" хаалтыг агуулсан хоёр хэмжээст массивыг хаалтын массив гэнэ. Замын дурын дараалласан хоёр нүд нь хөрш талтай ба замын нүд бүр өмнөх нүднийхээ доор эсвэл баруун талд байрласан байх хоёр хэмжээст массиваар явсан замыг уйтгартай зам гэнэ.

Хэрвээ $n × m$ хэмжээтэй хоёр хэмжээст массивын $(1, 1)$ нүднээс $(n, m)$ нүдрүү очих ямар нэг уйтгартай зам нь зөв хаалтын дараалал үүсгэж байвал уг массивыг зөв хаалтын массив гэнэ.

Ижил хэмжээтэй хоёр зөв зөв хаалтын массивыг ($a$ ба $b$) харьцуулах үйлдлийг тодорхойлцгооё. $1$-c $nm$ хүртэлх ялгаатай бүхэл тоонуудыг агуулсан ижил хэмжээтэй массив буюу давуу эрхийн ($c$) массивыг авч үзье. Хоёр хэмжээст массив дахь $a_{i, j} ≠ b_{i, j}$ байх $(i, j)$ байрлалыг олцгооё. Хэрвээ ийм хэд хэдэн байрлал байвал $c_{i, j}$ тоо хамгийн бага байх нэгийг нь сонгоё. Хэрвээ $a_{i, j}$ = "$($" байвал $a < b$ бусад тохиолдолд $a > b$. Хэрвээ $(i, j)$ байрлал олдохгүй бол массивууд тэнцүүд тооцогдоно.

Таны ажил бол $k$-р хоёр хэмжээст зөв хаалтын массивыг олох юм. Өгөгдсөн $n$ ба $m$ хэмжээсүүдийн хувьд $k$-с бага тооны зөв хаалтын массив байхгүй.

Оролт

Эхний мөрөнд бүхэл тоон утгууд $n$, $m$ ба $k$ байх буюу массивийн хэмжээсүүд болон хайж буй зөв хаалтын массивийн дугаар юм ($1 ≤ n, m ≤ 100$, $1 ≤ k ≤ 10^{18}$). Тэгээд давуу эрхийн массив өгөгдөнө, тус бүрдээ $m$ тоо агуулсан $n$ мөр байх ба $p_{i, j}$ тоо нь $i$-р мөрийн $j$-р тэмдэгтийн давуу эрхийг харуулах ба бүх $p_{i, j}$ тоонууд ялгаатай $1 ≤ p_{i, j} ≤ nm$.

C++ хэлэнд 64 битийн бүхэл тоонуудыг унших болон бичихдээ %lld тодорхойлогчийг битгий ашиглаарай. Харин үүний оронд cin, cout урсгалууд эсвэл %I64d тодорхойлогчийг ашиглаарай.

Гаралт

$k$-р хоёр хэмжээст зөв хаалтын массивыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
1 2 1
1 2
Гаралт
()
Оролт
2 3 1
1 2 3
4 5 6
Гаралт
(()
())
Оролт
3 2 2
3 6
1 4
2 5
Гаралт
()
)(
()

Тэмдэглэл

Эхний жишээн дээр зөвхөн нэг зөв хоёр хэмжээст хаалтын массив оршин байна.

Хоёр болон гурав дахь жишээн дээр хоёр массив оршин байна.

Хэрвээ хаалтын дараалал дээр «$+$» ба «$1$» тэмдэгтүүдийг нэмээд зөв арифметик илэрхийлэл гарган авч болж байвал уг дарааллыг ердийн гэнэ. Жишээлбэл «$(())()$», «$()$» ба «$(()(()))$» дарааллууд нь ердийн байхад «$)($», «$(()$» ба «$(()))($» дарааллууд нь биш юм.

Сэтгэгдлүүдийг ачааллаж байна...