#P9567. [SDCPC 2023] Puzzle: Sashigane

[SDCPC 2023] Puzzle: Sashigane

Description

给定一个 nnnn 列的网格,网格中包含恰好一个黑色方格,其余方格均为白色。令 (i,j)(i, j) 表示位于第 ii 行第 jj 列的格子,这个黑色方格位于 (bi,bj)(b_i, b_j)

您需要用若干 L 形覆盖所有白色格子,使得每个白色格子都恰好被一个 L 形所覆盖,同时唯一的黑色方格不能被任何 L 形覆盖。L 形不能超过网格的边界。

更正式地,网格中的一个 L 形由四个整数 (r,c,h,w)(r, c, h, w) 唯一确定,其中 (r,c)(r, c) 确定了 L 形的转折点,hhww 确定了 L 形两臂的方向和长度。四个整数满足 1r,cn1 \le r, c \le n1r+hn1 \le r + h \le n1c+wn1 \le c + w \le nh0h \ne 0w0w \ne 0

  • h<0h < 0,则所有满足 r+hirr + h \le i \le r 的格子 (i,c)(i, c) 均属于该 L 形;否则若 h>0h > 0,则所有满足 rir+hr \le i \le r + h 的格子 (i,c)(i, c) 均属于该 L 形。
  • w<0w < 0,则所有满足 c+wjcc + w \le j \le c 的格子 (r,j)(r, j) 均属于该 L 形;否则若 w>0w > 0,则所有满足 cjc+wc \le j \le c + w 的格子 (r,j)(r, j) 均属于该 L 形。

下图展示了几种 L 形。

Input Format

每个测试文件仅有一组测试数据。

第一行输入三个整数 nnbib_ibjb_j1n1031 \le n \le 10^31bi,bjn1 \le b_i, b_j \le n)表示网格的大小以及黑色格子的位置。

Output Format

如果存在符合要求的覆盖方案,首先输出一行 Yes,接下来在第二行输出一个整数 kk0kn2130 \leq k \leq \frac{n^2-1}{3})表示覆盖白色格子的 L 形数量。接下来输出 kk 行,第 ii 行输出四个由单个空格分隔的整数 rir_icic_ihih_iwiw_i,表示第 ii 个 L 形由 (ri,ci,hi,wi)(r_i, c_i, h_i, w_i) 唯一确定。如果有多种合法答案,您可以输出任意一种。

如果不存在符合要求的覆盖方案,仅需要输出一行 No

【样例解释】

第一组样例数据展示如下。

5 3 4

Yes
6
5 1 -1 3
1 2 1 3
3 1 -2 1
4 3 -1 -1
4 5 1 -1
2 5 1 -2

1 1 1

Yes
0