{"problem":{"name":"G. Projection","description":{"content":"Everybody knows that you are a _TensorFlow_ fan. Therefore, you've been challenged to recreate the _TensorFlow_ logo from two projections.  Consider that you have a _3D_ volume, $n times m times h$, ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10239G"},"statements":[{"statement_type":"Markdown","content":"Everybody knows that you are a _TensorFlow_ fan. Therefore, you've been challenged to recreate the _TensorFlow_ logo from two projections. \n\nConsider that you have a _3D_ volume, $n times m times h$, and two projections (two matrices with dimensions $n times m$ and $n times h$ with elements $0$ and $1$). You are asked to compute a possible sets of cubes that must be placed inside the _3D_ volume such that the _3D_ object created with the cubes throws the shadows specified by the projection-matrices, when the light comes from left and front. If it is not possible, just print $-1$. If it is possible you must find exactly two sets, one with the *maximum* amount of cubes and one with the *minimum* amount. You can assume there is no gravitation (the cubes are located inside the _3D_ volume exactly where they are placed, without requiring any support). We assume that $1$ represents shadow and $0$ represents light. \n\nIf there are multiple such solutions, you must output the minimum lexicographic one. One solution $A$ is lexicographically smaller than another solution $b$ if the first number that differs between the two solutions is smaller in $a$ than in $b$.\n\nFor example, solution $[ (0, 0, 0), (1, 1, 1) ]$ is smaller than $[ (1, 1, 1), (0, 0, 0) ]$.\n\nThe first line contains three integers separated by a single space $n$, $m$, $h$ ($1 <= n, m, h <= 100$) — the volume dimensions. \n\nEach of the next $n$ lines contains $m$ characters, each being either $1$ or $0$ representing either a shadow area ($1$) or a light area ($0$), describing the projection from the light in the front.\n\nEach of the next $n$ lines contains $h$ characters, with the same format as above, describing the projection from the light on the left.\n\nThe output should contain on the first line one number, either $-1$ if there is no solution or $k_{m a x}$ representing the maximum number of cubes we can assign in the volume that will generate the two projections given in the input.\n\nThe next $k_{m a x}$ lines should contain triplets of numbers $x$, $y$, $z$ ($0 <= x < n$, $0 <= y < m$, $0 <= z < h$) representing the cubes chosen in the lexicographically smallest solution with maximum number of cubes.\n\nThen, only if there is a solution, one more line follows containing $k_{m i n}$, the minimum number of cubes we can assign in the volume that will generate the two projections given in the input.\n\nAfter that, the next $k_{m i n}$ lines should contain triplets of numbers $x$, $y$, $z$ ($0 <= x < n$, $0 <= y < m$, $0 <= z < h$) representing the cubes in the lexicographically smallest solution with minimum number of cubes.\n\nA cube at coordinates $(x, y, z)$ will generate a shadow at line $x$ and column $y$ in the $n times m$ projection and line $x$ and column $z$ in the $n times h$ projection (indexed from $0$).\n\n## Input\n\nThe first line contains three integers separated by a single space $n$, $m$, $h$ ($1 <= n, m, h <= 100$) — the volume dimensions. Each of the next $n$ lines contains $m$ characters, each being either $1$ or $0$ representing either a shadow area ($1$) or a light area ($0$), describing the projection from the light in the front.Each of the next $n$ lines contains $h$ characters, with the same format as above, describing the projection from the light on the left.\n\n## Output\n\nThe output should contain on the first line one number, either $-1$ if there is no solution or $k_{m a x}$ representing the maximum number of cubes we can assign in the volume that will generate the two projections given in the input.The next $k_{m a x}$ lines should contain triplets of numbers $x$, $y$, $z$ ($0 <= x < n$, $0 <= y < m$, $0 <= z < h$) representing the cubes chosen in the lexicographically smallest solution with maximum number of cubes.Then, only if there is a solution, one more line follows containing $k_{m i n}$, the minimum number of cubes we can assign in the volume that will generate the two projections given in the input.After that, the next $k_{m i n}$ lines should contain triplets of numbers $x$, $y$, $z$ ($0 <= x < n$, $0 <= y < m$, $0 <= z < h$) representing the cubes in the lexicographically smallest solution with minimum number of cubes.\n\n[samples]\n\n## Note\n\nA cube at coordinates $(x, y, z)$ will generate a shadow at line $x$ and column $y$ in the $n times m$ projection and line $x$ and column $z$ in the $n times h$ projection (indexed from $0$).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, k \\leq 10^5 $.  \nLet $ M = (m_1, m_2, \\dots, m_n) $ be Mahmoud's array.  \nLet $ B = (b_1, b_2, \\dots, b_n) $ be Bashar's array.  \n\n**Constraints**  \nFor all $ i \\in \\{1, \\dots, n\\} $:  \n$ 1 \\leq m_i \\leq 10^5 $,  \n$ 1 \\leq b_i \\leq 10^5 $.  \n\n**Objective**  \nDefine a pair $ (i, j) $ with $ 1 \\leq i < j \\leq n $ as a *good pair* if:  \n$$\n|m_i - m_j| \\geq k \\quad \\text{(for Mahmoud)}, \\quad \\text{or} \\quad |b_i - b_j| \\geq k \\quad \\text{(for Bashar)}.\n$$  \nLet $ P_M $ be the number of good pairs in $ M $, and $ P_B $ be the number of good pairs in $ B $.  \n\nDetermine:  \n- If $ P_M > P_B $, output $ \\text{\"Mahmoud\"} $,  \n- If $ P_B > P_M $, output $ \\text{\"Bashar\"} $,  \n- If $ P_M = P_B $, output $ \\text{\"Draw\"} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10239G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}