D. Big Brush

problem_index: D

time_limit: 3 seconds

memory_limit: 256 megabytes

note:
In the first test case, the solution is not unique. Here's one of them:
![image](images/cf_1638_D/1.png)
In the second test case, there is no way one could obtain the given painting, thus the answer is $$$-1$$$.

solutions: ["from __future__ import division, print_function\r\nfrom collections import defaultdict\r\nimport math\r\nimport sys\r\nimport os\r\nfrom io import BytesIO, IOBase\r\nfrom collections import deque, Counter, OrderedDict, defaultdict\r\nimport heapq\r\n# ceil,floor,log,sqrt,factorial,pow,pi,gcd\r\nimport bisect\r\nfrom bisect import bisect_left,bisect_right\r\n\r\nBUFSIZE = 8192\r\n\r\n\r\nclass FastIO(IOBase):\r\n\tnewlines = 0\r\n\r\n\tdef __init__(self, file):\r\n\t\tself._fd = file.fileno()\r\n\t\tself.buffer = BytesIO()\r\n\t\tself.writable = \"x\" in file.mode or \"r\" not in file.mode\r\n\t\tself.write = self.buffer.write if self.writable else None\r\n\r\n\tdef read(self):\r\n\t\twhile True:\r\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n\t\t\tif not b:\r\n\t\t\t\tbreak\r\n\t\t\tptr = self.buffer.tell()\r\n\t\t\tself.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n\t\tself.newlines = 0\r\n\t\treturn self.buffer.read()\r\n\r\n\tdef readline(self):\r\n\t\twhile self.newlines == 0:\r\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n\t\t\tself.newlines = b.count(b\"\\n\") + (not b)\r\n\t\t\tptr = self.buffer.tell()\r\n\t\t\tself.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n\t\tself.newlines -= 1\r\n\t\treturn self.buffer.readline()\r\n\r\n\tdef flush(self):\r\n\t\tif self.writable:\r\n\t\t\tos.write(self._fd, self.buffer.getvalue())\r\n\t\t\tself.buffer.truncate(0), self.buffer.seek(0)\r\n\r\n\r\nclass IOWrapper(IOBase):\r\n\tdef __init__(self, file):\r\n\t\tself.buffer = FastIO(file)\r\n\t\tself.flush = self.buffer.flush\r\n\t\tself.writable = self.buffer.writable\r\n\t\tself.write = lambda s: self.buffer.write(s.encode(\"ascii\"))\r\n\t\tself.read = lambda: self.buffer.read().decode(\"ascii\")\r\n\t\tself.readline = lambda: self.buffer.readline().decode(\"ascii\")\r\n\r\n\r\ndef print(*args, **kwargs):\r\n\t\"\"\"Prints the values to a stream, or to sys.stdout by default.\"\"\"\r\n\tsep, file = kwargs.pop(\"sep\", \" \"), kwargs.pop(\"file\", sys.stdout)\r\n\tat_start = True\r\n\tfor x in args:\r\n\t\tif not at_start:\r\n\t\t\tfile.write(sep)\r\n\t\tfile.write(str(x))\r\n\t\tat_start = False\r\n\tfile.write(kwargs.pop(\"end\", \"\\n\"))\r\n\tif kwargs.pop(\"flush\", False):\r\n\t\tfile.flush()\r\n\r\n\r\nif sys.version_info[0] < 3:\r\n\tsys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)\r\nelse:\r\n\tsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\r\n\r\ninput = lambda: sys.stdin.readline().rstrip(\"\\r\\n\")\r\n\r\ndef inp():\r\n    return(int(input()))\r\ndef inps():\r\n    return input().strip()\r\ndef inlt():\r\n    return(list(map(int,input().split())))\r\ndef insr():\r\n    s = input().strip()\r\n    return(list(s[:len(s)]))\r\ndef invr():\r\n    return(map(int,input().split()))\r\n\r\nfrom types import GeneratorType\r\ndef bootstrap(f,stack=[]):\r\n\tdef wrappedfunc(*args,**kwargs):\r\n\t\tto=f(*args,**kwargs)\r\n\t\tif stack:\r\n\t\t\treturn to\r\n\t\telse:\r\n\t\t\twhile True:\r\n\t\t\t\tif type(to) is GeneratorType:\r\n\t\t\t\t\tstack.append(to)\r\n\t\t\t\t\tto=next(to)\r\n\t\t\t\telse:\r\n\t\t\t\t\tstack.pop()\r\n\t\t\t\t\tif not stack:\r\n\t\t\t\t\t\tbreak\r\n\t\t\t\t\tto=stack[-1].send(to)\r\n\t\t\treturn to\r\n\treturn wrappedfunc\r\n\r\ndef opr(i,j):\r\n    for dx1,dy1 in dir:\r\n        l[i+dx1][j+dy1]=0\r\n\r\ndef check(i,j):\r\n\tif vis[i][j]:\r\n\t\treturn 0\r\n\ts=0\r\n\tif i>=0 and j>=0 and i<n-1 and j<m-1:\r\n\t\tfor dx1,dy1 in dir:\r\n\t\t\tif l[i+dx1][j+dy1] and not s:\r\n\t\t\t\ts=l[i+dx1][j+dy1]\r\n\t\t\telif l[i+dx1][j+dy1] and s!=l[i+dx1][j+dy1]:\r\n\t\t\t\treturn 0\r\n\t\t# return s\r\n\treturn s\r\n\r\n\r\ndx=[1,1,0,0]\r\ndy=[0,1,0,1]\r\ndir=[[dx[i],dy[i]] for i in range(4)]\r\nn,m=invr()\r\nl=[]\r\nfor i in range(n):\r\n    l.append(inlt())\r\nvis=[[0]*m for j in range(n)]\r\nd=deque([])\r\nfor i in range(n-1):\r\n    for j in range(m-1):\r\n        c=l[i][j]\r\n        flg=1\r\n        for k in range(4):\r\n            if l[i+dx[k]][j+dy[k]]!=c:\r\n                flg=0\r\n        if flg:\r\n            d.append([i,j,l[i][j]])\r\nans=[]\r\nwhile d:\r\n    i,j,c=d.pop()\r\n    if not vis[i][j]:    \r\n        ans.append([i,j,c])\r\n        vis[i][j]=1\r\n        opr(i,j)\r\n        for dx1,dy1 in dir:\r\n            for dx2,dy2 in dir:\r\n                i1=i+dx1-dx2\r\n                j1=j+dy1-dy2\r\n                v=check(i1,j1)\r\n                if v:\r\n                    d.append([i1,j1,v])\r\nflg=1\r\nfor i in range(n):\r\n\tfor j in range(m):\r\n\t\tif l[i][j]:\r\n\t\t\tflg=0\r\n\t\t\tbreak\r\n\tif not flg:\r\n\t\tbreak\r\n\r\nif not flg:\r\n    print(-1)\r\nelse:\r\n\tprint(len(ans))\r\n\tans.reverse()\r\n\tfor i,j,c in ans:\r\n\t\tprint(i+1,j+1,c)\r\n\r\n\r\n# def verify(ans):\r\n#     z=[[0 for i in range(m)]for j in range(n)]\r\n#     for each in ans:\r\n#         i,j,c=each\r\n#         for dx1,dy1 in dir:\r\n#             z[i+dx1][j+dy1]=c\r\n#     print(z)\r\n# verify(ans)", "from __future__ import division, print_function\r\nfrom collections import defaultdict\r\nimport math\r\nimport sys\r\nimport os\r\nfrom io import BytesIO, IOBase\r\nfrom collections import deque, Counter, OrderedDict, defaultdict\r\nimport heapq\r\n# ceil,floor,log,sqrt,factorial,pow,pi,gcd\r\nimport bisect\r\nfrom bisect import bisect_left,bisect_right\r\n\r\nBUFSIZE = 8192\r\n\r\n\r\nclass FastIO(IOBase):\r\n\tnewlines = 0\r\n\r\n\tdef __init__(self, file):\r\n\t\tself._fd = file.fileno()\r\n\t\tself.buffer = BytesIO()\r\n\t\tself.writable = \"x\" in file.mode or \"r\" not in file.mode\r\n\t\tself.write = self.buffer.write if self.writable else None\r\n\r\n\tdef read(self):\r\n\t\twhile True:\r\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n\t\t\tif not b:\r\n\t\t\t\tbreak\r\n\t\t\tptr = self.buffer.tell()\r\n\t\t\tself.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n\t\tself.newlines = 0\r\n\t\treturn self.buffer.read()\r\n\r\n\tdef readline(self):\r\n\t\twhile self.newlines == 0:\r\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n\t\t\tself.newlines = b.count(b\"\\n\") + (not b)\r\n\t\t\tptr = self.buffer.tell()\r\n\t\t\tself.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n\t\tself.newlines -= 1\r\n\t\treturn self.buffer.readline()\r\n\r\n\tdef flush(self):\r\n\t\tif self.writable:\r\n\t\t\tos.write(self._fd, self.buffer.getvalue())\r\n\t\t\tself.buffer.truncate(0), self.buffer.seek(0)\r\n\r\n\r\nclass IOWrapper(IOBase):\r\n\tdef __init__(self, file):\r\n\t\tself.buffer = FastIO(file)\r\n\t\tself.flush = self.buffer.flush\r\n\t\tself.writable = self.buffer.writable\r\n\t\tself.write = lambda s: self.buffer.write(s.encode(\"ascii\"))\r\n\t\tself.read = lambda: self.buffer.read().decode(\"ascii\")\r\n\t\tself.readline = lambda: self.buffer.readline().decode(\"ascii\")\r\n\r\n\r\ndef print(*args, **kwargs):\r\n\t\"\"\"Prints the values to a stream, or to sys.stdout by default.\"\"\"\r\n\tsep, file = kwargs.pop(\"sep\", \" \"), kwargs.pop(\"file\", sys.stdout)\r\n\tat_start = True\r\n\tfor x in args:\r\n\t\tif not at_start:\r\n\t\t\tfile.write(sep)\r\n\t\tfile.write(str(x))\r\n\t\tat_start = False\r\n\tfile.write(kwargs.pop(\"end\", \"\\n\"))\r\n\tif kwargs.pop(\"flush\", False):\r\n\t\tfile.flush()\r\n\r\n\r\nif sys.version_info[0] < 3:\r\n\tsys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)\r\nelse:\r\n\tsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\r\n\r\ninput = lambda: sys.stdin.readline().rstrip(\"\\r\\n\")\r\n\r\ndef inp():\r\n    return(int(input()))\r\ndef inps():\r\n    return input().strip()\r\ndef inlt():\r\n    return(list(map(int,input().split())))\r\ndef insr():\r\n    s = input().strip()\r\n    return(list(s[:len(s)]))\r\ndef invr():\r\n    return(map(int,input().split()))\r\n\r\nfrom types import GeneratorType\r\ndef bootstrap(f,stack=[]):\r\n\tdef wrappedfunc(*args,**kwargs):\r\n\t\tto=f(*args,**kwargs)\r\n\t\tif stack:\r\n\t\t\treturn to\r\n\t\telse:\r\n\t\t\twhile True:\r\n\t\t\t\tif type(to) is GeneratorType:\r\n\t\t\t\t\tstack.append(to)\r\n\t\t\t\t\tto=next(to)\r\n\t\t\t\telse:\r\n\t\t\t\t\tstack.pop()\r\n\t\t\t\t\tif not stack:\r\n\t\t\t\t\t\tbreak\r\n\t\t\t\t\tto=stack[-1].send(to)\r\n\t\t\treturn to\r\n\treturn wrappedfunc\r\n\r\ndef opr(i,j):\r\n    for dx1,dy1 in dir:\r\n        l[i+dx1][j+dy1]=0\r\n\r\ndef check(i,j):\r\n\tif vis[i][j]:\r\n\t\treturn 0\r\n\tv=0\r\n\tif i>=0 and j>=0 and i<n-1 and j<m-1:\r\n\t\tfor dx1,dy1 in dir:\r\n\t\t\tif l[i+dx1][j+dy1] and not v:\r\n\t\t\t\tv=l[i+dx1][j+dy1]\r\n\t\t\telif l[i+dx1][j+dy1] and v!=l[i+dx1][j+dy1]:\r\n\t\t\t\treturn 0\r\n\t\t# return s\r\n\treturn v\r\n\r\n\r\ndx=[1,1,0,0]\r\ndy=[0,1,0,1]\r\ndir=[(dx[i],dy[i]) for i in range(4)]\r\nn,m=invr()\r\nl=[]\r\nfor i in range(n):\r\n    l.append(inlt())\r\nvis=[[0]*m for j in range(n)]\r\nd=deque([])\r\nfor i in range(n-1):\r\n    for j in range(m-1):\r\n        c=l[i][j]\r\n        flg=1\r\n        for k in range(4):\r\n            if l[i+dx[k]][j+dy[k]]!=c:\r\n                flg=0\r\n        if flg:\r\n            d.append([i,j,l[i][j]])\r\nans=[]\r\nwhile d:\r\n    i,j,c=d.pop()\r\n    if not vis[i][j]:    \r\n        ans.append([i,j,c])\r\n        vis[i][j]=1\r\n        opr(i,j)\r\n        for dx1,dy1 in dir:\r\n            for dx2,dy2 in dir:\r\n                i1=i+dx1-dx2\r\n                j1=j+dy1-dy2\r\n                v=check(i1,j1)\r\n                if v:\r\n                    d.append([i1,j1,v])\r\nflg=1\r\n\r\nfor i in range(n):\r\n\tfor j in range(m):\r\n\t\tif l[i][j]:\r\n\t\t\tflg=0\r\n\t\t\tbreak\r\n\tif not flg:\r\n\t\tbreak\r\n\r\nif not flg:\r\n    print(-1)\r\nelse:\r\n\tprint(len(ans))\r\n\tans.reverse()\r\n\tfor i,j,c in ans:\r\n\t\tprint(i+1,j+1,c)\r\n\r\n\r\n# def verify(ans):\r\n#     z=[[0 for i in range(m)]for j in range(n)]\r\n#     for each in ans:\r\n#         i,j,c=each\r\n#         for dx1,dy1 in dir:\r\n#             z[i+dx1][j+dy1]=c\r\n#     print(z)\r\n# verify(ans)", "from __future__ import division, print_function\r\nfrom collections import defaultdict\r\nimport math\r\nimport sys\r\nimport os\r\nfrom io import BytesIO, IOBase\r\nfrom collections import deque, Counter, OrderedDict, defaultdict\r\nimport heapq\r\n# ceil,floor,log,sqrt,factorial,pow,pi,gcd\r\nimport bisect\r\nfrom bisect import bisect_left,bisect_right\r\n\r\nBUFSIZE = 8192\r\n\r\n\r\nclass FastIO(IOBase):\r\n\tnewlines = 0\r\n\r\n\tdef __init__(self, file):\r\n\t\tself._fd = file.fileno()\r\n\t\tself.buffer = BytesIO()\r\n\t\tself.writable = \"x\" in file.mode or \"r\" not in file.mode\r\n\t\tself.write = self.buffer.write if self.writable else None\r\n\r\n\tdef read(self):\r\n\t\twhile True:\r\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n\t\t\tif not b:\r\n\t\t\t\tbreak\r\n\t\t\tptr = self.buffer.tell()\r\n\t\t\tself.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n\t\tself.newlines = 0\r\n\t\treturn self.buffer.read()\r\n\r\n\tdef readline(self):\r\n\t\twhile self.newlines == 0:\r\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n\t\t\tself.newlines = b.count(b\"\\n\") + (not b)\r\n\t\t\tptr = self.buffer.tell()\r\n\t\t\tself.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n\t\tself.newlines -= 1\r\n\t\treturn self.buffer.readline()\r\n\r\n\tdef flush(self):\r\n\t\tif self.writable:\r\n\t\t\tos.write(self._fd, self.buffer.getvalue())\r\n\t\t\tself.buffer.truncate(0), self.buffer.seek(0)\r\n\r\n\r\nclass IOWrapper(IOBase):\r\n\tdef __init__(self, file):\r\n\t\tself.buffer = FastIO(file)\r\n\t\tself.flush = self.buffer.flush\r\n\t\tself.writable = self.buffer.writable\r\n\t\tself.write = lambda s: self.buffer.write(s.encode(\"ascii\"))\r\n\t\tself.read = lambda: self.buffer.read().decode(\"ascii\")\r\n\t\tself.readline = lambda: self.buffer.readline().decode(\"ascii\")\r\n\r\n\r\ndef print(*args, **kwargs):\r\n\t\"\"\"Prints the values to a stream, or to sys.stdout by default.\"\"\"\r\n\tsep, file = kwargs.pop(\"sep\", \" \"), kwargs.pop(\"file\", sys.stdout)\r\n\tat_start = True\r\n\tfor x in args:\r\n\t\tif not at_start:\r\n\t\t\tfile.write(sep)\r\n\t\tfile.write(str(x))\r\n\t\tat_start = False\r\n\tfile.write(kwargs.pop(\"end\", \"\\n\"))\r\n\tif kwargs.pop(\"flush\", False):\r\n\t\tfile.flush()\r\n\r\n\r\nif sys.version_info[0] < 3:\r\n\tsys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)\r\nelse:\r\n\tsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\r\n\r\ninput = lambda: sys.stdin.readline().rstrip(\"\\r\\n\")\r\n\r\ndef inp():\r\n    return(int(input()))\r\ndef inps():\r\n    return input().strip()\r\ndef inlt():\r\n    return(list(map(int,input().split())))\r\ndef insr():\r\n    s = input().strip()\r\n    return(list(s[:len(s)]))\r\ndef invr():\r\n    return(map(int,input().split()))\r\n\r\nfrom types import GeneratorType\r\ndef bootstrap(f,stack=[]):\r\n\tdef wrappedfunc(*args,**kwargs):\r\n\t\tto=f(*args,**kwargs)\r\n\t\tif stack:\r\n\t\t\treturn to\r\n\t\telse:\r\n\t\t\twhile True:\r\n\t\t\t\tif type(to) is GeneratorType:\r\n\t\t\t\t\tstack.append(to)\r\n\t\t\t\t\tto=next(to)\r\n\t\t\t\telse:\r\n\t\t\t\t\tstack.pop()\r\n\t\t\t\t\tif not stack:\r\n\t\t\t\t\t\tbreak\r\n\t\t\t\t\tto=stack[-1].send(to)\r\n\t\t\treturn to\r\n\treturn wrappedfunc\r\n\r\ndef opr(i,j):\r\n    for dx1,dy1 in dir:\r\n        l[i+dx1][j+dy1]=0\r\n\r\ndef check(i,j):\r\n\tif vis[i][j]:\r\n\t\treturn 0\r\n\tv=0\r\n\tif i>=0 and j>=0 and i<n-1 and j<m-1:\r\n\t\tfor dx1,dy1 in dir:\r\n\t\t\tif l[i+dx1][j+dy1] and not v:\r\n\t\t\t\tv=l[i+dx1][j+dy1]\r\n\t\t\telif l[i+dx1][j+dy1] and v!=l[i+dx1][j+dy1]:\r\n\t\t\t\treturn 0\r\n\t\t# return s\r\n\treturn v\r\n\r\n\r\ndx=[1,1,0,0]\r\ndy=[0,1,0,1]\r\ndir=[[dx[i],dy[i]] for i in range(4)]\r\nn,m=invr()\r\nl=[]\r\nfor i in range(n):\r\n    l.append(inlt())\r\nvis=[[0]*m for j in range(n)]\r\nd=deque([])\r\nfor i in range(n-1):\r\n    for j in range(m-1):\r\n        c=l[i][j]\r\n        flg=1\r\n        for k in range(4):\r\n            if l[i+dx[k]][j+dy[k]]!=c:\r\n                flg=0\r\n        if flg:\r\n            d.append([i,j,l[i][j]])\r\nans=[]\r\nwhile d:\r\n    i,j,c=d.pop()\r\n    if not vis[i][j]:    \r\n        ans.append([i,j,c])\r\n        vis[i][j]=1\r\n        opr(i,j)\r\n        for dx1,dy1 in dir:\r\n            for dx2,dy2 in dir:\r\n                i1=i+dx1-dx2\r\n                j1=j+dy1-dy2\r\n                v=check(i1,j1)\r\n                if v:\r\n                    d.append([i1,j1,v])\r\nflg=1\r\nfor i in range(n):\r\n    if sum(l[i]):\r\n        flg=0\r\n        break\r\n\r\nif not flg:\r\n    print(-1)\r\nelse:\r\n\tprint(len(ans))\r\n\tans.reverse()\r\n\tfor i,j,c in ans:\r\n\t\tprint(i+1,j+1,c)\r\n\r\n\r\n# def verify(ans):\r\n#     z=[[0 for i in range(m)]for j in range(n)]\r\n#     for each in ans:\r\n#         i,j,c=each\r\n#         for dx1,dy1 in dir:\r\n#             z[i+dx1][j+dy1]=c\r\n#     print(z)\r\n# verify(ans)", "from __future__ import division, print_function\r\nfrom collections import defaultdict\r\nimport math\r\nimport sys\r\nimport os\r\nfrom io import BytesIO, IOBase\r\nfrom collections import deque, Counter, OrderedDict, defaultdict\r\nimport heapq\r\n# ceil,floor,log,sqrt,factorial,pow,pi,gcd\r\nimport bisect\r\nfrom bisect import bisect_left,bisect_right\r\n\r\nBUFSIZE = 8192\r\n\r\n\r\nclass FastIO(IOBase):\r\n\tnewlines = 0\r\n\r\n\tdef __init__(self, file):\r\n\t\tself._fd = file.fileno()\r\n\t\tself.buffer = BytesIO()\r\n\t\tself.writable = \"x\" in file.mode or \"r\" not in file.mode\r\n\t\tself.write = self.buffer.write if self.writable else None\r\n\r\n\tdef read(self):\r\n\t\twhile True:\r\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n\t\t\tif not b:\r\n\t\t\t\tbreak\r\n\t\t\tptr = self.buffer.tell()\r\n\t\t\tself.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n\t\tself.newlines = 0\r\n\t\treturn self.buffer.read()\r\n\r\n\tdef readline(self):\r\n\t\twhile self.newlines == 0:\r\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n\t\t\tself.newlines = b.count(b\"\\n\") + (not b)\r\n\t\t\tptr = self.buffer.tell()\r\n\t\t\tself.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n\t\tself.newlines -= 1\r\n\t\treturn self.buffer.readline()\r\n\r\n\tdef flush(self):\r\n\t\tif self.writable:\r\n\t\t\tos.write(self._fd, self.buffer.getvalue())\r\n\t\t\tself.buffer.truncate(0), self.buffer.seek(0)\r\n\r\n\r\nclass IOWrapper(IOBase):\r\n\tdef __init__(self, file):\r\n\t\tself.buffer = FastIO(file)\r\n\t\tself.flush = self.buffer.flush\r\n\t\tself.writable = self.buffer.writable\r\n\t\tself.write = lambda s: self.buffer.write(s.encode(\"ascii\"))\r\n\t\tself.read = lambda: self.buffer.read().decode(\"ascii\")\r\n\t\tself.readline = lambda: self.buffer.readline().decode(\"ascii\")\r\n\r\n\r\ndef print(*args, **kwargs):\r\n\t\"\"\"Prints the values to a stream, or to sys.stdout by default.\"\"\"\r\n\tsep, file = kwargs.pop(\"sep\", \" \"), kwargs.pop(\"file\", sys.stdout)\r\n\tat_start = True\r\n\tfor x in args:\r\n\t\tif not at_start:\r\n\t\t\tfile.write(sep)\r\n\t\tfile.write(str(x))\r\n\t\tat_start = False\r\n\tfile.write(kwargs.pop(\"end\", \"\\n\"))\r\n\tif kwargs.pop(\"flush\", False):\r\n\t\tfile.flush()\r\n\r\n\r\nif sys.version_info[0] < 3:\r\n\tsys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)\r\nelse:\r\n\tsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\r\n\r\ninput = lambda: sys.stdin.readline().rstrip(\"\\r\\n\")\r\n\r\ndef inp():\r\n    return(int(input()))\r\ndef inps():\r\n    return input().strip()\r\ndef inlt():\r\n    return(list(map(int,input().split())))\r\ndef insr():\r\n    s = input().strip()\r\n    return(list(s[:len(s)]))\r\ndef invr():\r\n    return(map(int,input().split()))\r\n\r\nfrom types import GeneratorType\r\ndef bootstrap(f,stack=[]):\r\n\tdef wrappedfunc(*args,**kwargs):\r\n\t\tto=f(*args,**kwargs)\r\n\t\tif stack:\r\n\t\t\treturn to\r\n\t\telse:\r\n\t\t\twhile True:\r\n\t\t\t\tif type(to) is GeneratorType:\r\n\t\t\t\t\tstack.append(to)\r\n\t\t\t\t\tto=next(to)\r\n\t\t\t\telse:\r\n\t\t\t\t\tstack.pop()\r\n\t\t\t\t\tif not stack:\r\n\t\t\t\t\t\tbreak\r\n\t\t\t\t\tto=stack[-1].send(to)\r\n\t\t\treturn to\r\n\treturn wrappedfunc\r\n\r\ndef opr(i,j):\r\n    for dx1,dy1 in dir:\r\n        l[i+dx1][j+dy1]=0\r\n\r\ndef check(i,j):\r\n\tif vis[i][j]:\r\n\t\treturn 0\r\n\tv=0\r\n\tif i>=0 and j>=0 and i<n-1 and j<m-1:\r\n\t\tfor dx1,dy1 in dir:\r\n\t\t\tif l[i+dx1][j+dy1] and not v:\r\n\t\t\t\tv=l[i+dx1][j+dy1]\r\n\t\t\telif l[i+dx1][j+dy1] and v!=l[i+dx1][j+dy1]:\r\n\t\t\t\treturn 0\r\n\treturn v\r\n\r\n\r\ndx=[1,1,0,0]\r\ndy=[0,1,0,1]\r\ndir=[[dx[i],dy[i]] for i in range(4)]\r\n\r\n\r\nn,m=invr()\r\nl=[]\r\nfor i in range(n):\r\n    l.append(inlt())\r\nvis=[[0]*m for j in range(n)]\r\nd=deque([])\r\nfor i in range(n-1):\r\n    for j in range(m-1):\r\n        c=l[i][j]\r\n        flg=1\r\n        for k in range(4):\r\n            if l[i+dx[k]][j+dy[k]]!=c:\r\n                flg=0\r\n        if flg:\r\n            d.append([i,j,l[i][j]])\r\nans=[]\r\nwhile d:\r\n    i,j,c=d.pop()\r\n    if not vis[i][j]:    \r\n        ans.append([i,j,c])\r\n        vis[i][j]=1\r\n        opr(i,j)\r\n        for dx1,dy1 in dir:\r\n            for dx2,dy2 in dir:\r\n                i1=i+dx1-dx2\r\n                j1=j+dy1-dy2\r\n                v=check(i1,j1)\r\n                if v:\r\n                    d.append([i1,j1,v])\r\nflg=1\r\nfor i in range(n):\r\n    if sum(l[i]):\r\n        flg=0\r\n        break\r\n\r\nif not flg:\r\n    print(-1)\r\nelse:\r\n\tans.reverse()\r\n\tprint(len(ans))\r\n\tfor i,j,c in ans:\r\n\t\tprint(i+1,j+1,c)", "from collections import deque\r\n\r\ndef main():\r\n    \r\n    n, m = readIntArr()\r\n    \r\n    # grid = []\r\n    # for _ in range(n):\r\n    #     grid.append(readIntArr())\r\n    \r\n    # def check(i, j):\r\n    #     '''Return True if i, j can be top left of a full square of same color'''\r\n    #     if not (0 <= i < n - 1 and 0 <= j < m - 1):\r\n    #         return False\r\n    #     cols = set()\r\n    #     for ii in range(i, i + 2):\r\n    #         for jj in range(j, j + 2):\r\n    #             c = grid[ii][jj]\r\n    #             if c != -1:\r\n    #                 cols.add(c)\r\n    #     return len(cols) == 1 and not vi[i][j]\r\n    \r\n    # def unset(i, j):\r\n    #     vi[i][j] = True\r\n    #     for ii in range(i, i + 2):\r\n    #         for jj in range(j, j + 2):\r\n    #             grid[ii][jj] = -1\r\n    \r\n    # def getCol(i, j):\r\n    #     for ii in range(i, i + 2):\r\n    #         for jj in range(j, j + 2):\r\n    #             c = grid[ii][jj]\r\n    #             if c != - 1:\r\n    #                 return c\r\n    #     # print(i, j)\r\n    #     # for row in grid:\r\n    #     #     print(row)\r\n    #     assert False\r\n    \r\n    flatgrid = []\r\n    for _ in range(n):\r\n        flatgrid.extend(readIntArr())\r\n    def check(i, j):\r\n        if not (0 <= i < n - 1 and 0 <= j < m - 1):\r\n            return False\r\n        if vi[i * m + j]:\r\n            return False\r\n        arr = []\r\n        if flatgrid[i * m + j] != -1: arr.append(flatgrid[i * m + j])\r\n        if flatgrid[(i + 1) * m + j] != -1: arr.append(flatgrid[(i + 1) * m + j])\r\n        if flatgrid[i * m + j + 1] != -1: arr.append(flatgrid[i * m + j + 1])\r\n        if flatgrid[(i + 1) * m + j + 1] != -1: arr.append(flatgrid[(i + 1) * m + j + 1])\r\n        if len(arr) == 0:\r\n            return False\r\n        for i in range(1, len(arr)):\r\n            if arr[0] != arr[i]: # not unique\r\n                return False\r\n        return True\r\n    \r\n    def unset(i, j):\r\n        vi[i * m + j] = True\r\n        flatgrid[i * m + j] = flatgrid[(i + 1) * m + j] =\\\r\n            flatgrid[i * m + j + 1] = flatgrid[(i + 1) * m + j + 1] = -1\r\n    def getCol(i, j):\r\n        if flatgrid[i * m + j] != -1: return flatgrid[i * m + j]\r\n        if flatgrid[(i + 1) * m + j] != -1: return flatgrid[(i + 1) * m + j]\r\n        if flatgrid[i * m + j + 1] != -1: return flatgrid[i * m + j + 1]\r\n        if flatgrid[(i + 1) * m + j + 1] != -1: return flatgrid[(i + 1) * m + j + 1]\r\n        assert False\r\n    \r\n    ans = [] # (i, j, c)\r\n    q1 = deque()\r\n    q2 = deque()\r\n    vi = [False] * (m * n)\r\n    for i in range(n - 1, -1, -1):\r\n        for j in range(m - 1, -1, -1):\r\n            if check(i, j):\r\n                # q.append(i * m + j)\r\n                q1.append(i)\r\n                q2.append(j)\r\n                ans.append((i + 1, j + 1, getCol(i, j)))\r\n                unset(i, j)\r\n    # print('asdf', vi, vi[2][0])\r\n    while q1:\r\n        i = q1.popleft()\r\n        j = q2.popleft()\r\n        for ii, jj in ((i - 1, j - 1), (i - 1, j), (i - 1, j + 1),\r\n                       (i, j - 1), (i, j + 1),\r\n                       (i + 1, j - 1), (i + 1, j), (i + 1, j + 1)):\r\n            if check(ii, jj):\r\n                # print(ii, jj, vi[ii][jj])\r\n                ans.append((ii + 1, jj + 1, getCol(ii, jj)))\r\n                # q.append(ii * m + jj)\r\n                q1.append(ii)\r\n                q2.append(jj)\r\n                unset(ii, jj)\r\n    \r\n    # for i in range(n):\r\n    #     for j in range(m):\r\n    #         # if grid[i][j] != -1:\r\n    #         if flatgrid[i * m + j] != -1:\r\n    #             print(-1)\r\n    #             return\r\n    for X in range(n * m):\r\n        if flatgrid[X] != -1:\r\n            print(-1)\r\n            return\r\n    \r\n    print(len(ans))\r\n    multiLineArrayOfArraysPrint(reversed(ans))\r\n    \r\n    # for row in grid:\r\n    #     print(row)\r\n    # grid2 = [[-1 for _ in range(m)] for __ in range(n)]\r\n    # for i, j, c in ans:\r\n    #     i -= 1; j -= 1\r\n    #     for ii in range(i, i + 2):\r\n    #         for jj in range(j, j + 2):\r\n    #             grid2[ii][jj] = c\r\n    # print()\r\n    # for row in grid2:\r\n    #     print(row)\r\n    \r\n    return\r\n \r\nimport sys\r\ninput=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)\r\n# input=lambda: sys.stdin.readline().rstrip(\"\\r\\n\") #FOR READING STRING/TEXT INPUTS.\r\n \r\ndef oneLineArrayPrint(arr):\r\n    print(' '.join([str(x) for x in arr]))\r\ndef multiLineArrayPrint(arr):\r\n    print('\\n'.join([str(x) for x in arr]))\r\ndef multiLineArrayOfArraysPrint(arr):\r\n    print('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\r\n \r\ndef readIntArr():\r\n    return [int(x) for x in input().split()]\r\n# def readFloatArr():\r\n#     return [float(x) for x in input().split()]\r\n \r\ndef makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])\r\n    dv=defaultValFactory;da=dimensionArr\r\n    if len(da)==1:return [dv() for _ in range(da[0])]\r\n    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]\r\n \r\ndef queryInteractive(a, b, c):\r\n    print('? {} {} {}'.format(a, b, c))\r\n    sys.stdout.flush()\r\n    return int(input())\r\n \r\ndef answerInteractive(x1, x2):\r\n    print('! {} {}'.format(x1, x2))\r\n    sys.stdout.flush()\r\n \r\ninf=float('inf')\r\n# MOD=10**9+7\r\n# MOD=998244353\r\n \r\nfrom math import gcd,floor,ceil\r\nimport math\r\n# from math import floor,ceil # for Python2\r\n \r\nfor _abc in range(1):\r\n    main()"]

