{"problem":{"name":"G. Mass Change Queries","description":{"content":"You are given an array _a_ consisting of _n_ integers. You have to process _q_ queries to this array; each query is given as four numbers _l_, _r_, _x_ and _y_, denoting that for every _i_ such that _","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF911G"},"statements":[{"statement_type":"Markdown","content":"You are given an array _a_ consisting of _n_ integers. You have to process _q_ queries to this array; each query is given as four numbers _l_, _r_, _x_ and _y_, denoting that for every _i_ such that _l_ ≤ _i_ ≤ _r_ and _a__i_ = _x_ you have to set _a__i_ equal to _y_.\n\nPrint the array after all queries are processed.\n\n## Input\n\nThe first line contains one integer _n_ (1 ≤ _n_ ≤ 200000) — the size of array _a_.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 100) — the elements of array _a_.\n\nThe third line contains one integer _q_ (1 ≤ _q_ ≤ 200000) — the number of queries you have to process.\n\nThen _q_ lines follow. _i_\\-th line contains four integers _l_, _r_, _x_ and _y_ denoting _i_\\-th query (1 ≤ _l_ ≤ _r_ ≤ _n_, 1 ≤ _x_, _y_ ≤ 100).\n\n## Output\n\nPrint _n_ integers — elements of array _a_ after all changes are made.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给定一个包含 $n$ 个整数的数组 $[a]$。你需要对这个数组处理 $q$ 个查询；每个查询由四个数 $l$、$r$、$x$ 和 $y$ 给出，表示对于所有满足 $l ≤ i ≤ r$ 且 $a_i = x$ 的下标 $i$，将 $a_i$ 设置为 $y$。\n\n在处理完所有查询后，输出数组。\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 200000$) —— 数组 $[a]$ 的大小。\n\n第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$ ($1 ≤ a_i ≤ 100$) —— 数组 $[a]$ 的元素。\n\n第三行包含一个整数 $q$ ($1 ≤ q ≤ 200000$) —— 需要处理的查询数量。\n\n接下来 $q$ 行，第 $i$ 行包含四个整数 $l$, $r$, $x$ 和 $y$，表示第 $i$ 个查询 ($1 ≤ l ≤ r ≤ n$, $1 ≤ x, y ≤ 100$)。\n\n请输出 $n$ 个整数 —— 所有修改完成后数组 $[a]$ 的元素。\n\n## Input\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 200000$) —— 数组 $[a]$ 的大小。第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$ ($1 ≤ a_i ≤ 100$) —— 数组 $[a]$ 的元素。第三行包含一个整数 $q$ ($1 ≤ q ≤ 200000$) —— 需要处理的查询数量。接下来 $q$ 行，第 $i$ 行包含四个整数 $l$, $r$, $x$ 和 $y$，表示第 $i$ 个查询 ($1 ≤ l ≤ r ≤ n$, $1 ≤ x, y ≤ 100$)。\n\n## Output\n\n请输出 $n$ 个整数 —— 所有修改完成后数组 $[a]$ 的元素。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the initial array, where $ a_i \\in \\{1, 2, \\dots, 100\\} $.  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \nLet $ Q = \\{(l_j, r_j, x_j, y_j) \\mid j \\in \\{1, \\dots, q\\}\\} $ be the set of queries, where for each $ j $:  \n- $ l_j, r_j \\in \\mathbb{Z} $, $ 1 \\leq l_j \\leq r_j \\leq n $,  \n- $ x_j, y_j \\in \\{1, 2, \\dots, 100\\} $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200000 $  \n2. $ 1 \\leq a_i \\leq 100 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq q \\leq 200000 $  \n4. For each query $ j $: $ 1 \\leq l_j \\leq r_j \\leq n $, $ 1 \\leq x_j, y_j \\leq 100 $  \n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, q\\} $, update the array $ A $ as follows:  \n$$\n\\forall i \\in \\{l_j, \\dots, r_j\\}, \\quad \\text{if } a_i = x_j, \\text{ then set } a_i := y_j.\n$$  \nOutput the final array $ A $ after all $ q $ queries.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF911G","tags":["data structures"],"sample_group":[["5\n1 2 3 4 5\n3\n3 5 3 5\n1 5 5 1\n1 5 1 5","5 2 5 4 5"]],"created_at":"2026-03-03 11:00:39"}}