C. Баланс
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Имеется система из n сосудов с водой, некоторые пары которых соединены трубками с клапанами и механизмами для переливания. Через трубки, соединяющие сосуды, можно переливать целое число литров из одного сосуда в другой (в любом направлении). Два сосуда могут быть соединены более чем одной трубкой. Общее количество трубок равно e. Объемы всех сосудов одинаковы и равны v, и объем воды в сосудах, разумеется, не должен превышать объема сосуда в процессе переливаний.

Известны начальные объемы ai воды в сосудах и объемы bi, которые требуется получить. Найдите последовательность переливаний, которая выполняет эту задачу. Число переливаний не должно превышать 2·n2.

Входные данные

Первая строка содержит целые числа n, v, e (1 ≤ n ≤ 300, 1 ≤ v ≤ 109, 0 ≤ e ≤ 50000).

Следующие две строки содержат по n неотрицательных целых чисел каждая — изначальные ai и требуемые объемы bi соответствующих сосудов (0 ≤ ai, bi ≤ v).

В следующих e строках содержится описание всех трубок в формате x y (1 ≤ x, y ≤ n, x ≠ y) для трубки, соединяющей сосуды с номерами x и y. Два сосуда могут быть соединены более чем одной трубкой. Считайте, что сосуды пронумерованы некоторым образом от 1 до n.

Выходные данные

Выведите «NO» (без кавычек), если такой последовательности переливаний не существует.

Иначе выведите любую подходящую последовательность переливаний в следующем формате. В первой строчке выведите число переливаний k (k не должно превышать 2·n2). В последующих строчках выведите переливания по одному на строке в формате x y d (переливание d литров из сосуда номер x в сосуд номер y, x и y должны быть различны). Для всех операций число d должно быть целым неотрицательным.

Примеры
Входные данные
2 10 1
1 9
5 5
1 2
Выходные данные
1
2 1 4
Входные данные
2 10 0
5 2
4 2
Выходные данные
NO
Входные данные
2 10 0
4 2
4 2
Выходные данные
0