source: codeforces

raw_problem:
D. Big Brush

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You found a painting on a canvas of size $$$n \times m$$$. The canvas can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Each cell has some color. Cell $$$(i, j)$$$ has color $$$c_{i,j}$$$.

Near the painting you also found a brush in the shape of a $$$2 \times 2$$$ square, so the canvas was surely painted in the following way: initially, no cell was painted. Then, the following painting operation has been performed some number of times:

 Choose two integers $$$i$$$ and $$$j$$$ ($$$1 \le i < n$$$, $$$1 \le j < m$$$) and some color $$$k$$$ ($$$1 \le k \le nm$$$).

 Paint cells $$$(i, j)$$$, $$$(i + 1, j)$$$, $$$(i, j + 1)$$$, $$$(i + 1, j + 1)$$$ in color $$$k$$$.

All cells must be painted at least once. A cell can be painted multiple times. In this case, its final color will be the last one.

Find any sequence of at most $$$nm$$$ operations that could have led to the painting you found or state that it's impossible.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 1000$$$) — the dimensions of the canvas.

On the $$$i$$$-th of the next $$$n$$$ lines of input, there will be $$$m$$$ integers. The $$$j$$$-th of them is $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le nm$$$) — the color of cell $$$(i, j)$$$.

Output

If there is no solution, print a single integer $$$-1$$$.

