На поле несчастного фермера Билла постоянно садятся летающие тарелки, оставляя после себя следы в виде выжженных кругов. Билл очень правильный американский фермер, и потому каждый такой круг он обносит квадратной полиэтиленовой оградой с надписью "Attention - UFO terrorism!", которую рекомендует ставить правительство страны. Если же ограды для двух кругов пересекаются или касаются (хотя бы и углами), то Билл огораживает такие круги одним объемлющим прямоугольником (пример см. ниже).
Все бы ничего. Но у зловредных инопланетян из широко известной игры X-COM скоро день дурака, на который одна из эскадр летающих тарелок, располагающая N тарелками радиуса Ri (i =1..N), решила зло подшутить над честным фермером. А именно: так прожечь его территорию, чтобы в огороженную Биллом зону попало все поле. Требуется определить: возможно ли осуществить этот коварный замысел, если за ночь дурака одна тарелка может прожечь лишь один круг.
Входные данные:
В первой строке содержатся целые числа H и V (0<H,V<=1000000) - размеры поля по горизонтали и вертикали соответственно. Во второй строке расположено число тарелок 0<N<=1000.
В третьей строке подряд записаны N радиусов летающих тарелок: целые числа 0<Ri<=30000.
Выходные данные:
Выходной файл должен содержать одно число: 1, если возможно так прожечь поле тарелками, что после огораживания все поле попадет в запретную зону. Или 0 в противном случае.
Примеры входа и выхода
INPUT OUTPUT
10 10 0
1
4
INPUT OUTPUT
10 10 1
4
6 6 6 6
|
