009 - Re:百人一首

時間制限 2 秒 / メモリ制限 128 MB / 得点 100 / x 6 /


TLE
2sec
MLE
128MB
得点
100

問題

人狼ゲームをしよう!!!
山本君は友人を誘って計 $N$ 人で人狼ゲームを行うことにした。
しかし、普通に行うと時間がかかるので、本来のルールを少しだけいじることにした。
その名も「ワンデイ人狼」。名前の通り、$1$ 日で勝敗を決める人狼ゲームである。
以下、このゲームの内容について示す。

  • $N$ 人のプレイヤーをそれぞれプレイヤー $i$ $(1 \leq i \leq N)$ とする。
  • $N$ 人のプレイヤーには、それぞれ疑惑度という値が定められており、始めは全員 $0$ である。
  • 各プレイヤーの役割を決定する。役割は人狼役と村人役の $2$ つが存在する。
    以下、人狼役のプレイヤーを人狼、村人役のプレイヤーを村人と表記する。
    人狼は $W$ 人おり、プレイヤー $w_i$ $(1 \leq i \leq W)$ を人狼とする。それ以外のプレイヤーは村人である。
  • 話し合いが $M$ 回行われる。
    $i$ $(1 \leq i \leq M)$ 回目の話し合いでは、プレイヤー $p_i$ の疑惑度が以下のように変化する。
    $i$ 回目の話し合いが行われる直前のプレイヤー $p_i$ の疑惑度を $x$ とする。
    • $x + s_i \lt 0$ であるとき、$0$ に変化する。
    • $0 \leq x + s_i \leq 100$ であるとき、$x + s_i$ に変化する。
    • $100 \lt x + s_i$ であるとき、$100$ に変化する。
  • $M$ 回の話し合いが行われた後、疑惑度が高い順に $K$ 人のプレイヤーを処刑する。
    なお、疑惑度が同じプレイヤーがいる場合、「最後に疑惑度が変化した話し合い」の行われた時刻が早いプレイヤーから順に処刑するものとする。
  • 人狼を全員処刑することができれば村人の勝ち、できなければ人狼の勝ちである。

人狼と村人のどちらが勝ち、どちらが負けるかを求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$ $W$
$w_1$ $\ldots$ $w_W$
$p_1$ $s_1$
$\vdots$
$p_M$ $s_M$

出力

村人の勝ちならば human win、人狼の勝ちならば wolf win を出力せよ。
出力の最後に改行を入れること。

制約

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

  • $2 \leq N \leq 100$
  • $1 \leq W \leq K \leq N$
  • $N \leq M \leq 10^5$
  • $1 \leq w_i \leq N$
  • $w_i \neq w_j$ $(i \neq j)$
  • $1 \leq p_i \leq N$
  • $-100 \leq s_i \leq 100$
  • どのプレイヤーも必ず一回以上疑惑度が変化する
  • 入力はすべて整数

入出力例

入力例1

3 3 1 1
3
2 30
1 10
3 50

出力例1

human win

$3$ 回の話し合いが行われた後の各プレイヤーの疑惑度は、プレイヤー $1$ から順に $10, 30, 50$ である。
$K = 1$ より、疑惑度が最も高いプレイヤー $1$ 名が処刑される。
最も高い疑惑度は $50$ であり、疑惑度が $50$ である唯一のプレイヤー $3$ が処刑される。
プレイヤー $3$ は人狼であり、人狼を全員処刑できたので、村人の勝利となる。


入力例2

3 3 1 1
3
3 10
2 10
1 30

出力例2

wolf win

入力例3

3 3 1 1
3
3 100
2 100
1 100

出力例3

human win

$3$ 回の話し合いが行われた後の各プレイヤーの疑惑度は、プレイヤー $1$ から順に $100, 100, 100$ である。
$K = 1$ より、疑惑度が最も高いプレイヤー $1$ 名が処刑される。
プレイヤー全員の疑惑度が同じであるため、最初に疑惑度が $100$ に変化したプレイヤー $3$ が処刑される。
プレイヤー $3$ は人狼であり、人狼を全員処刑できたので、村人の勝利となる。