006 - 霧明けの鮫島

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 3 /


TLE
1sec
MLE
64MB
得点
100

問題

あなたは漂流した。手元には漂流した島 $(x,y)$ の周辺の地図がある。
地図は縦 $h$、横 $w$ の大きさで、$n$ 個の×印 $(a,b)$ がある。
そこには凶暴な鮫がいて、通ろうとすると鮫に襲われるため、そこは通らないことにした。
斜めに通ればいいじゃないか!と言うだろうが下手したら数匹の鮫に襲われるので、東西南北にしか動かないことにした。
本来なら鮫のヒレが見えるのでそこを通らなくても済むのだが、霧が深くて何も見えないため、地図を頼りにするしかない。
地図の外には鮫がいない(らしい)ので、島の位置が与えられたときに地図の外までいけるかを判断することにした。
尚、体力に関しては気にしないこととする。

入力

$w$ $h$ $x$ $y$
$n$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_n$ $b_n$

出力

地図の外にいけるなら alive、いけないなら give up と出力せよ。出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • $3 \leq h,w \leq 500$
  • $1 \leq n \leq h \times w$
  • $1 \leq x,a \leq w$
  • $1 \leq y,b \leq h$

入出力例

入力例1

3 3 2 2
5
1 1
3 3
2 3
2 1
3 1

出力例1

alive

解説

図に表すとこうなる。
###
.s.
.##
このとき、地図の外に出ることができるので、 alive と出力する。

入力例2

5 5 3 3
8
2 2
2 3
2 4
3 2
3 4
4 2
4 3
4 4

出力例2

give up

解説

.....
.###.
.#s#.
.###.
.....
無理ですね。