Otherwise, on the first line, print one integer $$$q$$$ ($$$1 \le q \le nm$$$) — the number of operations.

Next, print the operations in order. On the $$$k$$$-th of the next $$$q$$$ lines, print three integers $$$i$$$, $$$j$$$, $$$c$$$ ($$$1 \le i < n$$$, $$$1 \le j < m$$$, $$$1 \le c \le nm$$$) — the description of the $$$k$$$-th operation.

If there are multiple solutions, print any.

Examples

Input

4 4
5 5 3 3
1 1 5 3
2 2 5 4
2 2 4 4

Output

6
1 3 3
3 3 4
2 2 5
1 1 5
2 1 1
3 1 2

Input

3 4
1 1 1 1
2 2 3 1
2 2 1 1

Output

-1

Note

In the first test case, the solution is not unique. Here's one of them:

In the second test case, there is no way one could obtain the given painting, thus the answer is $$$-1$$$.

question:
You found a painting on a canvas of size $$$n \times m$$$. The canvas can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Each cell has some color. Cell $$$(i, j)$$$ has color $$$c_{i,j}$$$.
Near the painting you also found a brush in the shape of a $$$2 \times 2$$$ square, so the canvas was surely painted in the following way: initially, no cell was painted. Then, the following painting operation has been performed some number of times:
 -  Choose two integers $$$i$$$ and $$$j$$$ ($$$1 \le i < n$$$, $$$1 \le j < m$$$) and some color $$$k$$$ ($$$1 \le k \le nm$$$). -  Paint cells $$$(i, j)$$$, $$$(i + 1, j)$$$, $$$(i, j + 1)$$$, $$$(i + 1, j + 1)$$$ in color $$$k$$$. All cells must be painted at least once. A cell can be painted multiple times. In this case, its final color will be the last one.
Find any sequence of at most $$$nm$$$ operations that could have led to the painting you found or state that it's impossible.

Input
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 1000$$$) — the dimensions of the canvas.
On the $$$i$$$-th of the next $$$n$$$ lines of input, there will be $$$m$$$ integers. The $$$j$$$-th of them is $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le nm$$$) — the color of cell $$$(i, j)$$$.

Output
If there is no solution, print a single integer $$$-1$$$.
Otherwise, on the first line, print one integer $$$q$$$ ($$$1 \le q \le nm$$$) — the number of operations.
Next, print the operations in order. On the $$$k$$$-th of the next $$$q$$$ lines, print three integers $$$i$$$, $$$j$$$, $$$c$$$ ($$$1 \le i < n$$$, $$$1 \le j < m$$$, $$$1 \le c \le nm$$$) — the description of the $$$k$$$-th operation.
If there are multiple solutions, print any.

Examples
Input
4 4
5 5 3 3
1 1 5 3
2 2 5 4
2 2 4 4

Output
6
1 3 3
3 3 4
2 2 5
1 1 5
2 1 1
3 1 2

Input
3 4
1 1 1 1
2 2 3 1
2 2 1 1

Output
-1

Note
In the first test case, the solution is not unique. Here's one of them:
 ![image](1.png) In the second test case, there is no way one could obtain the given painting, thus the answer is $$$-1$$$.

data_split: test


Artur

difficulty: HARD

source: open kattis

raw_problem:
You have most definitely heard the legend of King Arthur and
    the Knights of the Round Table. Almost all versions of this
    story proudly point out that the roundness of the Round Table
    is closely related to Arthur’s belief of equality among the
    Knights. That is a lie! In fact, Arthur’s choice of table is
    conditioned by his childhood traumas.

In fact, Arthur was forced to clean up quadratic tables from
    a young age after a tournament in pick-up sticks1 had been played on them. After the
    tournament, typically there would be a bunch of sticks on the
    table that do not touch each other. In the spirit of the game,
    the organizers issued strict regulations for the table
    cleaners. More precisely, the sticks on the table need to be
    removed one by one in a way that the cleaners pull them in the
    shortest way towards the edge of the table closest to where
    they are currently sitting. They also mustn’t rotate or touch
    the other sticks while doing this (not even in the edge
    points).

In this task, we will represent the table in the coordinate
    system with a square that has opposite points in the
    coordinates $(0,0)$ and
    $(10\, 000, 10\, 000)$,
    whereas the sticks will be represented with straight line
    segments that lie within that square. We will assume that
    Arthur is sitting at the edge of the table lying on the
    $x$-axis. Then the
    movement of the stick comes down to translating the line
    segment along the shortest path towards the $x$-axis until the stick falls off the
    table (as shown in the image). It is your task to help Arthur
    determine the order of stick movements that meets the
    requirements from the previous paragraph.

Input

The first line of input contains the integer $N$ ($1
    \leq N \leq 5\, 000$), the number of sticks on the
    table. Each of the following $N$ lines contains four integers
    $x_1$, $y_1$, $x_2$, $y_2$ ($0 \leq x_1, y_1, x_2, y_2 \leq 10\,
    000$) that denote the edge points of a stick.

Output

The first and only line of output must contain
    space-separated stick labels in the order which they need to be
    taken off the table. A stick’s label corresponds to its
    position in the input sequence.

If there are multiple possible solutions, output any of
    them.

Sample Input 1
Sample Output 1

4
1 3 2 2
1 1 3 2
2 4 7 3
3 3 5 3

2 4 1 3

Sample Input 2
Sample Output 2

4
0 0 1 1
1 2 0 3
2 2 3 3
4 0 3 1

4 3 1 2

Sample Input 3
Sample Output 3

3
4 6 5 5
2 1 15 1
3 2 8 7

2 3 1

question:
You have most definitely heard the legend of King Arthur and the Knights of the Round Table. Almost all versions of this story proudly point out that the roundness of the Round Table is closely related to Arthur’s belief of equality among the Knights. That is a lie! In fact, Arthur’s choice of table is conditioned by his childhood traumas.
In fact, Arthur was forced to clean up quadratic tables from a young age after a tournament in pick-up sticks^{1}had been played on them. After the tournament, typically there would be a bunch of sticks on the table that do not touch each other. In the spirit of the game, the organizers issued strict regulations for the table cleaners. More precisely, the sticks on the table need to be removed one by one in a way that the cleaners pull them in the shortest way towards the edge of the table closest to where they are currently sitting. They also mustn’t rotate or touch the other sticks while doing this (not even in the edge points).
In this task, we will represent the table in the coordinate system with a square that has opposite points in the coordinates$(0,0)$and$(10\, 000, 10\, 000)$, whereas the sticks will be represented with straight line segments that lie within that square. We will assume that Arthur is sitting at the edge of the table lying on the$x$-axis. Then the movement of the stick comes down to translating the line segment along the shortest path towards the$x$-axis until the stick falls off the table (as shown in the image). It is your task to help Arthur determine the order of stick movements that meets the requirements from the previous paragraph.
![image](1.png)
Input
The first line of input contains the integer$N$($1 \leq N \leq 5\, 000$), the number of sticks on the table. Each of the following$N$lines contains four integers$x_1$,$y_1$,$x_2$,$y_2$($0 \leq x_1, y_1, x_2, y_2 \leq 10\, 000$) that denote the edge points of a stick.

Output
The first and only line of output must contain space-separated stick labels in the order which they need to be taken off the table. A stick’s label corresponds to its position in the input sequence.
If there are multiple possible solutions, output any of them.
Sample Input 1
4
1 3 2 2
1 1 3 2
2 4 7 3
3 3 5 3

Sample Output 1
2 4 1 3

Sample Input 2
4
0 0 1 1
1 2 0 3
2 2 3 3
4 0 3 1

Sample Output 2
4 3 1 2

Sample Input 3
3
4 6 5 5
2 1 15 1
3 2 8 7

Sample Output 3
2 3 1

data_split: test


Web 0.5

source: ACM-ICPC Japan Alumni Group Summer Camp 2006 Day 3

raw_problem:
Web 0.5

In a forest, there lived a spider named Tim. Tim was so smart that he created a huge, well-structured web.
Surprisingly, his web forms a set of equilateral and concentric N-sided polygons whose edge lengths
form an arithmetic sequence.

Figure 1: An example web of Tim

Corresponding vertices of the N-sided polygons lie on a straight line, each apart from neighboring ver-
tices by distance 1. Neighboring vertices are connected by a thread (shown in the figure as solid lines),
on which Tim can walk (you may regard Tim as a point). Radial axes are numbered from 1 to N in a
rotational order, so you can denote by (r, i) the vertex on axis i and apart from the center of the web by
distance r. You may consider the web as infinitely large, i.e. consisting of infinite number of N-sided
polygons, since the web is so gigantic.

