問題
雛ちゃんです。かわいいです。
雛ちゃんは厄を集めたので、おうちに帰ろうとしています。
例によって、謎の機械に追突したので、何個かの直線状の壁が出現しました。
更に雛ちゃんの現在位置とおうちの場所も変化してしまいました。
雛ちゃんが現在位置からおうちに帰れるかを判定するプログラムを作成してください。
入出力形式
入力形式
一行目に、雛ちゃんがいる土地の縦の長さと横の長さ、
直線状の壁の数と質問の数 h , w , n , q が与えられる。
土地の座標は左上から [0][0] ~ [h-1][w-1] で表される。
次の n行に渡り、出現した壁の始点と終点のxy座標
ws_x , ws_y , wg_x , wg_y が空白区切りで与えられる。
この入力は、xを横、yを縦とし、(ws_x,ws_y) から (wg_x,wg_y) まで壁が出現していることを示す。
出現した壁は、必ず土地の縦もしくは横に平行である。
壁が斜めに出現しているデータが与えられることはない。
次の q行に渡り、雛ちゃんの現在位置とおうちのxy座標
sx , sy , gx , gy が空白区切りで与えられる。
この入力は、xを横、yを縦とし、(sx,sy) が雛ちゃんのxy座標、
(gx,gy) がおうちのxy座標を示す。
h w n q ws_x1 ws_y1 wg_x1 wg_y1 ws_x2 ws_y2 wg_x2 wg_y2 .. .. ws_xn ws_yn wg_xn wg_yn sx1 sy1 gx1 gy1 sx2 sy2 gx2 gy2 .. .. sxq syq syq gyq
出力形式
(sx , sy , gx , gy) の入力毎に、
雛ちゃんがおうちに辿り着けるなら、"Success" を、
辿り着けない場合は、"Broadcasting accident" を出力せよ。
制約
- 1 ≦ h,w ≦ 1000000
- 0 ≦ n ≦ 300
- 0 ≦ q ≦ 1000000
部分点
小課題1
(1 ≦ h,w ≦ 100) , (0 ≦ q ≦ 10) を満たすテストケースに正解すると、
配点の10% が与えられる。
小課題2
(0 ≦ q ≦ 10) を満たすテストケースに正解すると、
配点の50% が与えられる。
入出力例
入力例
20 20 4 5 5 0 5 14 14 5 14 19 5 5 19 5 0 14 14 14 0 0 3 3 3 4 9 9 15 6 19 19 19 19 19 19 5 5 5 5
出力例
Success Broadcasting accident Success Success Broadcasting accident
上の入力例では、土地の情報は以下のようになる。
.....#.............. .....#.............. .....#.............. .....#.............. .....#.............. .....############### .....#........#..... .....#........#..... .....#........#..... .....#........#..... .....#........#..... .....#........#..... .....#........#..... .....#........#..... ###############..... ..............#..... ..............#..... ..............#..... ..............#..... ..............#.....