Марися любить розв’язувати східні кросворди. Так називається головоломка, в якій потрібно зафарбувати деякі клітинки прямокутника N * M таким чином, щоб на кожній з N вертикалей і на кожній з M горизонталей кількість зафарбованих клітинок дорівнювала деякому наперед визначеному записаному на полях для даної вертикалі чи горизонталі числу. На жаль, інколи укладачі кросвордів помиляються, і кросворд розв’язку не має. Дівчина не хотіла б марнувати свій час, розв’язуючи такі кросворди.
Завдання
Напишіть програму, яка для заданих величин N та M, а також N +M чисел, записаних на полях кросворда, визначить, чи є даний кросворд розв’язним.
У першому рядку вхідного файла записано число 1 ≤ T ≤ 5, — кількість кросвордів для перевірки. Кожен кросворд подається трьома рядками: в першому рядку записано натуральні числа M та N, що не перевищують 10^5, — ширину та висоту кросворда; у другому рядку подано N цілих невід’ємних чисел — кількість зафарбованих клітинок на першій, другій, ...,N -й вертикалях відповідно; у третьому рядку подано M цілих невід’ємних чисел — кількість зафарбованих клітинок на першій, другій, ..., M -й горизонталях відповідно. Жодне з чисел у другому і третьому рядках не перевищує загальної кількості клітинок на відповідній вертикалі чи горизонталі.
Вихідний файл повинен містити відповідь для кожного з кросвордів в окремому рядку: 1, якщо кросворд розв’язний, або 0, якщо ні. Відповіді потрібно подати в тому ж порядку, в якому у вхідному файлі подано самі кросворди.
Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови:
1. 15 % балів: жоден з розмірів (ні ширина, ні висота) жодного з кросвордів не перевищує 5.
2. 35 % балів: жоден з розмірів жодного з кросвордів не перевищує 1000, причому хоча б один з розмірів хоча б одного з кросвордів більший за 5.
50 % балів: хоча б один з розмірів хоча б одного з кросвордів більший за 1000.
Пояснення. У першому випадку кросворд має, наприклад, таке розв’язання:
У другому випадку кросворд нерозв’язний: з одного боку, рядок з п’ятірок свідчить, що всі вертикалі повністю зафарбовано; з іншого боку, рядок з нулів означає, що жодна з горизонталей не містить жодної зафарбованої клітинки. Такого, очевидно, бути не може.