Tim’s web is thus marvelous, but currently has one problem: due to rainstorms, some of the threads are
damaged and Tim can’t walk on those parts.

Now, a bug has been caught on the web. Thanks to the web having so organized a structure, Tim accu-
rately figures out where the bug is, and heads out for that position. You, as a biologist, are interested in
whether Tim is smart enough to move through the shortest possible route. To judge that, however, you
need to know the length of the shortest route yourself, and thereby decided to write a program which
calculates that length.

Input

The input consists of multiple test cases. Each test case begins with a line containing two integers N
(3 ≤ N ≤ 100) and X (0 ≤ X ≤ 100), where N is as described above and X denotes the number of
damaged threads. Next line contains four integers rS, iS, rT, and iT, meaning that Tim is starting at (rS, iS) and the bug is at (rT, iT). This line is followed by X lines, each containing four integers rA, iA, rB, and
iB, meaning that a thread connecting (rA, iA) and (rB, iB) is damaged. Here (rA, iA) and (rB, iB) will be
always neighboring to each other. Also, for all vertices (r, i) given above, you may assume 1 ≤ r ≤ 107
and 1 ≤ i ≤ N.

There will be at most 200 test cases. You may also assume that Tim is always able to reach where the
bug is.

The input is terminated by a line containing two zeros.

Output

For each test case, print the length of the shortest route in a line. You may print any number of digits
after the decimal point, but the error must not be greater than 0.01.

Sample Input

5 1
2 1 3 2
2 1 2 2
0 0

Output for the Sample Input

4.18

source: aizu

question:
Web 0.5

In a forest, there lived a spider named Tim. Tim was so smart that he created a huge, well-structured web.
Surprisingly, his web forms a set of equilateral and concentric N-sided polygons whose edge lengths
form an arithmetic sequence.

![image](1.png)
Figure 1: An example web of Tim

Corresponding vertices of the N-sided polygons lie on a straight line, each apart from neighboring ver-
tices by distance 1. Neighboring vertices are connected by a thread (shown in the figure as solid lines),
on which Tim can walk (you may regard Tim as a point). Radial axes are numbered from 1 to N in a
rotational order, so you can denote by (r, i) the vertex on axis i and apart from the center of the web by
distance r. You may consider the web as infinitely large, i.e. consisting of infinite number of N-sided
polygons, since the web is so gigantic.

Tim’s web is thus marvelous, but currently has one problem: due to rainstorms, some of the threads are
damaged and Tim can’t walk on those parts.

Now, a bug has been caught on the web. Thanks to the web having so organized a structure, Tim accu-
rately figures out where the bug is, and heads out for that position. You, as a biologist, are interested in
whether Tim is smart enough to move through the shortest possible route. To judge that, however, you
need to know the length of the shortest route yourself, and thereby decided to write a program which
calculates that length.

Input

The input consists of multiple test cases. Each test case begins with a line containing two integers N
(3 ≤ N ≤ 100) and X (0 ≤ X ≤ 100), where N is as described above and X denotes the number of
damaged threads. Next line contains four integers r_{S}, i_{S}, r_{T}, and i_{T}, meaning that Tim is starting at (r_{S}, i_{S}) and the bug is at (r_{T}, i_{T}). This line is followed by X lines, each containing four integers r_{A}, i_{A}, r_{B}, and
i_{B}, meaning that a thread connecting (r_{A}, i_{A}) and (r_{B}, i_{B}) is damaged. Here (r_{A}, i_{A}) and (r_{B}, i_{B}) will be
always neighboring to each other. Also, for all vertices (r, i) given above, you may assume 1 ≤ r ≤ 10^{7}
and 1 ≤ i ≤ N.

There will be at most 200 test cases. You may also assume that Tim is always able to reach where the
bug is.

The input is terminated by a line containing two zeros.

Output

For each test case, print the length of the shortest route in a line. You may print any number of digits
after the decimal point, but the error must not be greater than 0.01.

Sample Input

5 1
2 1 3 2
2 1 2 2
0 0

Output for the Sample Input

4.18

data_split: test


