/ 
Time Limit: 1.5 sec / Memory Limit: 1024 MB
配点: 7 点
問題文
2 次元座標平面とみなせる大空に、N 機の飛行機が航行しています。
i=1,2, \cdots ,N に対し、 i 番目の飛行機は時刻 0 において座標 (AX_i,AY_i) に存在しました。
飛行機はいずれも向き 1,2,3,4,5,6,7,8 のいずれかを向いて航行しています。
時刻 t において座標 (x,y) に存在する向き d の飛行機は、 時刻 t+1 において
- d=1 ならば座標 (x+1,y) に
- d=2 ならば座標 (x+1,y+1) に
- d=3 ならば座標 (x,y+1) に
- d=4 ならば座標 (x-1,y+1) に
- d=5 ならば座標 (x-1,y) に
- d=6 ならば座標 (x-1,y-1) に
- d=7 ならば座標 (x,y-1) に
- d=8 ならば座標 (x+1,y-1) に
存在します。
また、航行の途中で飛行機が向きを変えることはありません。
あなたは管制官の高橋くんから次のような報告を受けました。
時刻 T において、座標 (BX_1,BY_1),(BX_2,BY_2), \cdots ,(BX_N,BY_N) に飛行機が存在した
彼の報告に矛盾しないような N 機の飛行機の向きの組み合わせが存在するかを判定し、存在する場合は一例を出力してください。
制約
- 1 \leq N \leq 20000
- 1 \leq T \leq 10^9
- 0 \leq AX_i,AY_i,BX_i,BY_i \leq 10^9
- i \ne j ならば (AX_i,AY_i) \ne (AX_j,AY_j)
- i \ne j ならば (BX_i,BY_i) \ne (BX_j,BY_j)
- 入力はすべて整数
小課題・得点
この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。
- (1 点)：N \leq 6
- (1 点)：AY_i=0, BY_i=0
- (2 点)：N \leq 1000
- (3 点)：追加の制約はない。
入力
入力は以下の形式で標準入力から与えられます。
N T AX_1 AY_1 AX_2 AY_2 \vdots AX_N AY_N BX_1 BY_1 BX_2 BY_2 \vdots BX_N BY_N
出力
高橋くんの報告に矛盾しない向きの組み合わせが存在しない場合、No と出力してください。
存在する場合、以下の形式で 1, 2, \cdots, N 番目の飛行機の向きを空白区切りで出力してください。ただし、D_i は飛行機 i の向きとします。
Yes D_1 D_2 D_3 \cdots D_N
入力例 1
3 2 3 3 5 5 9 2 11 2 5 5 3 3
出力例 1
Yes 2 6 1
時刻 T において、1 番目の飛行機は座標 (BX_2,BY_2) に、2 番目の飛行機は座標 (BX_3,BY_3) に、3 番目の飛行機は座標 (BX_1,BY_1) に存在します。
入力例 2
3 2 3 3 5 5 9 2 11 1000000000 5 5 3 3
出力例 2
No
高橋くんの報告に矛盾しない向きの組み合わせは存在しません。
入力例 3
20 774 540130346 269080121 139837096 165633078 731188937 784167460 18996195 52176517 153153670 738204723 179733158 825294112 698198250 713974773 449248931 563096572 249863070 242694893 428066819 476630383 554127636 460973490 389988495 32320086 889782910 956212985 43905938 212030305 638141790 667879166 985957895 358743012 971007109 827787244 804625543 141347414 905270323 167192824 614855582 963943648 179733932 825294886 731188163 784166686 153154444 738205497 554128410 460973490 804626317 141348188 449249705 563096572 540129572 269079347 638142564 667878392 614855582 963944422 18996969 52177291 971007109 827788018 889782910 956213759 43906712 212031079 389987721 32319312 139836322 165633078 428067593 476631157 905271097 167192824 249862296 242694893 985958669 358742238 698199024 713975547
出力例 3
Yes 6 5 6 2 2 2 2 1 5 2 1 6 3 2 8 8 3 2 1 3