Задачи
Східний кросворд
Східний кросворд
Марися любить розв’язувати східні кросворди. Так називається головоломка, в якій потрібно зафарбувати деякі клітинки прямокутника \textit{N * M} таким чином, щоб на кожній з \textit{N} вертикалей і на кожній з \textit{M} горизонталей кількість зафарбованих клітинок дорівнювала деякому наперед визначеному записаному на полях для даної вертикалі чи горизонталі числу. На жаль, інколи укладачі кросвордів помиляються, і кросворд розв’язку не має. Дівчина не хотіла б марнувати свій час, розв’язуючи такі кросворди.
\textbf{Завдання}
Напишіть програму, яка для заданих величин \textit{N} та \textit{M}, а також \textit{N +M} чисел, записаних на полях кросворда, визначить, чи є даний кросворд розв’язним.
\InputFile
У першому рядку вхідного файла записано число\textit{\textbf{ 1 ≤ T ≤ 5,}} --- кількість кросвордів для перевірки. Кожен кросворд подається трьома рядками: в першому рядку записано натуральні числа \textit{M} та \textit{N}, що не перевищують 10^5, --- ширину та висоту кросворда; у другому рядку подано \textit{N} цілих невід’ємних чисел --- кількість зафарбованих клітинок на першій, другій, ...,\textit{N} -й вертикалях відповідно; у третьому рядку подано M цілих невід’ємних чисел --- кількість зафарбованих клітинок на першій, другій, ..., \textit{M} -й горизонталях відповідно. Жодне з чисел у другому і третьому рядках не перевищує загальної кількості клітинок на відповідній вертикалі чи горизонталі.
\OutputFile
Вихідний файл повинен містити відповідь для кожного з кросвордів в окремому рядку: 1, якщо кросворд розв’язний, або 0, якщо ні. Відповіді потрібно подати в тому ж порядку, в якому у вхідному файлі подано самі кросворди.
\Scoring
Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови:
1. 15 \% балів: жоден з розмірів (ні ширина, ні висота) жодного з кросвордів не перевищує 5.
2. 35 \% балів: жоден з розмірів жодного з кросвордів не перевищує 1000, причому хоча б один з розмірів хоча б одного з кросвордів більший за 5.
50 \% балів: хоча б один з розмірів хоча б одного з кросвордів більший за 1000.
\textbf{Пояснення. }У першому випадку кросворд має, наприклад, таке розв’язання:
\includegraphics{https://static.e-olymp.com/content/3e/3e6102b5772bcb6a711414882ecdf5fe760ab967.png}
У другому випадку кросворд нерозв’язний: з одного боку, рядок з п’ятірок свідчить, що всі вертикалі повністю зафарбовано; з іншого боку, рядок з нулів означає, що жодна з горизонталей не містить жодної зафарбованої клітинки. Такого, очевидно, бути не може.
Входные данные #1
2 3 2 1 2 1 2 2 4 5 5 5 5 5 0 0 0 0 0
Выходные данные #1
1 0