solutions: ["import sys\ninput = sys.stdin.buffer.readline\nfrom collections import defaultdict\n\ndef getlist():\n\treturn list(map(int, input().split()))\n\ndef main():\n\t(H, W, h, w) = getlist()\n\tL = [[1] * W for i in range(H)]\n\tif h * w != 1:\n\t\tx = (10 ** 9 - 1) // (h * w - 1)\n\t\tfor i in range(H):\n\t\t\tfor j in range(W):\n\t\t\t\tL[i][j] = x\n\tfor i in range(H // h):\n\t\tfor j in range(W // w):\n\t\t\tL[(i + 1) * h - 1][(j + 1) * w - 1] = -10 ** 9\n\ts = 0\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\ts += L[i][j]\n\tif s < 0:\n\t\tprint('No')\n\t\treturn\n\tprint('Yes')\n\tfor i in range(H):\n\t\tprint(' '.join(list(map(str, L[i]))))\nmain()\n", "(H, W, h, w) = map(int, input().split())\n\ndef solve(H, W, h, w):\n\tif W % w == 0 and H % h == 0:\n\t\treturn (False, [])\n\tif W % w == 0:\n\t\treturn (True, solve_vertical(H, W, h, w))\n\treturn (True, solve_horizontal(H, W, h, w))\n\ndef solve_horizontal(H, W, h, w):\n\treturn [solve_horizontal_core(W, w)] * H\n\ndef solve_horizontal_core(W, w):\n\t(m, r) = divmod(W, w)\n\trow = [0] * W\n\trow[0] = m + 1\n\trow[w - 1] = -m - 2\n\tfor i in range(w, W):\n\t\trow[i] = row[i - w]\n\treturn row\n\ndef solve_vertical(H, W, h, w):\n\tcol = solve_horizontal_core(H, h)\n\tm = []\n\tfor c in col:\n\t\tm.append([c] * W)\n\treturn m\n(yesno, mat) = solve(H, W, h, w)\nif yesno:\n\tprint('Yes')\n\tfor row in mat:\n\t\tprint(*row)\nelse:\n\tprint('No')\n", "(H, W, h, w) = list(map(int, input().split()))\nINF = 10 ** 10\nmat = [[1000 for _ in range(H)] for _ in range(W)]\nval = -h * w * 1000 + 999\nfor h_new in range(h - 1, H, h):\n\tfor w_new in range(w - 1, W, w):\n\t\tmat[w_new][h_new] = val\nif sum((sum((mat[j][i] for i in range(H))) for j in range(W))) < 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\tprint(mat[j][i], end=' ')\n\t\tprint('')\n", "from sys import exit\n(H, W, h, w) = map(int, input().split())\nif not H % h and (not W % w):\n\tprint('No')\n\texit()\nprint('Yes')\nG = [[1000] * W for _ in range(H)]\nif H % h:\n\tfor i in range(H // h):\n\t\tt = (i + 1) * h - 1\n\t\tfor j in range(W):\n\t\t\tG[t][j] = -(h - 1) * 1000 - 1\nelse:\n\tfor i in range(W // w):\n\t\tt = (i + 1) * w - 1\n\t\tfor j in range(H):\n\t\t\tG[j][t] = -(w - 1) * 1000 - 1\nfor g in G:\n\tprint(*g)\n", "(H, W, h, w) = map(int, input().split())\np = (10 ** 9 - 1) // max(h * w - 1, 1)\nm = p * (h * w - 1) + 1\nvec = [[p for i in range(W + 1)] for j in range(H + 1)]\nsm = 0\nfor i in range(1, H + 1):\n\tfor j in range(1, W + 1):\n\t\tif i % h == 0 and j % w == 0:\n\t\t\tvec[i][j] = -m\n\t\tsm += vec[i][j]\nif sm <= 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tfor i in range(1, H + 1):\n\t\tfor j in range(1, W + 1):\n\t\t\tprint(vec[i][j], end=' \\n'[j == W])\n", "import sys\ninput = lambda : sys.stdin.readline().rstrip()\nsys.setrecursionlimit(max(1000, 10 ** 9))\nwrite = lambda x: sys.stdout.write(x + '\\n')\n(H, W, h, w) = map(int, input().split())\nv = [[0] * W for _ in range(H)]\nif H % h == 0 and W % w == 0:\n\tprint('No')\nelse:\n\tfor i in range(H // h):\n\t\tfor j in range(W // w):\n\t\t\tv[(i + 1) * h - 1][(j + 1) * w - 1] = -10 ** 9\n\tfor i in range(H // h + 1):\n\t\tfor j in range(W // w + 1):\n\t\t\tif i * h < H and j * w < W:\n\t\t\t\tv[i * h][j * w] = 10 ** 9 - 1\n\tss = sum((sum(vv) for vv in v))\n\tif ss > 0:\n\t\tprint('Yes')\n\t\twrite('\\n'.join((' '.join(map(str, vv)) for vv in v)))\n\telse:\n\t\tprint('No')\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\n\texit()\nrem = H * W - (H - H % h) * (W - W % w)\nx = H // h * W // w // rem + 1\na = [[x] * W for _ in range(H)]\nfor i in range(h - 1, H, h):\n\tfor j in range(w - 1, W, w):\n\t\ta[i][j] = -(h * w - 1) * x - 1\nprint('Yes')\nfor row in a:\n\tprint(*row)\n", "(H, W, h, w) = map(int, input().split())\nlis = [[600] * W for i in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i % h == h - 1 and j % w == w - 1:\n\t\t\tlis[i][j] = -600 * (h * w - 1) - 1\ns = 0\nfor i in range(H):\n\ts += sum(lis[i])\nif s <= 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tfor i in lis:\n\t\tprint(' '.join(map(str, i)))\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\n\tquit()\nelse:\n\tprint('Yes')\nm = -10 ** 9\np = (-m - 1) // (h * w - 1)\nans = [[m if i % h == 0 and j % w == 0 else p for j in range(1, W + 1)] for i in range(1, H + 1)]\nfor i in ans:\n\tprint(' '.join(map(str, i)))\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tans = [[None] * W for i in range(H)]\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\tif i % h == h - 1 and j % w == w - 1:\n\t\t\t\tans[i][j] = -1 * 1000 * (h * w - 1) - 1\n\t\t\telse:\n\t\t\t\tans[i][j] = 1000\n\tfor i in ans:\n\t\tprint(*i)\n", "import sys\n(H, W, h, w) = map(int, input().split())\nrh = H % h\nrw = W % w\nqh = H // h\nqw = W // w\nif rh == 0 and rw == 0:\n\tprint('No')\n\tsys.exit()\nprint('Yes')\ndp = [[0] * W for i in range(H)]\nfor i in range(0, H, h):\n\tfor j in range(0, W, w):\n\t\tdp[i][j] = 10 ** 9 - 1\nfor i in range(h - 1, H, h):\n\tfor j in range(w - 1, W, w):\n\t\tdp[i][j] = -10 ** 9\nfor i in range(H):\n\tprint(' '.join(map(str, dp[i])))\n", "import sys\ninput = sys.stdin.readline\n(H, W, h, w) = map(int, input().split())\nunit = 10 ** 9 - 1\nc = H * W\nfor i in range(h - 1, H, h):\n\tfor j in range(w - 1, W, w):\n\t\tc -= 1\nif c == 0:\n\tprint('No')\n\texit(0)\nres = [[unit // c] * W for _ in range(H)]\nfor i in range(h - 1, H, h):\n\tfor j in range(w - 1, W, w):\n\t\tres[i][j] = -(unit // c * (h * w - 1) + 1)\nif sum([sum(r) for r in res]) > 0:\n\tprint('Yes')\n\tfor r in res:\n\t\tprint(*r)\nelse:\n\tprint('No')\n", "(H, W, a, b) = map(int, input().split())\nif H % a or W % b:\n\tprint('Yes')\n\taccAs = [0]\n\tif H % a:\n\t\t(N, c) = (H, a)\n\t\tk = -(-H // a)\n\telse:\n\t\t(N, c) = (W, b)\n\t\tk = -(-W // b)\n\tfor i in range(k):\n\t\taccAs += [k - i] * (c - 1) + [-i - 1]\n\tAs = []\n\tfor i in range(N):\n\t\tAs.append(accAs[i + 1] - accAs[i])\n\tif H % a:\n\t\tfor i in range(H):\n\t\t\tprint(' '.join(map(str, [As[i]] * W)))\n\telse:\n\t\tfor _ in range(H):\n\t\t\tprint(*As)\nelse:\n\tprint('No')\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\n\texit()\nbig = 1000\nmul = h * w - 1\nprint('Yes')\nfor y in range(1, H + 1):\n\tarr = []\n\tfor x in range(1, W + 1):\n\t\tif y % h == 0 and x % w == 0:\n\t\t\tarr.append(-(big * mul + 1))\n\t\telse:\n\t\t\tarr.append(big)\n\tprint(' '.join(map(str, arr)))\n", "(H, W, h, w) = map(int, input().split())\np = 1000\nif H % h > 0 or W % w > 0:\n\tprint('Yes')\n\ta = [[p] * W for i in range(H)]\n\tfor i in range(h - 1, H, h):\n\t\tfor j in range(w - 1, W, w):\n\t\t\ta[i][j] = -p * (h * w - 1) - 1\n\tfor i in range(H):\n\t\tprint(' '.join(map(str, a[i])))\nelse:\n\tprint('No')\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\n\texit()\nprint('Yes')\nn = 1000\nif W % w:\n\tm = -((w - 1) * n + 1)\n\trow = [m if i % w == w - 1 else n for i in range(W)]\n\tfor i in range(H):\n\t\tprint(*row)\nelse:\n\tm = -((h - 1) * n + 1)\n\tfor i in range(H):\n\t\tif i % h == h - 1:\n\t\t\tprint(*[m] * W)\n\t\telse:\n\t\t\tprint(*[n] * W)\n", "def examA():\n\tAlpha = [chr(i) for i in range(97, 97 + 26)]\n\tS = SI()\n\tN = len(S)\n\tans = -1\n\tfor i in range(N):\n\t\tfor s in Alpha:\n\t\t\tcur = [s for s in S]\n\t\t\tfor l in range(i):\n\t\t\t\tfor k in range(N - 1):\n\t\t\t\t\tif cur[k + 1] == s:\n\t\t\t\t\t\tcur[k] = s\n\t\t\tif len(Counter(cur[:N - i])) == 1:\n\t\t\t\tans = i\n\t\t\t\tbreak\n\t\tif ans >= 0:\n\t\t\tbreak\n\tprint(ans)\n\treturn\n\ndef examB():\n\tN = I()\n\tA = LI()\n\td = defaultdict(int)\n\tfor a in A:\n\t\td[a] += 1\n\tl = min(d)\n\tr = max(d)\n\tans = 'Yes'\n\tif l >= N:\n\t\tans = 'No'\n\tif r - l > 1:\n\t\tans = 'No'\n\tif d[l] > l:\n\t\tans = 'No'\n\tif (r - d[l]) * 2 + d[l] > N:\n\t\tans = 'No'\n\tif r == l and (N - l == 1 or N // 2 >= l):\n\t\tans = 'Yes'\n\tprint(ans)\n\treturn\n\ndef examC():\n\t(H, W, h, w) = LI()\n\tjudge = H % h + W % w\n\tif judge == 0:\n\t\tprint('No')\n\t\treturn\n\tprint('Yes')\n\tnow = H // h + W // w\n\tneg = -(h * w - 1) * now - 1\n\tA = [[now] * W for _ in range(H)]\n\tfor i in range(1, 1 + H // h):\n\t\tfor j in range(1, 1 + W // w):\n\t\t\tA[i * h - 1][j * w - 1] = neg\n\tfor v in A:\n\t\tprint(' '.join(map(str, v)))\n\treturn\nimport sys, copy, bisect, itertools, heapq, math\nfrom heapq import heappop, heappush, heapify\nfrom collections import Counter, defaultdict, deque\n\ndef I():\n\treturn int(sys.stdin.readline())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef LSI():\n\treturn list(map(str, sys.stdin.readline().split()))\n\ndef LS():\n\treturn sys.stdin.readline().split()\n\ndef SI():\n\treturn sys.stdin.readline().strip()\nmod = 10 ** 9 + 7\ninf = float('inf')\nexamC()\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\n\texit()\nprint('Yes')\nBase = [[0] * w for i in range(h)]\nBase[0][0] = 10000000\nBase[-1][-1] = -10000001\nM = [[0] * W for i in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tM[i][j] = str(Base[i % h][j % w])\nfor i in range(H):\n\tprint(' '.join(M[i]))\n", "def solve(W, w):\n\tA = [1] * W\n\tfor i in range(W - 1, w - 1, -1):\n\t\tA[i - w] = A[i] + 1\n\tA[w - 1::w] = [-i for i in range(1, W // w + 1)]\n\tfor i in range(W - 2, -1, -1):\n\t\tA[i + 1] -= A[i]\n\treturn A\n(H, W, h, w) = map(int, input().split())\nif W % w:\n\tprint('Yes')\n\tA = solve(W, w)\n\tfor _ in range(H):\n\t\tprint(*A)\nelif H % h:\n\tprint('Yes')\n\tA = solve(H, h)\n\tfor i in range(H):\n\t\tprint(*[A[i]] * W)\nelse:\n\tprint('No')\n", "def main():\n\t(H, W, h, w) = map(int, input().split())\n\tp = 4000\n\tq = h * w - 1\n\ta = [[p] * W for _ in [0] * H]\n\tfor i in range(H // h):\n\t\tfor j in range(W // w):\n\t\t\ta[(i + 1) * h - 1][(j + 1) * w - 1] = -p * q - 1\n\tif sum([sum(i) for i in a]) <= 0:\n\t\tprint('No')\n\telse:\n\t\tprint('Yes')\n\t\tfor i in a:\n\t\t\tprint(*i)\nmain()\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tans = [[1000] * W for i in range(H)]\n\tnum = 0\n\tfor i in range(h - 1, H, h):\n\t\tfor j in range(w - 1, W, w):\n\t\t\tans[i][j] = -(h * w - 1) * 1000 - 1\n\t\t\tnum += 1\n\tfor nu in ans:\n\t\tprint(' '.join(map(str, nu)))\n", "(H, W, h, w) = map(int, input().split())\nif H % h or W % w:\n\tprint('Yes')\n\ta = 10 ** 9 // (h * w)\n\tans = [[a] * W for _ in [0] * H]\n\tfor i in range(h - 1, H, h):\n\t\tfor j in range(w - 1, W, w):\n\t\t\tans[i][j] = -a * (h * w - 1) - 1\n\tfor out in ans:\n\t\tprint(*out)\nelse:\n\tprint('No')\n", "(H, W, h, w) = map(int, input().split())\nif H % h == W % w == 0:\n\tprint('No')\n\texit(0)\nprint('Yes')\nf = 0\n(a, b) = (W, w)\nif not W % w:\n\tf = 1\n\t(a, b) = (H, h)\nl = [0] * (a + 1)\nl[1] = 10 ** 6\nfor i in range(2, a + 1):\n\tif i >= b:\n\t\tl[i] = l[i - b] - 1\n\telse:\n\t\tl[i] = l[i - 1] - 1\nassert l[-1] > 0\ng = [l[i + 1] - l[i] for i in range(a)]\nif f:\n\tfor x in g:\n\t\tprint(*[x] * W)\nelse:\n\tfor _ in range(H):\n\t\tprint(*g)\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\n\tquit()\nprint('Yes')\n\ndef solve(H, W, h, w):\n\tS = [0] * (W + 1)\n\tS[W % w] = 1 + W // w\n\tfor i in range(w, W + 1):\n\t\tS[i] = S[i - w] - 1\n\treturn [[S[i + 1] - S[i] for i in range(W)]] * H\nif W % w != 0:\n\tA = solve(H, W, h, w)\nelse:\n\tA = [r for r in zip(*solve(W, H, w, h))]\nfor a in A:\n\tprint(*a)\n", "(H, W, h, w) = map(int, input().split())\nA = [[0] * W for _ in range(H)]\nP = 10 ** 9 - 1\nM = -10 ** 9\nfor y in range(0, H, h):\n\tfor x in range(0, W, w):\n\t\tA[y][x] = P\nfor y in range(h - 1, H, h):\n\tfor x in range(w - 1, W, w):\n\t\tA[y][x] = M\ns = sum(map(sum, A))\nif s <= -1:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tfor a in A:\n\t\tprint(*a)\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tk = 1000000\n\tR = [[0] * W for i in range(H)]\n\tfor i in range(0, H, h):\n\t\tfor j in range(0, W, w):\n\t\t\tR[i][j] += k\n\t\t\tif i + h - 1 < H:\n\t\t\t\tR[i + h - 1][j] += k\n\t\t\tif j + w - 1 < W:\n\t\t\t\tR[i][j + w - 1] += k\n\t\t\tif i + h - 1 < H and j + w - 1 < W:\n\t\t\t\tR[i + h - 1][j + w - 1] -= 3 * k + 1\n\tfor r in R:\n\t\tprint(*r)\n", "import sys\n(H, W, h, w) = map(int, input().split())\nif W % w == 0 and H % h == 0:\n\tprint('No')\n\tsys.exit()\nprint('Yes')\nif W % w != 0:\n\tm = []\n\ta = str(1000 * (w - 1))\n\tb = str(-1001)\n\tfor i in range(W):\n\t\tif i % w == 0:\n\t\t\tm.append(a)\n\t\telse:\n\t\t\tm.append(b)\n\ts = ' '.join(m)\n\tfor i in range(H):\n\t\tprint(s)\nelse:\n\tm1 = ' '.join([str(1000 * (h - 1))] * W)\n\tm2 = ' '.join([str(-1001)] * W)\n\tfor i in range(H):\n\t\tif i % h == 0:\n\t\t\tprint(m1)\n\t\telse:\n\t\t\tprint(m2)\n", "(H, W, h, w) = map(int, input().split())\nif W % w != 0:\n\tprint('Yes')\n\ts = [0 for i in range(W + 1)]\n\ts[W % w] = 1 + W // w\n\tfor i in range(w, W + 1):\n\t\ts[i] = s[i - w] - 1\n\ta = [s[i] - s[i - 1] for i in range(1, W + 1)]\n\tans = [[str(a[i]) for i in range(W)] for j in range(H)]\n\tfor line in ans:\n\t\tprint(' '.join(line))\nelif H % h != 0:\n\tprint('Yes')\n\ts = [0 for i in range(H + 1)]\n\ts[H % h] = 1 + H // h\n\tfor i in range(h, H + 1):\n\t\ts[i] = s[i - h] - 1\n\ta = [s[i] - s[i - 1] for i in range(1, H + 1)]\n\tans = [[str(a[i]) for j in range(W)] for i in range(H)]\n\tfor line in ans:\n\t\tprint(' '.join(line))\nelse:\n\tprint('No')\n", "(H, W, h, w) = [int(v) for v in input().split()]\nif H % h == 0 and W % w == 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tgrid = [[-h * w * 1000 + 999 if i % h == h - 1 and j % w == w - 1 else 1000 for j in range(W)] for i in range(H)]\n\tfor i in grid:\n\t\tprint(*i)\n", "import sys\n(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\nelif H % h != 0:\n\tprint('Yes')\n\tp = 100000 * (h - 1) - 1\n\tq = -100000\n\tL = int(H / h)\n\tfor l in range(L):\n\t\tfor i in range(W):\n\t\t\tprint(p, end=' ')\n\t\tprint('')\n\t\tfor i in range(h - 1):\n\t\t\tfor i in range(W):\n\t\t\t\tprint(q, end=' ')\n\t\t\tprint('')\n\tfor i in range(W):\n\t\tprint(p, end=' ')\n\tprint('')\n\tfor i in range(H - L * h - 1):\n\t\tfor i in range(W):\n\t\t\tprint(q, end=' ')\nelse:\n\tprint('Yes')\n\tp = 100000 * (w - 1) - 1\n\tq = -100000\n\tL = int(W / w)\n\ts = ([p] + [q] * (w - 1)) * L + [p] + [q] * (W - L * w - 1)\n\tfor j in range(H):\n\t\tfor i in range(W):\n\t\t\tprint(s[i], end=' ')\n\t\tprint('')\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\nelif h == 1:\n\tprint('Yes')\n\tcoef = 999999999 // (w - 1)\n\t(plus, minus) = (coef, -coef * (w - 1) - 1)\n\tfor _ in range(H):\n\t\tprint(*[minus if j % w == 0 else plus for j in range(1, W + 1)])\nelif w == 1:\n\tprint('Yes')\n\tcoef = 999999999 // (h - 1)\n\t(plus, minus) = (coef, -coef * (h - 1) - 1)\n\tfor i in range(1, H + 1):\n\t\tprint(*[minus if i % h == 0 else plus for _ in range(W)])\nelse:\n\tprint('Yes')\n\tcoef = min(999999999 // ((h - 1) * (w - 1)), 1000000000 // (h + w - 1))\n\t(plus, minus) = (coef * (h + w - 1), -coef * (h - 1) * (w - 1) - 1)\n\tfor i in range(1, H + 1):\n\t\tif i % h != 0:\n\t\t\tprint(*[minus if j % w == 0 else plus for j in range(1, W + 1)])\n\t\telse:\n\t\t\tprint(*[minus for _ in range(W)])\n", "import sys\ninput = sys.stdin.readline\n(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\n\texit()\n(x, y) = (H // h, W // w)\ns = x * y + 1\nt = (h * w - 1) * s + 1\nimport numpy as np\ngrid = np.full((H + 1, W + 1), s, dtype=np.int32)\ngrid[::h, ::w] = -t\ngrid = grid[1:, 1:]\nprint('Yes')\nfor row in grid:\n\tprint(' '.join(row.astype(str)))\n", "(H, W, h, w) = [int(x) for x in input().split(' ')]\nif W % w != 0:\n\tr = W % w\n\tn = int(W / w)\n\tn = n + 1\n\tprint('Yes')\n\tfor i in range(H):\n\t\tfor k in range(W):\n\t\t\tif (k + 1) % w == 0:\n\t\t\t\tprint(-n * (w - 1) - 1, end='')\n\t\t\telse:\n\t\t\t\tprint(n, end='')\n\t\t\tif k == W - 1:\n\t\t\t\tprint()\n\t\t\telse:\n\t\t\t\tprint(end=' ')\nelif H % h != 0:\n\tr = H % h\n\tn = int(H / h)\n\tn = n + 1\n\tprint('Yes')\n\tstore = 0\n\tfor i in range(H):\n\t\tif (i + 1) % h == 0:\n\t\t\tstore = -n * (h - 1) - 1\n\t\telse:\n\t\t\tstore = n\n\t\tfor k in range(W):\n\t\t\tif k == W - 1:\n\t\t\t\tprint(store)\n\t\t\telse:\n\t\t\t\tprint(store, end=' ')\nelse:\n\tprint('No')\n", "(H, W, h, w) = map(int, input().split())\nif (H % h == 0) & (W % w == 0):\n\tprint('No')\n\texit()\nprint('Yes')\nif W % w != 0:\n\tbase = [1000] * (w - 1) + [-1000 * (w - 1) - 1]\n\tcol = []\n\tfor i in range(1 + W // w):\n\t\tcol = col + base\n\tcol = col[:W]\n\tfor i in range(H):\n\t\tprint(' '.join(map(str, col)))\nelse:\n\tbase = [1000] * (h - 1) + [-1000 * (h - 1) - 1]\n\trow = []\n\tfor i in range(1 + H // h):\n\t\trow = row + base\n\trow = row[:H]\n\tfor i in row:\n\t\tcol = [i] * W\n\t\tprint(' '.join(map(str, col)))\n", "min2 = lambda x, y: x if x < y else y\n\ndef solve(H, W, h, w):\n\tif h == 1 and w == 1:\n\t\treturn None\n\tres = [[0] * W for _ in range(H)]\n\tfor i in range(0, W, w):\n\t\tfor j in range(0, H, h):\n\t\t\tres[j][i] = 10 ** 9 - 1\n\t\t\tif i + w - 1 < W and j + h - 1 < H:\n\t\t\t\tres[j + h - 1][i + w - 1] = -10 ** 9\n\ts = sum((sum(l) for l in res))\n\tif s <= 0:\n\t\treturn None\n\telse:\n\t\treturn res\n(H, W, h, w) = map(int, input().split())\nres = solve(H, W, h, w)\nif res:\n\tprint('Yes')\n\tprint('\\n'.join((' '.join(map(str, l)) for l in res)))\nelse:\n\tprint('No')\n", "(H, W, h, w) = map(int, input().split())\nif h == w == 1:\n\tprint('No')\nelse:\n\ta = (10 ** 9 - 1) // (h * w - 1)\n\tret = [[a] * W for _ in range(H)]\n\tfor y in range(h - 1, H, h):\n\t\tfor x in range(w - 1, W, w):\n\t\t\tret[y][x] = -a * (h * w - 1) - 1\n\ts = 0\n\tfor y in range(H):\n\t\ts += sum(ret[y])\n\tif s > 0:\n\t\tprint('Yes')\n\t\tfor r in ret:\n\t\t\tprint(*r)\n\telse:\n\t\tprint('No')\n", "(h, w, hh, ww) = [int(i) for i in input().split()]\narea = [h * w, hh * ww]\nm = h // hh * (w // ww)\na_inv = area[0] / m - area[1]\nif a_inv <= 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\ta = a_inv ** (-1)\n\tif int(a) < a:\n\t\ta = int(a) + 1\n\telse:\n\t\ta = int(a)\n\tb = (area[1] - 1) * a + 1\n\twhile b >= (area[0] / m - 1) * a:\n\t\ta += 1\n\t\tb = (area[1] - 1) * a + 1\n\ta = str(a)\n\tb = str(-b)\n\tfor i in range(h):\n\t\tret = [None] * w\n\t\tfor j in range(w):\n\t\t\tif (i + 1) % hh == 0 and (j + 1) % ww == 0:\n\t\t\t\tret[j] = b\n\t\t\telse:\n\t\t\t\tret[j] = a\n\t\tprint(' '.join(ret))\n", "from collections import defaultdict, deque\nimport sys, heapq, bisect, math, itertools, string, queue, datetime\nsys.setrecursionlimit(10 ** 8)\nINF = float('inf')\nmod = 10 ** 9 + 7\neps = 10 ** (-7)\n\ndef inpl():\n\treturn list(map(int, input().split()))\n\ndef inpls():\n\treturn list(input().split())\n(H, W, h, w) = inpl()\nMAP = [[0] * W for i in range(H)]\npl = mn = 0\ntmp = 0\nfor y in range(H):\n\tfor x in range(W):\n\t\tif (y + 1) % h == 0 and (x + 1) % w == 0:\n\t\t\tMAP[y][x] -= (h * w - 1) * 1000 + 1\n\t\t\tmn += 1\n\t\t\ttmp -= (h * w - 1) * 1000 + 1\n\t\telse:\n\t\t\tMAP[y][x] = 1000\n\t\t\tpl += 1\n\t\t\ttmp += 1000\nif tmp <= 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tfor m in MAP:\n\t\tprint(' '.join(map(str, m)))\n", "def compose(W, w):\n\tA = [0] * W\n\tS = [0] * (W + 1)\n\tS[W % w] = 1000\n\tfor j in range(W - w + 1):\n\t\tS[j + w] = S[j] - 1\n\tfor j in range(W):\n\t\tA[j] = S[j + 1] - S[j]\n\treturn A\n(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tif W % w:\n\t\tS = compose(W, w)\n\t\tfor _ in range(H):\n\t\t\tprint(*S)\n\telse:\n\t\tS = compose(H, h)\n\t\tfor i in range(H):\n\t\t\tprint(*[S[i] for _ in range(W)])\n", "import sys\n\ndef read_int_list():\n\treturn list(map(int, input().split()))\n\ndef read_int():\n\treturn int(input())\n\ndef read_str_list():\n\treturn input().split()\n\ndef read_str():\n\treturn input()\n(H, W, h, w) = read_int_list()\n\ndef solve(H, W, h, w):\n\tif H % h == 0 and W % w == 0:\n\t\treturn (False, None)\n\ta = [[0] * W for _ in range(H)]\n\tm = 10 ** 9 - 1\n\tM = m + 1\n\tfor i in range(0, H, h):\n\t\tfor j in range(0, W, w):\n\t\t\ta[i][j] = m\n\tfor i in range(h - 1, H, h):\n\t\tfor j in range(w - 1, W, w):\n\t\t\ta[i][j] = -M\n\treturn (True, a)\n(possible, res) = solve(H, W, h, w)\nif possible:\n\tprint('Yes')\n\tfor row in res:\n\t\tprint(' '.join(map(str, row)))\nelse:\n\tprint('No')\n", "(H, W, h, w) = map(int, input().split())\nrem = H * W - (H - H % h) * (W - W % w)\nif rem == 0:\n\tprint('No')\n\texit()\nx = (H // h * W // w + rem) // rem\nif abs(x) > 10 ** 9 or abs(-(h * w - 1) * x - 1) > 10 ** 9:\n\tprint('No')\n\texit()\nprint('Yes')\na = [[x] * W for _ in range(H)]\nfor i in range(h - 1, H, h):\n\tfor j in range(w - 1, W, w):\n\t\ta[i][j] = -(h * w - 1) * x - 1\nfor row in a:\n\tprint(*row)\n", "import sys\ninput = sys.stdin.readline\n\ndef inpl():\n\treturn list(map(int, input().split()))\n\ndef solve():\n\t(H, W, h, w) = inpl()\n\tif H % h == 0 and W % w == 0:\n\t\tprint('No')\n\t\treturn -1\n\tans = [[1000] * W for _ in range(H)]\n\tcnt = 0\n\tfor i in range(h - 1, H, h):\n\t\tfor j in range(w - 1, W, w):\n\t\t\tans[i][j] = -(h * w - 1) * 1000 - 1\n\t\t\tcnt += 1\n\tprint('Yes')\n\tfor row in ans:\n\t\tprint(' '.join(map(str, row)))\n\treturn 0\nsolve()\n", "(H, W, h, w) = map(int, input().split())\ngrid = [[0] * W for _ in range(H)]\ninf = 10 ** 9\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i % h == h - 1 and j % w == w - 1:\n\t\t\tgrid[i][j] = -inf\n\t\telif i % h == 0 and j % w == 0:\n\t\t\tgrid[i][j] = inf - 1\nif sum([sum(line) for line in grid]) > 0:\n\tprint('Yes')\n\tfor i in range(H):\n\t\tprint(*grid[i])\nelse:\n\tprint('No')\n", "from collections import defaultdict, deque\nfrom heapq import heappush, heappop\nimport sys\nimport math\nimport bisect\nimport random\n\ndef LI():\n\treturn [int(x) for x in sys.stdin.readline().split()]\n\ndef I():\n\treturn int(sys.stdin.readline())\n\ndef LS():\n\treturn [list(x) for x in sys.stdin.readline().split()]\n\ndef S():\n\tres = list(sys.stdin.readline())\n\tif res[-1] == '\\n':\n\t\treturn res[:-1]\n\treturn res\n\ndef IR(n):\n\treturn [I() for i in range(n)]\n\ndef LIR(n):\n\treturn [LI() for i in range(n)]\n\ndef SR(n):\n\treturn [S() for i in range(n)]\n\ndef LSR(n):\n\treturn [LS() for i in range(n)]\nsys.setrecursionlimit(1000000)\nmod = 1000000007\n\ndef solve():\n\t(H, W, h, w) = LI()\n\tif W % w != 0:\n\t\ts = [0] + [100000] * (w - 1)\n\t\tfor i in range(W - w + 1):\n\t\t\ts.append(s[-w] - 1)\n\t\ta = [s[i] - s[i - 1] for i in range(1, W + 1)]\n\t\tprint('Yes')\n\t\tfor i in range(H):\n\t\t\tprint(*a)\n\telif H % h != 0:\n\t\t(H, W, h, w) = (W, H, w, h)\n\t\ts = [0] + [100000] * (w - 1)\n\t\tfor i in range(W - w + 1):\n\t\t\ts.append(s[-w] - 1)\n\t\ta = [s[i] - s[i - 1] for i in range(1, W + 1)]\n\t\tprint('Yes')\n\t\tans = [[a[i]] * H for i in range(W)]\n\t\tfor i in range(W):\n\t\t\tprint(*ans[i])\n\telse:\n\t\tprint('No')\n\treturn\nsolve()\n", "(H, W, sh, sw) = map(int, input().split())\nif H % sh == 0 and W % sw == 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tstate = [[1] * W for _ in range(H)]\n\tINF = 10 ** 9\n\tfor h in range(H):\n\t\tfor w in range(W):\n\t\t\tif w % sw == sw - 1 and h % sh == sh - 1:\n\t\t\t\tstate[h][w] = -INF\n\t\t\telif w % sw == 0 and h % sh == 0:\n\t\t\t\tstate[h][w] = INF - (sh * sw - 1)\n\tfor h in range(H):\n\t\tprint(' '.join([str(a) for a in state[h]]))\n", "(H, W, h, w) = map(int, input().split())\nif W % w == 0 and H % h == 0:\n\tprint('No')\nelse:\n\tswapped = False\n\tif W % w == 0:\n\t\t(H, W, h, w, swapped) = (W, H, w, h, True)\n\ta = [[0 for _ in range(W)] for _ in range(H)]\n\tfor y in range(H):\n\t\tfor x in range(0, W, w):\n\t\t\ta[y][x] = W\n\t\tfor x in range(w - 1, W, w):\n\t\t\ta[y][x] = -W - 1\n\tif swapped:\n\t\t(H, W, h, w) = (W, H, w, h)\n\t\tb = a\n\t\ta = [[0 for _ in range(W)] for _ in range(H)]\n\t\tfor y in range(H):\n\t\t\tfor x in range(W):\n\t\t\t\ta[y][x] = b[x][y]\n\tprint('Yes')\n\tfor y in range(H):\n\t\tprint(*a[y])\n", "(H, W, h, w) = [int(i) for i in input().split()]\nif H % h == 0 and W % w == 0:\n\tprint('No')\nelif W % w != 0:\n\tprint('Yes')\n\tfor y in range(H):\n\t\tfor x in range(W):\n\t\t\tif x != 0:\n\t\t\t\tprint(' ', end='')\n\t\t\tif x % w != w - 1:\n\t\t\t\tprint(100000, end='')\n\t\t\telse:\n\t\t\t\tprint(-100000 * (w - 1) - 1, end='')\n\t\tprint()\nelse:\n\tprint('Yes')\n\tfor y in range(H):\n\t\tfor x in range(W):\n\t\t\tif x != 0:\n\t\t\t\tprint(' ', end='')\n\t\t\tif y % h != h - 1:\n\t\t\t\tprint(100000, end='')\n\t\t\telse:\n\t\t\t\tprint(-100000 * (h - 1) - 1, end='')\n\t\tprint()\n", "(H, W, h, w) = map(int, input().split())\nif not (H % h or W % w):\n\tprint('No')\n\texit()\nif H % h:\n\tflg = 'tate'\n\tn = H\n\tr = h\nelse:\n\tflg = 'yoko'\n\tn = W\n\tr = w\nans = []\nif r % 2 == 0:\n\ts = r // 2\n\tfor i in range(n):\n\t\tif i // s % 2 == 0:\n\t\t\tans.append(2000)\n\t\telse:\n\t\t\tans.append(-2001)\nelse:\n\tfor i in range(n):\n\t\tif i % r < r // 2 + 1:\n\t\t\tans.append(2000)\n\t\telse:\n\t\t\tans.append(-int(2000 / (r // 2) * (r // 2 + 1)) - 1)\nprint('Yes')\nif flg == 'tate':\n\tfor i in range(H):\n\t\tprint(*[ans[i]] * W)\nelse:\n\tfor i in range(H):\n\t\tprint(*ans)\n", "import sys\ninput = sys.stdin.readline\n\ndef main():\n\t(H, W, h, w) = map(int, input().split())\n\tif H * W - H // h * (W // w) * w * h == 0:\n\t\tprint('No')\n\telif W % w != 0:\n\t\tans = [0 for _ in range(W)]\n\t\tco = [0 for _ in range(W + 1)]\n\t\tfor i in range(1, w):\n\t\t\tco[i] = (W - i) // w + 1\n\t\tfor i in range(w, W + 1):\n\t\t\tco[i] = co[i - w] - 1\n\t\tfor i in range(W):\n\t\t\tans[i] = co[i + 1] - co[i]\n\t\tprint('Yes')\n\t\tfor i in range(H):\n\t\t\tprint(*ans)\n\telse:\n\t\tans = [0 for _ in range(H)]\n\t\tco = [0 for _ in range(H + 1)]\n\t\tfor i in range(1, h):\n\t\t\tco[i] = (H - i) // h + 1\n\t\tfor i in range(h, H + 1):\n\t\t\tco[i] = co[i - h] - 1\n\t\tfor i in range(H):\n\t\t\tans[i] = co[i + 1] - co[i]\n\t\tprint('Yes')\n\t\tfor i in range(H):\n\t\t\tprint(*list((ans[i] for _ in range(W))))\nmain()\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\n\texit(0)\nblocks = H // h * (W // w)\nleft = H * W - blocks * h * w\noffset = blocks // left + 1\nv = [offset, -offset * (h * w - 1) - 1]\nprint('Yes')\nfor i in range(H):\n\ta = []\n\tfor j in range(W):\n\t\ta.append(v[1 if i % h == h - 1 and j % w == w - 1 else 0])\n\tprint(' '.join(list(map(str, a))))\n", "(H, W, h, w) = map(int, input().split())\nif H % h == 0 and W % w == 0:\n\tprint('No')\nelse:\n\tc = 10 ** 9\n\tans = [[(c - 1) // (h * w - 1) for i in range(W)] for j in range(H)]\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\tif (i + 1) % h == 0 and (j + 1) % w == 0:\n\t\t\t\tans[i][j] = -c\n\tif sum((ans[i][j] for i in range(H) for j in range(W))) > 0:\n\t\tprint('Yes')\n\t\tfor i in range(H):\n\t\t\tprint(*ans[i])\n\telse:\n\t\tprint('No')\n", "(H, W, h, w) = map(int, input().split())\na = [[0] * W for i in range(H)]\nINF = 10 ** 9\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i % h == h - 1 and j % w == w - 1:\n\t\t\ta[i][j] = -INF\n\t\telif i % h == 0 and j % w == 0:\n\t\t\ta[i][j] = INF - 1\nif sum([sum(line) for line in a]) > 0:\n\tprint('Yes')\n\tfor i in range(H):\n\t\tprint(*a[i])\nelse:\n\tprint('No')\n", "(H, W, a, b) = map(int, input().split())\nif H % a or W % b:\n\tprint('Yes')\n\tk = H // a * (W // b)\n\tx = k + 2\n\tansss = [[0] * W for _ in range(H)]\n\tfor i in range(H // a):\n\t\tfor j in range(W // b):\n\t\t\tansss[(i + 1) * a - 1][(j + 1) * b - 1] = -x\n\tfor i in range(-(-H // a)):\n\t\tfor j in range(-(-W // b)):\n\t\t\tansss[i * a][j * b] = x - 1\n\tprint('\\n'.join([' '.join(map(str, anss)) for anss in ansss]))\nelse:\n\tprint('No')\n", "def get_1d(H, h):\n\tret = [0] * (H + 1)\n\tfor s in range(h):\n\t\tfor (x, i) in enumerate(range(s, H, h)):\n\t\t\tret[i] = -x\n\tfor (x, i) in enumerate(range(H, 0, -h)):\n\t\tret[i] = x + 1\n\treturn [x1 - x0 for (x0, x1) in zip(ret, ret[1:])]\n\ndef solve(H, W, h, w):\n\tif H % h == 0 and W % w == 0:\n\t\treturn False\n\tans = []\n\tif H % h > 0:\n\t\tcol = get_1d(H, h)\n\t\tans.extend(([x] * W for x in col))\n\telse:\n\t\trow = get_1d(W, w)\n\t\tans.extend([row] * H)\n\treturn ans\n(H, W, h, w) = map(int, input().split())\nans = solve(H, W, h, w)\nif ans == False:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tfor row in ans:\n\t\tprint(*row)\n", "import sys\ninput = sys.stdin.readline\nsys.setrecursionlimit(pow(10, 6))\n\ndef main():\n\t(H, W, h, w) = map(int, input().split())\n\tif H % h == 0 and W % w == 0:\n\t\tprint('No')\n\telif H % h == 0:\n\t\tprint('Yes')\n\t\tans = [[0 for _ in range(W)] for _ in range(H)]\n\t\tfor i in range(H):\n\t\t\tfor j in range(0, W, w):\n\t\t\t\tans[i][j] = 99999\n\t\t\t\tif j + w - 1 < W:\n\t\t\t\t\tans[i][j + w - 1] = -100000\n\t\tfor a in ans:\n\t\t\tprint(*a)\n\telse:\n\t\tprint('Yes')\n\t\tans = [[0 for _ in range(W)] for _ in range(H)]\n\t\tfor i in range(W):\n\t\t\tfor j in range(0, H, h):\n\t\t\t\tans[j][i] = 99999\n\t\t\t\tif j + h - 1 < H:\n\t\t\t\t\tans[j + h - 1][i] = -100000\n\t\tfor a in ans:\n\t\t\tprint(*a)\nmain()\n", "import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools\nsys.setrecursionlimit(10 ** 7)\ninf = 10 ** 20\nmod = 10 ** 9 + 7\n\ndef LI():\n\treturn [int(x) for x in sys.stdin.readline().split()]\n\ndef LI_():\n\treturn [int(x) - 1 for x in sys.stdin.readline().split()]\n\ndef LF():\n\treturn [float(x) for x in sys.stdin.readline().split()]\n\ndef LS():\n\treturn sys.stdin.readline().split()\n\ndef I():\n\treturn int(sys.stdin.readline())\n\ndef F():\n\treturn float(sys.stdin.readline())\n\ndef S():\n\treturn input()\n\ndef main():\n\t(H, W, h, w) = LI()\n\tf = False\n\tif H % h == 0 and W % w == 0:\n\t\treturn 'No'\n\tif W % w == 0:\n\t\t(H, W, h, w) = (W, H, w, h)\n\t\tf = True\n\tp = 10 ** 6 * (w - 1) - 1\n\tm = -10 ** 6\n\ta = []\n\tfor i in range(W):\n\t\tif i % w == 0:\n\t\t\ta.append(p)\n\t\telse:\n\t\t\ta.append(m)\n\taa = [a] * H\n\tr = aa\n\tif f:\n\t\tr = [[aa[i][j] for i in range(H)] for j in range(W)]\n\treturn 'Yes\\n' + '\\n'.join((' '.join(map(str, t)) for t in r))\nprint(main())\n", "(h, w, h0, w0) = map(int, input().split())\nif h0 == w0 == 1:\n\tprint('No')\n\texit()\n(x, y) = (h // h0, w // w0)\na1cnt = h0 * w0 - 1\n(a1sum, a2sum) = (h * w - x * y, x * y)\na1 = (pow(10, 9) - 1) // a1cnt\na2 = -(a1 * a1cnt + 1)\nasum = a1 * a1sum + a2 * a2sum\nprint('Yes' if asum > 0 else 'No')\nif asum > 0:\n\tfor i in range(1, h + 1):\n\t\ta = [0] * w\n\t\tfor j in range(1, w + 1):\n\t\t\ta[j - 1] = a2 if i % h0 == j % w0 == 0 else a1\n\t\tprint(*a)\n", "import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time\nsys.setrecursionlimit(10 ** 7)\nINF = 10 ** 20\nMOD = 10 ** 9 + 7\n\ndef II():\n\treturn int(input())\n\ndef ILI():\n\treturn list(map(int, input().split()))\n\ndef IAI(LINE):\n\treturn [ILI() for __ in range(LINE)]\n\ndef IDI():\n\treturn {key: value for (key, value) in ILI()}\n\ndef read():\n\t(H, W, h, w) = ILI()\n\treturn (H, W, h, w)\n\ndef solve(H, W, h, w):\n\tif H % h == 0 and W % w == 0:\n\t\treturn (False, None)\n\telse:\n\t\tmatrix = [[10 ** 3] * W for __ in range(H)]\n\t\tval = -(h * w * 1000) + 999\n\t\tfor _h in range(h - 1, H, h):\n\t\t\tfor _w in range(w - 1, W, w):\n\t\t\t\tmatrix[_h][_w] = val\n\treturn (True, matrix)\n\ndef main():\n\tparams = read()\n\t(ans_bool, matrix) = solve(*params)\n\tif ans_bool:\n\t\tprint('Yes')\n\t\tfor row in matrix:\n\t\t\tprint(' '.join(map(str, row)))\n\telse:\n\t\tprint('No')\nmain()\n", "import sys\n\ndef MI():\n\treturn map(int, sys.stdin.readline().rstrip().split())\n(H, W, h, w) = MI()\n(q1, r1) = (H // h, H % h)\n(q2, r2) = (W // w, W % w)\nif r1 == 0 and r2 == 0:\n\tprint('No')\nelse:\n\tprint('Yes')\n\tif r2 != 0:\n\t\tA = []\n\t\tfor _ in range(q2):\n\t\t\tA += [2 * 10 ** 6] * (w - 1) + [-(2 * 10 ** 6) * (w - 1) - 1]\n\t\tA += [2 * 10 ** 6] * r2\n\t\tfor _ in range(H):\n\t\t\tprint(*A)\n\telse:\n\t\tfor i in range(1, H + 1):\n\t\t\tif i % h != 0:\n\t\t\t\tprint(*[2 * 10 ** 6] * W)\n\t\t\telse:\n\t\t\t\tprint(*[-(2 * 10 ** 6) * (h - 1) - 1] * W)\n", "import sys\ntry:\n\tfrom typing import Any, Union, List, Tuple, Dict\nexcept ImportError:\n\tpass\n\ndef debug(*args):\n\tprint(*args, file=sys.stderr)\n\ndef exit():\n\tsys.exit(0)\n(H, W, h, w) = map(int, input().split())\n(yes, no) = ('Yes', 'No')\nif H % h == 0 and W % w == 0:\n\tprint(no)\n\texit()\nprint(yes)\nunit = 1000\nif W % w != 0:\n\tfor i in range(H):\n\t\tl = []\n\t\tfor j in range(W):\n\t\t\tif j % w == w - 1:\n\t\t\t\tl.append(str(-unit * (w - 1) - 1))\n\t\t\telse:\n\t\t\t\tl.append(str(unit))\n\t\tprint(' '.join(l))\n\texit()\nif H % h != 0:\n\tfor i in range(H):\n\t\tif i % h == h - 1:\n\t\t\tl = [str(-unit * (h - 1) - 1)] * W\n\t\telse:\n\t\t\tl = [str(unit)] * W\n\t\tprint(' '.join(l))\n\texit()\nraise Exception('hogeeee')\n"]

