AT_kupc2024_c Cake-Cutting Ceremony

今日は、双子の $ K $ 君と $ U $ 君の誕生日です。 $ 2 $ 人のために、 $ xy $ 平面上の $ 0 \le x, y \le N $ で表される領域に各辺の長さが $ N $ の正方形の形をした誕生日ケーキが用意してあります。 $ 1 \le i,j \le N $ をみたす整数 $ i,j $ について、 $ c_{i,j} $ は平面上の $ i-1 \le x \le i $ かつ $ j-1 \le y \le j $ で表される領域に何のクリームが塗られているかを表しています。 - $ c_{i,j} = $ `c` のとき、その領域にはチョコレートクリームが塗られている。 - $ c_{i,j} = $ `s` のとき、その領域にはストロベリークリームが塗られている。 - $ c_{i,j} = $ `.` のとき、その領域にはバタークリームが塗られている。 今からこのケーキを $ 2 $ つに切り、それぞれ $ K $ 君と $ U $ 君に渡す必要があるのですが、 $ 2 $ 人ともチョコレートクリームとストロベリークリームに目が無いので、 $ 2 $ つに分けられたケーキに含まれるチョコレートクリームとストロベリークリームの面積が一方でも異なっていると満足してくれません(バタークリームの面積は気にしません)。 あなたの仕事は、ケーキをある $ 1 $ 本の直線に沿って切り、 $ 2 $ 人を満足させることです。そのような切り方が存在する場合は切るべき直線とケーキの輪郭の **$ 2 $ 交点**の座標を、存在しない場合はその旨を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ c_{1,1} $ $ c_{1,2} $ $ \cdots $ $ c_{1,N} $ $ c_{2,1} $ $ c_{2,2} $ $ \cdots $ $ c_{2,N} $ $ \vdots $ $ c_{N,1} $ $ c_{N,2} $ $ \cdots $ $ c_{N,N} $

$ 2 $ 人を満足させられるような切り方が存在する場合は、切るべき直線とケーキの輪郭の $ 2 $ 交点の座標 $ (x_1, y_1) $ 及び $ (x_2, y_2) $ を次の形式で出力せよ。存在しない場合は `No` を出力せよ。 > Yes $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ 出力に従ってケーキを切った際の、ケーキの一方を $ P $ 、もう一方を $ Q $ とし、 $ P $ に含まれるチョコレートクリームの面積を $ P_c $ 、ストロベリークリームの面積を $ P_s $ 、 $ Q $ に含まれるチョコレートクリームの面積を $ Q_c $ 、ストロベリークリームの面積を $ Q_s $ とするとき、 $ |P_c - Q_c| \le 10^{-3} $ かつ $ |P_s - Q_s| \le 10^{-3} $ であれば正答と判定される。

### 部分点 以下の制約を満たすデータセットに正解した場合は $ 1 $ 点が与えられる。 - $ N $ は $ 1 \le N \le 105 $ を満たす整数 - $ c_{i,j} $ は `c`、`s` のいずれか ### Constraints - $ N $ は $ 1 \le N \le 2025 $ を満たす整数 - $ c_{i,j} $ は `c`、`s`、`.` のいずれか - $ c_{i,j} = $ `c` または $ c_{i,j} = $ `s` をみたす $ (i,j) $ が少なくとも $ 1 $ 組存在する