{"problem":{"name":"L. Ultra Weak Goldbach's Conjecture","description":{"content":"In number theory, Goldbach's conjecture states that every even integer greater than $2$ is the sum of two prime numbers. A weaker version of this conjecture states that every odd number greater than $","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10205L"},"statements":[{"statement_type":"Markdown","content":"In number theory, Goldbach's conjecture states that every even integer greater than $2$ is the sum of two prime numbers. A weaker version of this conjecture states that every odd number greater than $5$ is the sum of three prime numbers.\n\nHere is an ultra weak version of Goldbach's conjecture: every integer greater than $11$ is the sum of $textbf(s i x)$ prime numbers. Can you help to verify or disprove this conjecture?\n\nThe first line of the input gives the number of test cases, $T$ ($1 <= T <= 200$). $T$ test cases follow.\n\nEach test case contains one integer $N$ ($1 <= N <= 10^(12)$).\n\nFor each test case, output \"_Case x:_\" first, where _x_ is the test case number (starting from $1$). If the solution exist, output six prime numbers separated by spaces; otherwise output \"IMPOSSIBLE\" (quotes for clarity) when the solution does not exist. When the solution exists, any valid solution is acceptable.\n\n## Input\n\nThe first line of the input gives the number of test cases, $T$ ($1 <= T <= 200$). $T$ test cases follow.Each test case contains one integer $N$ ($1 <= N <= 10^(12)$).\n\n## Output\n\nFor each test case, output \"_Case x:_\" first, where _x_ is the test case number (starting from $1$). If the solution exist, output six prime numbers separated by spaces; otherwise output \"IMPOSSIBLE\" (quotes for clarity) when the solution does not exist. When the solution exists, any valid solution is acceptable.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ denote the number of stations and public railway edges, respectively.  \nLet $ A = (A_1, A_2, \\dots, A_n) \\in \\{0,1\\}^n $, where $ A_i = 0 $ if station $ i $ belongs to JR West, and $ A_i = 1 $ if JR East.  \nLet $ G = (V, E) $ be the undirected graph of public railways, with $ V = \\{1, 2, \\dots, n\\} $ and $ E $ of size $ m $, representing bidirectional public edges.  \nPrivate railways exist between all pairs of stations within the same JR region (i.e., complete subgraphs on $ \\{i \\mid A_i = 0\\} $ and $ \\{i \\mid A_i = 1\\} $).  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $, $ 0 \\le m \\le 10^5 $  \n2. $ G $ is connected.  \n3. No duplicate public edges.  \n\n**Objective**  \nFor each station $ i \\in \\{1, \\dots, n\\} $, compute:  \n$$\nS_i = \\sum_{j=1}^{n} D(i, j)\n$$  \nwhere $ D(u, v) $ is the minimum number of tickets required to travel from $ u $ to $ v $, with the following rules:  \n- Traveling along a **private railway** (same JR region) costs **0 tickets**.  \n- Traveling along a **public railway** costs **1 ticket**.  \n- Switching regions via a public edge incurs 1 ticket.  \n- The cost of a path is the number of public edges used.  \n\nThus, $ D(u, v) $ is the shortest path in $ G $, where edge weights are 1 for public edges and 0 for private edges (implicitly complete within regions).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10205L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}