name: AtCoder Grand Contest 016 - +/- Rectangle

source: atcoder

time_limit: 2.0 seconds

memory_limit: 256.0 megabytes

raw_problem:
配点 : <var>700</var> 点

問題文

整数 <var>H</var>, <var>W</var>, <var>h</var>, <var>w</var> (<var>1 ≤ h ≤ H</var>, <var>1 ≤ w ≤ W</var>) が与えられます。
次の条件がすべて成り立つような行列が存在するか判定し、存在するならばひとつ構成してください。

行列は <var>H</var> 行 <var>W</var> 列である。

行列の各要素は <var>-10^9</var> 以上 <var>10^9</var> 以下の整数である。

行列の全要素の総和は正の値である。

どこから <var>h</var> 行 <var>w</var> 列の部分長方形を取り出しても、部分長方形に含まれる全要素の総和は負の値である。

制約

<var>1 ≤ h ≤ H ≤ 500</var>

<var>1 ≤ w ≤ W ≤ 500</var>

入力

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

<var>H</var> <var>W</var> <var>h</var> <var>w</var>

出力

条件がすべて成り立つような行列が存在しないならば、No を出力せよ。

存在するならば、<var>1</var> 行目に Yes を出力し、<var>2</var> 行目以降に行列をひとつ出力せよ。
行列は以下の形式で出力せよ。
ただし、<var>a_{ij}</var> は行列の <var>(i,\ j)</var> 要素を表す。

