{"problem":{"name":"G. Periodic RMQ Problem","description":{"content":"You are given an array _a_ consisting of positive integers and _q_ queries to this array. There are two types of queries: *   1 _l_ _r_ _x_ — for each index _i_ such that _l_ ≤ _i_ ≤ _r_ set _a__i_ =","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF803G"},"statements":[{"statement_type":"Markdown","content":"You are given an array _a_ consisting of positive integers and _q_ queries to this array. There are two types of queries:\n\n*   1 _l_ _r_ _x_ — for each index _i_ such that _l_ ≤ _i_ ≤ _r_ set _a__i_ = _x_.\n*   2 _l_ _r_ — find the minimum among such _a__i_ that _l_ ≤ _i_ ≤ _r_.\n\nWe decided that this problem is too easy. So the array _a_ is given in a compressed form: there is an array _b_ consisting of _n_ elements and a number _k_ in the input, and before all queries _a_ is equal to the concatenation of _k_ arrays _b_ (so the size of _a_ is _n_·_k_).\n\n## Input\n\nThe first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 105, 1 ≤ _k_ ≤ 104).\n\nThe second line contains _n_ integers — elements of the array _b_ (1 ≤ _b__i_ ≤ 109).\n\nThe third line contains one integer _q_ (1 ≤ _q_ ≤ 105).\n\nThen _q_ lines follow, each representing a query. Each query is given either as 1 _l_ _r_ _x_ — set all elements in the segment from _l_ till _r_ (including borders) to _x_ (1 ≤ _l_ ≤ _r_ ≤ _n_·_k_, 1 ≤ _x_ ≤ 109) or as 2 _l_ _r_ — find the minimum among all elements in the segment from _l_ till _r_ (1 ≤ _l_ ≤ _r_ ≤ _n_·_k_).\n\n## Output\n\nFor each query of type 2 print the answer to this query — the minimum on the corresponding segment.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定一个由正整数组成的数组 #cf_span[a] 和对该数组的 #cf_span[q] 个查询。有两种类型的查询：\n\n我们决定这个问题太简单了。因此，数组 #cf_span[a] 以压缩形式给出：输入中包含一个包含 #cf_span[n] 个元素的数组 #cf_span[b] 和一个数字 #cf_span[k]，在所有查询之前，#cf_span[a] 等于将 #cf_span[k] 个数组 #cf_span[b] 拼接而成（因此 #cf_span[a] 的大小为 #cf_span[n·k]）。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ k ≤ 104]）。\n\n第二行包含 #cf_span[n] 个整数——数组 #cf_span[b] 的元素（#cf_span[1 ≤ bi ≤ 109]）。\n\n第三行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 105]）。\n\n接下来 #cf_span[q] 行，每行表示一个查询。每个查询要么是 #cf_span[1] #cf_span[l] #cf_span[r] #cf_span[x] —— 将从 #cf_span[l] 到 #cf_span[r]（包含端点）的所有元素设为 #cf_span[x]（#cf_span[1 ≤ l ≤ r ≤ n·k]，#cf_span[1 ≤ x ≤ 109]），要么是 #cf_span[2] #cf_span[l] #cf_span[r] —— 求从 #cf_span[l] 到 #cf_span[r]（包含端点）的所有元素中的最小值（#cf_span[1 ≤ l ≤ r ≤ n·k]）。\n\n对于每个类型为 #cf_span[2] 的查询，请输出该查询的答案——对应区间上的最小值。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ k ≤ 104]）。第二行包含 #cf_span[n] 个整数——数组 #cf_span[b] 的元素（#cf_span[1 ≤ bi ≤ 109]）。第三行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 105]）。接下来 #cf_span[q] 行，每行表示一个查询。每个查询要么是 #cf_span[1] #cf_span[l] #cf_span[r] #cf_span[x] —— 将从 #cf_span[l] 到 #cf_span[r]（包含端点）的所有元素设为 #cf_span[x]（#cf_span[1 ≤ l ≤ r ≤ n·k]，#cf_span[1 ≤ x ≤ 109]），要么是 #cf_span[2] #cf_span[l] #cf_span[r] —— 求从 #cf_span[l] 到 #cf_span[r]（包含端点）的所有元素中的最小值（#cf_span[1 ≤ l ≤ r ≤ n·k]）。\n\n## Output\n\n对于每个类型为 #cf_span[2] 的查询，请输出该查询的答案——对应区间上的最小值。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $, with $ 1 \\leq n \\leq 10^5 $, $ 1 \\leq k \\leq 10^4 $.  \nLet $ B = (b_1, b_2, \\dots, b_n) \\in (\\mathbb{Z}^+)^n $ be the base array.  \nDefine the expanded array $ A \\in (\\mathbb{Z}^+)^{n \\cdot k} $ as $ A = \\underbrace{B \\parallel B \\parallel \\cdots \\parallel B}_{k \\text{ times}} $, i.e., $ A_{(i-1) \\cdot n + j} = b_j $ for $ i \\in \\{1, \\dots, k\\}, j \\in \\{1, \\dots, n\\} $.  \n\nLet $ q \\in \\mathbb{Z}^+ $, $ 1 \\leq q \\leq 10^5 $, be the number of queries.  \nEach query is one of two types:  \n- Type 1: $ (1, l, r, x) $ — assign $ A_i \\leftarrow x $ for all $ i \\in [l, r] $.  \n- Type 2: $ (2, l, r) $ — compute $ \\min_{i \\in [l, r]} A_i $.  \n\n**Constraints**  \n1. $ 1 \\leq b_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n2. For all queries:  \n   - $ 1 \\leq l \\leq r \\leq n \\cdot k $  \n   - $ 1 \\leq x \\leq 10^9 $  \n\n**Objective**  \nFor each query of type 2, output $ \\min_{i = l}^{r} A_i $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF803G","tags":["data structures"],"sample_group":[["3 1\n1 2 3\n3\n2 1 3\n1 1 2 4\n2 1 3","1\n3"],["3 2\n1 2 3\n5\n2 4 4\n1 4 4 5\n2 4 4\n1 1 6 1\n2 6 6","1\n5\n1"]],"created_at":"2026-03-03 11:00:39"}}