{"problem":{"name":"[CCC 2021 S5]  Math Homework","description":{"content":"构造一个长度为 $N$ 的整数序列 $A$，使得： 1. $\\forall i=1,2,\\cdots,N,1\\leq A_i\\leq 10^9$； 2. $\\forall i=1,2,\\cdots,M,\\gcd(A_{X_i},A_{X_i+1},\\cdots,A_{Y_i})=Z_i$。 或者报告无解。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9027"},"statements":[{"statement_type":"Markdown","content":"构造一个长度为 $N$ 的整数序列 $A$，使得：\n\n1. $\\forall i=1,2,\\cdots,N,1\\leq A_i\\leq 10^9$；\n2. $\\forall i=1,2,\\cdots,M,\\gcd(A_{X_i},A_{X_i+1},\\cdots,A_{Y_i})=Z_i$。\n\n或者报告无解。\n\n## Input\n\n第一行，$N,M$。\n\n接下来 $M$ 行，每行有 $X_i,Y_i,Z_i$，描述一个限制 2.\n\n## Output\n\n一行，序列 $A$，或者 `Impossible`。\n\n[samples]\n\n## Note\n\n$$1\\leq N\\leq 150000,1\\leq M\\leq 150000,1\\leq Z_i\\leq 16$$\n\n译自 [CCC2021 S5](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。\n\nspj 在附件里，发现锅了请联系[我](/user/90693)。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9027","tags":["线段树","2021","Special Judge","CCC（加拿大）","ST 表","构造","差分"],"sample_group":[["2 2\n1 2 2\n2 2 6\n","4 6"],["2 2\n1 2 2\n2 2 5\n","Impossible"]],"created_at":"2026-03-03 11:09:25"}}