<var>a_{11}</var> <var>...</var> <var>a_{1W}</var>
<var>:</var>
<var>a_{H1}</var> <var>...</var> <var>a_{HW}</var>

入力例 1

3 3 2 2

出力例 1

Yes
1 1 1
1 -4 1
1 1 1

行列の全要素の総和は <var>4</var> であり、正の値です。
また、部分長方形を取り出す方法は次図の <var>4</var> 通りですが、どの場合も、部分長方形に含まれる全要素の総和は <var>-1</var> であり、負の値です。

入力例 2

2 4 1 2

出力例 2

No

入力例 3

3 4 2 3

出力例 3

Yes
2 -5 8 7
3 -5 -4 -5
2 1 -1 7

Score : <var>700</var> points

Problem Statement

You are given four integers: <var>H</var>, <var>W</var>, <var>h</var> and <var>w</var> (<var>1 ≤ h ≤ H</var>, <var>1 ≤ w ≤ W</var>).
Determine whether there exists a matrix such that all of the following conditions are held, and construct one such matrix if the answer is positive:

The matrix has <var>H</var> rows and <var>W</var> columns.

Each element of the matrix is an integer between <var>-10^9</var> and <var>10^9</var> (inclusive).

The sum of all the elements of the matrix is positive.

The sum of all the elements within every subrectangle with <var>h</var> rows and <var>w</var> columns in the matrix is negative.

Constraints

<var>1 ≤ h ≤ H ≤ 500</var>

<var>1 ≤ w ≤ W ≤ 500</var>

Input

Input is given from Standard Input in the following format:

<var>H</var> <var>W</var> <var>h</var> <var>w</var>

Output

If there does not exist a matrix that satisfies all of the conditions, print No.

Otherwise, print Yes in the first line, and print a matrix in the subsequent lines in the following format:

<var>a_{11}</var> <var>...</var> <var>a_{1W}</var>
<var>:</var>
<var>a_{H1}</var> <var>...</var> <var>a_{HW}</var>

Here, <var>a_{ij}</var> represents the <var>(i,\ j)</var> element of the matrix.

Sample Input 1

3 3 2 2

Sample Output 1

Yes
1 1 1
1 -4 1
1 1 1

The sum of all the elements of this matrix is <var>4</var>, which is positive.
Also, in this matrix, there are four subrectangles with <var>2</var> rows and <var>2</var> columns as shown below. For each of them, the sum of all the elements inside is <var>-1</var>, which is negative.

Sample Input 2

2 4 1 2

Sample Output 2

No

Sample Input 3

3 4 2 3

Sample Output 3

Yes
2 -5 8 7
3 -5 -4 -5
2 1 -1 7

question:
You are given four integers: $H$, $W$, $h$ and $w$ ($1 ≤ h ≤ H$, $1 ≤ w ≤ W$).
Determine whether there exists a matrix such that all of the following conditions are held, and construct one such matrix if the answer is positive:

- The matrix has $H$ rows and $W$ columns.
- Each element of the matrix is an integer between $-10^9$ and $10^9$ (inclusive).
- The sum of all the elements of the matrix is positive.
- The sum of all the elements within every subrectangle with $h$ rows and $w$ columns in the matrix is negative.

Constraints

- $1 ≤ h ≤ H ≤ 500$
- $1 ≤ w ≤ W ≤ 500$

Input
Input is given from Standard Input in the following format:
$H$ $W$ $h$ $w$

Output
If there does not exist a matrix that satisfies all of the conditions, print No.
Otherwise, print Yes in the first line, and print a matrix in the subsequent lines in the following format:
$a_{11}$ $...$ $a_{1W}$

$:$

$a_{H1}$ $...$ $a_{HW}$

Here, $a_{ij}$ represents the $(i,\ j)$ element of the matrix.

Sample Input 1
3 3 2 2

Sample Output 1
Yes
1 1 1
1 -4 1
1 1 1

The sum of all the elements of this matrix is $4$, which is positive.
Also, in this matrix, there are four subrectangles with $2$ rows and $2$ columns as shown below. For each of them, the sum of all the elements inside is $-1$, which is negative.

![image](1.png)

Sample Input 2
2 4 1 2

Sample Output 2
No

Sample Input 3
3 4 2 3

Sample Output 3
Yes
2 -5 8 7
3 -5 -4 -5
2 1 -1 7

data_split: test


F. RC Kaboom Show

problem_index: F

time_limit: 6 seconds

memory_limit: 256 megabytes

note:
Here is the picture for the first example:
![image](images/cf_1359_F/1.png)
The fastest cars to crash are cars $$$2$$$ and $$$4$$$. Let's launch car $$$2$$$ at $$$0$$$, car $$$4$$$ at about $$$0.096762$$$ and cars $$$1$$$ and $$$3$$$ at arbitrary time. That way cars $$$2$$$ and $$$4$$$ will crash into each other at about $$$0.585902$$$. So here's what it looks like at the moment of the collision:
![image](images/cf_1359_F/2.png)
Here's the picture for the second example:
![image](images/cf_1359_F/3.png)

source: codeforces

raw_problem:
F. RC Kaboom Show

time limit per test
6 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You know, it's hard to conduct a show with lots of participants and spectators at the same place nowadays. Still, you are not giving up on your dream to make a car crash showcase! You decided to replace the real cars with remote controlled ones, call the event "Remote Control Kaboom Show" and stream everything online.

For the preparation you arranged an arena — an infinite 2D-field. You also bought $$$n$$$ remote controlled cars and set them up on the arena. Unfortunately, the cars you bought can only go forward without turning left, right or around. So you additionally put the cars in the direction you want them to go.

To be formal, for each car $$$i$$$ ($$$1 \le i \le n$$$) you chose its initial position ($$$x_i, y_i$$$) and a direction vector ($$$dx_i, dy_i$$$). Moreover, each car has a constant speed $$$s_i$$$ units per second. So after car $$$i$$$ is launched, it stars moving from ($$$x_i, y_i$$$) in the direction ($$$dx_i, dy_i$$$) with constant speed $$$s_i$$$.

