Восточный кроссворд

Мария увлекается решением японских кроссвордов. Это головоломка, в которой необходимо закрасить некоторые клетки в прямоугольнике размером 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.

3. 50 % баллов: хотя бы один из размеров хотя бы одного из кроссвордов больше 1000.

Объяснение. В первом случае кроссворд имеет, например, такое решение:

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