{"problem":{"name":"[ICPC 2021 Nanjing R] Puzzle in Inazuma","description":{"content":"Every traveler knows that they'll be rewarded with a treasure box after solving the puzzles in Inazuma, but few know that these puzzles are designed by Yae Miko, the Guuji of the Grand Narukami Shrine","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9841"},"statements":[{"statement_type":"Markdown","content":"Every traveler knows that they'll be rewarded with a treasure box after solving the puzzles in Inazuma, but few know that these puzzles are designed by Yae Miko, the Guuji of the Grand Narukami Shrine, to test whether the traveler is strong enough to save her friend Raiden Shogun and people of Inazuma.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/p50zu2m6.png)\n\nAfter a traveler passes the test Yae will have to reset the puzzles to the initial state. But this time she has some troubles and even doubts that whether some of them are already broken.\n\nYae's puzzle can be considered as a weighted undirected complete graph $G$ before resetting. We also denote the initial state as another weighted undirected complete graph $H$. Both $G$ and $H$ have exactly $n$ vertices, and these vertices are labeled from $1$ to $n$.\n\nTo reset graph $G$ to $H$ Yae can perform the following operation any number of times:\n- First select four distinct vertices $a$, $b$, $c$, $d$ and an integer $x$. Note that she can select a different set of $a$, $b$, $c$, $d$ and $x$ each time.\n- Let $(i, j)$ be the edge between vertices $i$ and $j$. Increase the weight of $(a, b)$, $(a, c)$ and $(a, d)$ by $x$ and also decrease the weight of $(b, c)$, $(b, d)$ and $(c, d)$ by $x$.\n\nPlease help Yae determine whether she can change graph $G$ to graph $H$. If yes you also shall tell her the detailed steps.\n\n## Input\n\nThere is only one test case in each test file.\n\nThe first line of the input contains an integer $n$ ($4 \\leq n \\leq 100$) indicating the number of vertices in graph $G$ and $H$.\n\nFor the following $(n - 1)$ lines, the $i$-th line contains $(n - i)$ integers $w_{i, i + 1}, w_{i, i + 2}, \\cdots, w_{i, n}$ ($-100 \\le w_{i, j} \\le 100$) where $w_{i, j}$ indicates the weight of the edge connecting vertices $i$ and $j$ in graph $G$.\n\nFor the following $(n - 1)$ lines, the $i$-th line contains $(n - i)$ integers $v_{i, i + 1}, v_{i, i + 2}, \\cdots, v_{i, n}$ ($-100 \\le v_{i, j} \\le 100$) where $v_{i, j}$ indicates the weight of the edge connecting vertices $i$ and $j$ in graph $H$.\n\n## Output\n\nIf Yae cannot change $G$ to $H$, output `-1`.\n\nOtherwise first output an integer $m$ ($0 \\le m \\le 10^5$) in one line indicating the number of operations Yae needs.\n\nFor the following $m$ lines, output five integers $a_i$, $b_i$, $c_i$, $d_i$ and $x_i$ in the $i$-th line separated by a space, indicating that for the $i$-th operation Yae choose vertices $a_i$, $b_i$, $c_i$, $d_i$ and integer $x_i$. Note that $a_i$, $b_i$, $c_i$, $d_i$ must be distinct and $-10^9 \\le x_i \\le 10^9$.\n\nIt can be proved that if graph $G$ can be changed to graph $H$ there exists a solution with no more than $10^5$ operations.\n\nNote that you don't have to minimize $m$. If there are multiple solutions, output any of them.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9841","tags":["搜索","2021","Special Judge","O2优化","构造","ICPC","分类讨论","南京"],"sample_group":[["4\n0 1 1\n0 0\n1\n1 0 0\n1 1\n0\n","1\n2 1 3 4 1\n"],["4\n3 3 3\n0 0\n0\n0 0 0\n3 3\n3\n","1\n1 2 3 4 -3\n"],["5\n-12 15 -12 1\n37 14 7\n7 9\n-11\n12 5 1 13\n-1 -4 -7\n-5 -9\n18\n","-1\n"]],"created_at":"2026-03-03 11:09:25"}}