The goal of the show is to create a car collision as fast as possible! You noted that launching every car at the beginning of the show often fails to produce any collisions at all. Thus, you plan to launch the $$$i$$$-th car at some moment $$$t_i$$$. You haven't chosen $$$t_i$$$, that's yet to be decided. Note that it's not necessary for $$$t_i$$$ to be integer and $$$t_i$$$ is allowed to be equal to $$$t_j$$$ for any $$$i, j$$$.

The show starts at time $$$0$$$. The show ends when two cars $$$i$$$ and $$$j$$$ ($$$i \ne j$$$) collide (i. e. come to the same coordinate at the same time). The duration of the show is the time between the start and the end.

What's the fastest crash you can arrange by choosing all $$$t_i$$$? If it's possible to arrange a crash then print the shortest possible duration of the show. Otherwise, report that it's impossible.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 25000$$$) — the number of cars.

Each of the next $$$n$$$ lines contains five integers $$$x_i$$$, $$$y_i$$$, $$$dx_i$$$, $$$dy_i$$$, $$$s_i$$$ ($$$-10^3 \le x_i, y_i \le 10^3$$$; $$$1 \le |dx_i| \le 10^3$$$; $$$1 \le |dy_i| \le 10^3$$$; $$$1 \le s_i \le 10^3$$$) — the initial position of the $$$i$$$-th car, its direction vector and its speed, respectively.

It's guaranteed that all cars start at distinct positions (i. e. $$$(x_i, y_i) \neq (x_j, y_j)$$$ for $$$i \neq j$$$).

Output

Print the shortest possible duration of the show if it's possible to arrange a crash by choosing all $$$t_i$$$. Otherwise, print "No show :(".

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Examples

Input

4
3 -1 -1 1 2
2 3 -3 -2 10
-4 2 1 -2 1
-2 -2 -1 2 4

Output

0.585902082262898

Input

2
-1 1 -1 1 200
1 1 1 5 200

Output

No show :(

Note

Here is the picture for the first example:

The fastest cars to crash are cars $$$2$$$ and $$$4$$$. Let's launch car $$$2$$$ at $$$0$$$, car $$$4$$$ at about $$$0.096762$$$ and cars $$$1$$$ and $$$3$$$ at arbitrary time. That way cars $$$2$$$ and $$$4$$$ will crash into each other at about $$$0.585902$$$. So here's what it looks like at the moment of the collision:

Here's the picture for the second example:

question:
You know, it's hard to conduct a show with lots of participants and spectators at the same place nowadays. Still, you are not giving up on your dream to make a car crash showcase! You decided to replace the real cars with remote controlled ones, call the event "Remote Control Kaboom Show" and stream everything online.
For the preparation you arranged an arena — an infinite 2D-field. You also bought $$$n$$$ remote controlled cars and set them up on the arena. Unfortunately, the cars you bought can only go forward without turning left, right or around. So you additionally put the cars in the direction you want them to go.
To be formal, for each car $$$i$$$ ($$$1 \le i \le n$$$) you chose its initial position ($$$x_i, y_i$$$) and a direction vector ($$$dx_i, dy_i$$$). Moreover, each car has a constant speed $$$s_i$$$ units per second. So after car $$$i$$$ is launched, it stars moving from ($$$x_i, y_i$$$) in the direction ($$$dx_i, dy_i$$$) with constant speed $$$s_i$$$.
The goal of the show is to create a car collision as fast as possible! You noted that launching every car at the beginning of the show often fails to produce any collisions at all. Thus, you plan to launch the $$$i$$$-th car at some moment $$$t_i$$$. You haven't chosen $$$t_i$$$, that's yet to be decided. Note that it's not necessary for $$$t_i$$$ to be integer and $$$t_i$$$ is allowed to be equal to $$$t_j$$$ for any $$$i, j$$$.
The show starts at time $$$0$$$. The show ends when two cars $$$i$$$ and $$$j$$$ ($$$i \ne j$$$) collide (i. e. come to the same coordinate at the same time). The duration of the show is the time between the start and the end.
What's the fastest crash you can arrange by choosing all $$$t_i$$$? If it's possible to arrange a crash then print the shortest possible duration of the show. Otherwise, report that it's impossible.

Input
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 25000$$$) — the number of cars.
Each of the next $$$n$$$ lines contains five integers $$$x_i$$$, $$$y_i$$$, $$$dx_i$$$, $$$dy_i$$$, $$$s_i$$$ ($$$-10^3 \le x_i, y_i \le 10^3$$$; $$$1 \le |dx_i| \le 10^3$$$; $$$1 \le |dy_i| \le 10^3$$$; $$$1 \le s_i \le 10^3$$$) — the initial position of the $$$i$$$-th car, its direction vector and its speed, respectively.
It's guaranteed that all cars start at distinct positions (i. e. $$$(x_i, y_i) \neq (x_j, y_j)$$$ for $$$i \neq j$$$).

Output
Print the shortest possible duration of the show if it's possible to arrange a crash by choosing all $$$t_i$$$. Otherwise, print "No show :(".
Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Examples
Input
4
3 -1 -1 1 2
2 3 -3 -2 10
-4 2 1 -2 1
-2 -2 -1 2 4

Output
0.585902082262898

Input
2
-1 1 -1 1 200
1 1 1 5 200

Output
No show :(

Note
Here is the picture for the first example:
 ![image](1.png) The fastest cars to crash are cars $$$2$$$ and $$$4$$$. Let's launch car $$$2$$$ at $$$0$$$, car $$$4$$$ at about $$$0.096762$$$ and cars $$$1$$$ and $$$3$$$ at arbitrary time. That way cars $$$2$$$ and $$$4$$$ will crash into each other at about $$$0.585902$$$. So here's what it looks like at the moment of the collision:
 ![image](2.png) Here's the picture for the second example:
 ![image](3.png)

tags: ['Geometry', 'Sorting', 'Complete search', 'Mathematics', 'Data structures']

skill_types: ['Sorting', 'Data structures', 'Complete search']

raw_tags: ['data structures', 'geometry', 'math', 'binary search', 'brute force']

image_tags:
2D Geometry
2D Geometry
2D Geometry

data_split: test


Dice Room

source: ACM-ICPC Japan Alumni Group Practice Contest for Asia Regionals 2010

raw_problem:
Problem D: Dice Room

You are playing a popular video game which is famous for its depthful story and interesting
puzzles. In the game you were locked in a mysterious house alone and there is no way to call for
help, so you have to escape on yours own. However, almost every room in the house has some
kind of puzzles and you cannot move to neighboring room without solving them.

One of the puzzles you encountered in the house is following. In a room, there was a device
which looked just like a dice and laid on a table in the center of the room. Direction was written
on the wall. It read:

      "This cube is a remote controller and you can manipulate a remote room, Dice
      Room, by it. The room has also a cubic shape whose surfaces are made up of 3x3
      unit squares and some squares have a hole on them large enough for you to go though
      it. You can rotate this cube so that in the middle of rotation at least one edge always
      touch the table, that is, to 4 directions. Rotating this cube affects the remote room
      in the same way and positions of holes on the room change. To get through the
      room, you should have holes on at least one of lower three squares on the front and
      back side of the room."

You can see current positions of holes by a monitor. Before going to Dice Room, you should
rotate the cube so that you can go though the room. But you know rotating a room takes some
time and you don’t have much time, so you should minimize the number of rotation. How many
rotations do you need to make it possible to get though Dice Room?

Input

The input consists of several datasets. Each dataset contains 6 tables of 3x3 characters which
describe the initial position of holes on each side. Each character is either '*' or '.'. A hole is
indicated by '*'. The order which six sides appears in is: front, right, back, left, top, bottom.
The order and orientation of them are described by this development view:

Figure 4: Dice Room

Figure 5: available dice rotations

There is a blank line after each dataset. The end of the input is indicated by a single '#'.

Output

Print the minimum number of rotations needed in a line for each dataset. You may assume all
datasets have a solution.

Sample Input

...
...
.*.
...
...
.*.
...
...
...
...
...
.*.
...
...
.*.
...
...
...

...
.*.
...
*..
...
..*
*.*
*.*
*.*
*.*
.*.
*.*
*..
.*.
..*
*.*
...
*.*

...
.*.
.*.
...
.**
*..
...
...
.*.
.*.
...
*..
..*
...
.**
...
*..
...

#

Output for the Sample Input

3
1
0

source: aizu

question:
Problem D: Dice Room

You are playing a popular video game which is famous for its depthful story and interesting
puzzles. In the game you were locked in a mysterious house alone and there is no way to call for
help, so you have to escape on yours own. However, almost every room in the house has some
kind of puzzles and you cannot move to neighboring room without solving them.

One of the puzzles you encountered in the house is following. In a room, there was a device
which looked just like a dice and laid on a table in the center of the room. Direction was written
on the wall. It read:

      "This cube is a remote controller and you can manipulate a remote room, Dice
      Room, by it. The room has also a cubic shape whose surfaces are made up of 3x3
      unit squares and some squares have a hole on them large enough for you to go though
      it. You can rotate this cube so that in the middle of rotation at least one edge always
      touch the table, that is, to 4 directions. Rotating this cube affects the remote room
      in the same way and positions of holes on the room change. To get through the
      room, you should have holes on at least one of lower three squares on the front and
      back side of the room."

You can see current positions of holes by a monitor. Before going to Dice Room, you should
rotate the cube so that you can go though the room. But you know rotating a room takes some
time and you don’t have much time, so you should minimize the number of rotation. How many
rotations do you need to make it possible to get though Dice Room?

Input

The input consists of several datasets. Each dataset contains 6 tables of 3x3 characters which
describe the initial position of holes on each side. Each character is either '*' or '.'. A hole is
indicated by '*'. The order which six sides appears in is: front, right, back, left, top, bottom.
The order and orientation of them are described by this development view:

![image](1.png)

Figure 4: Dice Room

![image](2.png)

Figure 5: available dice rotations

![image](3.png)

There is a blank line after each dataset. The end of the input is indicated by a single '#'.

Output

Print the minimum number of rotations needed in a line for each dataset. You may assume all
datasets have a solution.

Sample Input

...
...
.*.
...
...
.*.
...
...
...
...
...
.*.
...
...
.*.
...
...
...

...
.*.
...
*..
...
..*
*.*
*.*
*.*
*.*
.*.
*.*
*..
.*.
..*
*.*
...
*.*

...
.*.
.*.
...
.**
*..
...
...
.*.
.*.
...
*..
..*
...
.**
...
*..
...

#

Output for the Sample Input

3
1
0

image_tags:
3D Geometry
3D Geometry
3D Geometry

data_split: test


F. Caterpillar

problem_index: F

time_limit: 2 seconds

memory_limit: 256 megabytes

source: codeforces

raw_problem:
F. Caterpillar

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

An undirected graph is called a caterpillar if it is a connected graph without cycles and it has such a path p that any vertex is located at a distance of at most 1 from the path p. The caterpillar can contain loops (edges from a vertex to itself) but cannot contain multiple (parallel) edges.

The picture contains an example of a caterpillar:

You are given an undirected graph G. You are allowed to do a merging operations, each such operation merges two vertices into one vertex. For that two any vertices a and b (a ≠ b) are chosen. These verteces are deleted together with their edges (which are incident to at least one of the vertices a or b) but a new vertex w is added together with edges (x, w) for each edge (a, w) and/or (b, w). If there was the edge (a, b) it transforms to the loop (w, w). The resulting graph (after the merging operation) may contain multiple (parallel) edges between pairs of vertices and loops. Let us note that this operation decreases the number of vertices of graph by 1 but leaves the number of edges in the graph unchanged.

The merging operation can be informally described as a unity of two vertices of the graph into one with the natural transformation of the graph edges.

You may apply this operation consecutively and make the given graph to be a caterpillar. Write a program that will print the minimal number of merging operations required to make the given graph a caterpillar.

Input

The first line contains a pair of integers n, m (1 ≤ n ≤ 2000;0 ≤ m ≤ 105), where n represents the number of vertices in the graph and m is the number of edges in it. Then the following m lines contain edge descriptions, one edge description per line. Every line contains a pair of integers ai, bi (1 ≤ ai, bi ≤ n;ai ≠ bi), ai, bi which represent the indices of the vertices connected by the edge. The vertices are numbered from 1 to n. In the given graph it will be no more than one edge between any pair of vertices. The given graph is not necessarily connected.

Output

Print the minimal required number of operations.

Examples

Input

4 4
1 2
2 3
3 4
4 2

Output

2

Input

6 3
1 2
3 4
5 6

Output

2

Input

7 6
1 2
2 3
1 4
4 5
1 6
6 7

Output

1

question:
An undirected graph is called a caterpillar if it is a connected graph without cycles and it has such a path p that any vertex is located at a distance of at most 1 from the path p. The caterpillar can contain loops (edges from a vertex to itself) but cannot contain multiple (parallel) edges.
The picture contains an example of a caterpillar:
 ![image](1.png) You are given an undirected graph G. You are allowed to do a merging operations, each such operation merges two vertices into one vertex. For that two any vertices a and b (a ≠ b) are chosen. These verteces are deleted together with their edges (which are incident to at least one of the vertices a or b) but a new vertex w is added together with edges (x, w) for each edge (a, w) and/or (b, w). If there was the edge (a, b) it transforms to the loop (w, w). The resulting graph (after the merging operation) may contain multiple (parallel) edges between pairs of vertices and loops. Let us note that this operation decreases the number of vertices of graph by 1 but leaves the number of edges in the graph unchanged.
The merging operation can be informally described as a unity of two vertices of the graph into one with the natural transformation of the graph edges.
You may apply this operation consecutively and make the given graph to be a caterpillar. Write a program that will print the minimal number of merging operations required to make the given graph a caterpillar.

Input
The first line contains a pair of integers n, m (1 ≤ n ≤ 2000;0 ≤ m ≤ 10^{5}), where n represents the number of vertices in the graph and m is the number of edges in it. Then the following m lines contain edge descriptions, one edge description per line. Every line contains a pair of integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n;a_{i} ≠ b_{i}), a_{i}, b_{i} which represent the indices of the vertices connected by the edge. The vertices are numbered from 1 to n. In the given graph it will be no more than one edge between any pair of vertices. The given graph is not necessarily connected.

Output
Print the minimal required number of operations.

Examples
Input
4 4
1 2
2 3
3 4
4 2

Output
2

Input
6 3
1 2
3 4
5 6

Output
2

Input
7 6
1 2
2 3
1 4
4 5
1 6
6 7

Output
1

tags: ['Tree algorithms', 'Graph algorithms', 'Graph traversal', 'Dynamic programming']

skill_types: ['Dynamic programming']

raw_tags: ['trees', 'dfs and similar', 'graphs', 'dp']

data_split: test