{"raw_statement":[{"iden":"statement","content":"Bash likes playing with arrays. He has an array _a_1, _a_2, ... _a__n_ of _n_ integers. He likes to guess the greatest common divisor (gcd) of different segments of the array. Of course, sometimes the guess is not correct. However, Bash will be satisfied if his guess is _almost correct_.\n\nSuppose he guesses that the gcd of the elements in the range \\[_l_, _r_\\] of _a_ is _x_. He considers the guess to be almost correct if he can change **at most** one element in the segment such that the gcd of the segment is _x_ after making the change. Note that when he guesses, he doesn't actually change the array — he just wonders if the gcd of the segment can be made _x_. Apart from this, he also sometimes makes changes to the array itself.\n\nSince he can't figure it out himself, Bash wants you to tell him which of his guesses are almost correct. Formally, you have to process _q_ queries of one of the following forms:\n\n*   1 _l_ _r_ _x_ — Bash guesses that the gcd of the range \\[_l_, _r_\\] is _x_. Report if this guess is almost correct.\n*   2 _i_ _y_ — Bash sets _a__i_ to _y_.\n\n**Note:** The array is 1\\-indexed."},{"iden":"input","content":"The first line contains an integer _n_ (1 ≤ _n_ ≤ 5·105) — the size of the array.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the elements of the array.\n\nThe third line contains an integer _q_ (1 ≤ _q_ ≤ 4·105) — the number of queries.\n\nThe next _q_ lines describe the queries and may have one of the following forms:\n\n*   1 _l_ _r_ _x_ (1 ≤ _l_ ≤ _r_ ≤ _n_, 1 ≤ _x_ ≤ 109).\n*   2 _i_ _y_ (1 ≤ _i_ ≤ _n_, 1 ≤ _y_ ≤ 109).\n\nGuaranteed, that there is at least one query of first type."},{"iden":"output","content":"For each query of first type, output _\"YES\"_ (without quotes) if Bash's guess is almost correct and _\"NO\"_ (without quotes) otherwise."},{"iden":"examples","content":"Input\n\n3\n2 6 3\n4\n1 1 2 2\n1 1 3 3\n2 1 9\n1 1 3 2\n\nOutput\n\nYES\nYES\nNO\n\nInput\n\n5\n1 2 3 4 5\n6\n1 1 4 2\n2 3 6\n1 1 4 2\n1 1 5 2\n2 5 10\n1 1 5 2\n\nOutput\n\nNO\nYES\nNO\nYES"},{"iden":"note","content":"In the first sample, the array initially is {2, 6, 3}.\n\nFor query 1, the first two numbers already have their gcd as 2.\n\nFor query 2, we can achieve a gcd of 3 by changing the first element of the array to 3. Note that the changes made during queries of type 1 are temporary and do not get reflected in the array.\n\nAfter query 3, the array is now {9, 6, 3}.\n\nFor query 4, no matter which element you change, you cannot get the gcd of the range to be 2."}],"translated_statement":[{"iden":"statement","content":"Bash 喜欢玩数组。他有一个包含 $n$ 个整数的数组 $[a_1, a_2, \\dots, a_n]$。他喜欢猜测数组中不同区间的最大公约数（gcd）。当然，有时他的猜测并不正确。但只要他的猜测“几乎正确”，Bash 就会满意。\n\n假设他猜测数组中区间 $[l, r]$ 的 gcd 为 $x$。如果他能将该区间中的**至多一个**元素修改为任意值，使得修改后区间的 gcd 恰好为 $x$，则他认为这个猜测是“几乎正确”的。注意，当他进行猜测时，并不会真正修改数组——他只是想知道是否可以通过至多一次修改使区间 gcd 变为 $x$。此外，他有时也会实际修改数组本身。\n\n由于他自己无法解决，Bash 希望你告诉他哪些猜测是“几乎正确”的。形式上，你需要处理 $q$ 个以下形式的查询：\n\n*注意*：数组是 $1$-索引的。\n\n第一行包含一个整数 $n$ ($1 \\leq n \\leq 5\\cdot10^5$) —— 数组的大小。\n\n第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ ($1 \\leq a_i \\leq 10^9$) —— 数组的元素。\n\n第三行包含一个整数 $q$ ($1 \\leq q \\leq 4\\cdot10^5$) —— 查询的数量。\n\n接下来的 $q$ 行描述查询，可能为以下两种形式之一：\n\n保证至少存在一个第一类查询。\n\n对于每个第一类查询，如果 Bash 的猜测是“几乎正确”的，请输出 _\"YES\"_（不含引号），否则输出 _\"NO\"_（不含引号）。\n\n在第一个样例中，数组初始为 $\\{2, 6, 3\\}$。\n\n对于查询 $1$，前两个数的 gcd 已经是 $2$。\n\n对于查询 $2$，我们可以通过将数组的第一个元素改为 $3$ 来使 gcd 变为 $3$。注意，类型为 $1$ 的查询所做的修改是临时的，不会反映到数组中。\n\n在查询 $3$ 之后，数组变为 $\\{9, 6, 3\\}$。\n\n对于查询 $4$，无论你修改哪个元素，都无法使该区间的 gcd 变为 $2$。"},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 \\leq n \\leq 5\\cdot10^5$) —— 数组的大小。第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ ($1 \\leq a_i \\leq 10^9$) —— 数组的元素。第三行包含一个整数 $q$ ($1 \\leq q \\leq 4\\cdot10^5$) —— 查询的数量。接下来的 $q$ 行描述查询，可能为以下两种形式之一：\n\n$1\\ l\\ r\\ x$ ($1 \\leq l \\leq r \\leq n, 1 \\leq x \\leq 10^9$)。\n\n$2\\ i\\ y$ ($1 \\leq i \\leq n, 1 \\leq y \\leq 10^9$)。\n\n保证至少存在一个第一类查询。"},{"iden":"output","content":"对于每个第一类查询，如果 Bash 的猜测是“几乎正确”的，请输出 _\"YES\"_（不含引号），否则输出 _\"NO\"_（不含引号）。"},{"iden":"examples","content":"输入\n3\n2 6 3\n4\n1 1 2 2\n1 1 3 3\n2 1 9\n1 1 3 2\n输出\nYES\nYES\nNO\n\n输入\n5\n1 2 3 4 5\n6\n1 1 4 2\n2 3 6\n1 1 4 2\n1 1 5 2\n2 5 10\n1 1 5 2\n输出\nNO\nYES\nNO\nYES"},{"iden":"note","content":"在第一个样例中，数组初始为 $\\{2, 6, 3\\}$。对于查询 $1$，前两个数的 gcd 已经是 $2$。对于查询 $2$，我们可以通过将数组的第一个元素改为 $3$ 来使 gcd 变为 $3$。注意，类型为 $1$ 的查询所做的修改是临时的，不会反映到数组中。在查询 $3$ 之后，数组变为 $\\{9, 6, 3\\}$。对于查询 $4$，无论你修改哪个元素，都无法使该区间的 gcd 变为 $2$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ a = [a_1, a_2, \\dots, a_n] $ be an array of $ n $ positive integers, 1-indexed.\n- Let $ \\gcd(S) $ denote the greatest common divisor of a multiset $ S $ of integers.\n- A query is of one of two types:\n  1. **Guess Query**: Given $ l, r, x $, determine whether there exists an index $ i \\in [l, r] $ such that replacing $ a_i $ with some integer $ b $ yields $ \\gcd(a_l, \\dots, a_{i-1}, b, a_{i+1}, \\dots, a_r) = x $, **or** $ \\gcd(a_l, \\dots, a_r) = x $ (i.e., no change needed).\n  2. **Update Query**: Given $ i, v $, set $ a_i \\leftarrow v $.\n\n**Constraints:**\n\n- $ 1 \\leq n \\leq 5 \\cdot 10^5 $\n- $ 1 \\leq a_i \\leq 10^9 $\n- $ 1 \\leq q \\leq 4 \\cdot 10^5 $\n- Queries of type 1 are guaranteed to exist.\n\n**Objective:**\n\nFor each query of type 1 with parameters $ (l, r, x) $, output:\n\n- **\"YES\"** if **at most one** element in $ a[l:r] $ can be replaced (with any positive integer) so that the gcd of the resulting segment equals $ x $,\n- **\"NO\"** otherwise.\n\n**Formal Condition for \"YES\":**\n\nLet $ G = \\gcd(a_l, a_{l+1}, \\dots, a_r) $.\n\nDefine $ g_i = \\gcd(\\{a_j : j \\in [l, r], j \\ne i\\}) $ for each $ i \\in [l, r] $.\n\nThen, the guess is almost correct **iff**:\n\n$$\n\\exists\\, i \\in [l, r] \\text{ such that } g_i \\text{ is divisible by } x \\quad \\text{and} \\quad \\frac{g_i}{x} \\text{ is an integer} \\quad \\text{and} \\quad \\exists\\, b \\in \\mathbb{Z}^+ \\text{ such that } \\gcd(g_i, b) = x\n$$\n\nBut since we can choose $ b $ arbitrarily, the condition simplifies to:\n\n> There exists an index $ i \\in [l, r] $ such that $ x \\mid g_i $,  \n> **or** $ G = x $ (i.e., no change needed).\n\nEquivalently, since $ \\gcd(g_i, b) = x $ is achievable for some $ b $ if and only if $ x \\mid g_i $, the condition becomes:\n\n$$\n\\boxed{\n\\exists\\, i \\in [l, r] \\text{ such that } x \\mid \\gcd(\\{a_j : j \\in [l, r], j \\ne i\\})\n}\n$$\n\n**Note:** If $ x \\mid G $, then setting $ b = x $ (or any multiple of $ x $) may not work unless the other elements’ gcd is divisible by $ x $. But the above condition captures it: if $ x \\mid g_i $, then we can choose $ b = x $, and the overall gcd becomes $ \\gcd(g_i, x) = x $, since $ x \\mid g_i $.\n\nThus, the necessary and sufficient condition is:\n\n> The guess $ x $ is almost correct for segment $ [l, r] $ **iff**  \n> $$\n> \\exists\\, i \\in [l, r] \\text{ such that } x \\mid \\gcd_{j \\in [l, r] \\setminus \\{i\\}} a_j\n> $$\n\nThis includes the case $ i $ is not changed (i.e., $ \\gcd_{j \\in [l, r]} a_j = x $), because then $ g_i = \\gcd_{j \\ne i} a_j $ still satisfies $ x \\mid g_i $ (since $ x = G \\mid g_i $ only if $ g_i = G $, which is true only if removing $ a_i $ doesn't change the gcd — but actually, if $ G = x $, then for *any* $ i $, we have $ x \\mid g_i $? Not necessarily. So we must be careful.\n\nActually, if $ G = x $, then we don't need to change anything. So we can always choose to change *no* element. So we must allow the case of **zero changes**.\n\nTherefore, the condition is:\n\n$$\n\\boxed{\n\\gcd(a_l, \\dots, a_r) = x \\quad \\text{OR} \\quad \\exists\\, i \\in [l, r] \\text{ such that } x \\mid \\gcd(\\{a_j : j \\in [l, r], j \\ne i\\})\n}\n$$\n\nBut note: if $ \\gcd(a_l, \\dots, a_r) = x $, then for *every* $ i $, $ g_i $ is a multiple of $ x $? Not necessarily. For example: $ [6, 10] $, $ x = 2 $. $ \\gcd(6,10)=2 $, but $ g_1 = 10 $, $ g_2 = 6 $, both divisible by 2 — so yes. But is it always true?\n\nSuppose $ G = x $. Then $ x \\mid a_j $ for all $ j $. So for any $ i $, $ g_i = \\gcd(\\text{all except } a_i) $, which is still divisible by $ x $, since all other $ a_j $ are divisible by $ x $. So yes: if $ G = x $, then for **every** $ i $, $ x \\mid g_i $.\n\nThus, the condition \"there exists $ i \\in [l, r] $ such that $ x \\mid g_i $\" **includes** the case $ G = x $.\n\nTherefore, the entire condition reduces to:\n\n$$\n\\boxed{\n\\exists\\, i \\in [l, r] \\text{ such that } x \\mid \\gcd\\left( \\{a_j : j \\in [l, r],\\ j \\ne i\\} \\right)\n}\n$$\n\nThis is the formal condition to check for each query of type 1.\n\n**Update queries** modify $ a_i \\leftarrow v $, and are handled directly.\n\n**Implementation note:** To compute $ g_i = \\gcd(\\text{prefix}[i-1], \\text{suffix}[i+1]) $ efficiently for all $ i \\in [l, r] $, we can precompute prefix and suffix gcd arrays for any range, but since queries are online and updates occur, we need a segment tree or similar data structure supporting:\n\n- Point updates\n- Range gcd queries\n- For a given range $ [l, r] $ and value $ x $, check: $ \\exists i \\in [l, r] $ such that $ x \\mid \\gcd(\\text{all elements in } [l, r] \\setminus \\{i\\}) $\n\nThe latter can be done by computing the total gcd $ G = \\gcd(a_l, \\dots, a_r) $, and for each $ i $, $ g_i = \\gcd(\\gcd(a_l, \\dots, a_{i-1}), \\gcd(a_{i+1}, \\dots, a_r)) $.\n\nWe can precompute prefix and suffix gcd arrays for any segment $ [l, r] $ in $ O(1) $ after $ O(n) $ preprocessing per segment — but since segments vary per query and updates occur, we need a segment tree that supports:\n\n- Point updates\n- Range gcd queries\n- And for a given $ [l, r] $, compute $ g_i $ for each $ i \\in [l, r] $ in $ O(1) $ per index — which would be $ O(r-l+1) $, too slow.\n\nAlternative insight:\n\nLet $ G = \\gcd(a_l, \\dots, a_r) $\n\nWe want to know: is there an index $ i \\in [l, r] $ such that $ x \\mid \\gcd_{j \\ne i} a_j $?\n\nLet $ g_i = \\gcd(\\text{all except } a_i) $\n\nNote: $ \\gcd(g_i, a_i) = G $\n\nSo $ g_i = \\frac{G}{\\gcd(G, a_i)} \\cdot \\text{something} $? Not exactly.\n\nActually, $ G = \\gcd(g_i, a_i) $\n\nSo $ g_i = \\frac{G}{d_i} $ where $ d_i = \\gcd(G, a_i) $? Not quite.\n\nBetter: $ G \\mid g_i $, because $ G $ divides every $ a_j $, so $ G \\mid g_i $. So $ g_i $ is a multiple of $ G $.\n\nWait: no! $ g_i $ is the gcd of all elements except $ a_i $, and $ G $ is the gcd of all elements. So $ G \\mid g_i $, because $ g_i $ is a common divisor of a subset of the elements, and $ G $ divides all elements, so $ G \\mid g_i $.\n\nTherefore, $ g_i $ is a multiple of $ G $. So $ x \\mid g_i $ implies $ x \\mid g_i $ and $ G \\mid g_i $.\n\nBut we are not requiring $ x \\mid G $. We are requiring $ x \\mid g_i $.\n\nSo: we want to know if there exists $ i \\in [l, r] $ such that $ x \\mid g_i $, where $ g_i = \\gcd_{j \\ne i} a_j $.\n\nAnd since $ g_i = \\gcd( \\gcd(a_l, \\dots, a_{i-1}), \\gcd(a_{i+1}, \\dots, a_r) ) $, we can compute $ g_i $ for each $ i $ using prefix and suffix arrays for the range $ [l, r] $.\n\nSo for a fixed query $ [l, r] $, we can:\n\n1. Precompute prefix gcd: $ P[i] = \\gcd(a_l, a_{l+1}, \\dots, a_i) $ for $ i = l $ to $ r $\n2. Precompute suffix gcd: $ S[i] = \\gcd(a_i, a_{i+1}, \\dots, a_r) $ for $ i = l $ to $ r $\n3. For each $ i \\in [l, r] $, compute $ g_i = \\gcd(P[i-1], S[i+1]) $ (with appropriate bounds)\n4. Check if $ x \\mid g_i $ for any $ i $\n\nBut doing this for each query would be $ O(n) $ per query, and $ q \\leq 4 \\cdot 10^5 $, so worst-case $ O(nq) \\approx 2 \\cdot 10^{11} $, too slow.\n\nWe need a better approach.\n\n**Key Insight:**\n\nLet $ G = \\gcd(a_l, \\dots, a_r) $\n\nWe want to know: does there exist an index $ i $ such that $ x \\mid \\gcd_{j \\ne i} a_j $?\n\nNote that $ \\gcd_{j \\ne i} a_j = \\frac{G}{\\gcd(G, a_i)} \\cdot k $? Not exactly.\n\nActually, we have:\n\n$$\n\\gcd_{j \\ne i} a_j = \\frac{G}{\\gcd(G, a_i / \\gcd(G, a_i))} \\quad \\text{? No.}\n$$\n\nBetter: Since $ G = \\gcd(g_i, a_i) $, and $ g_i $ is divisible by $ G $, then $ g_i = G \\cdot d_i $ for some integer $ d_i \\geq 1 $.\n\nBut $ d_i = \\frac{g_i}{G} $, and $ \\gcd(a_i / G, d_i) = 1 $.\n\nWe want $ x \\mid g_i = G \\cdot d_i $\n\nSo $ x \\mid G \\cdot d_i $\n\nLet $ d = \\gcd(x, G) $. Then $ x = d \\cdot x' $, $ G = d \\cdot G' $, and $ \\gcd(x', G') = 1 $\n\nThen $ x \\mid G \\cdot d_i \\iff d \\cdot x' \\mid d \\cdot G' \\cdot d_i \\iff x' \\mid G' \\cdot d_i $\n\nSince $ \\gcd(x', G') = 1 $, this implies $ x' \\mid d_i $\n\nSo $ d_i \\geq x' $\n\nBut $ d_i = g_i / G $, and $ g_i $ is the gcd of all except $ a_i $, so $ d_i $ is the \"extra\" factor from removing $ a_i $.\n\nThis is getting complex.\n\n**Practical known solution from similar problems (e.g., Codeforces):**\n\nThe standard solution for \"almost gcd\" queries is:\n\n- For a query $ (l, r, x) $, compute $ G = \\gcd(a_l, \\dots, a_r) $\n- If $ x \\mid G $, then YES (because we can change any element to $ x $, and since all others are divisible by $ x $, the gcd becomes $ x $) — **Wait, no!** If $ x \\mid G $, then $ G $ is a multiple of $ x $, so $ x $ divides all elements? No: $ G $ divides all elements, so if $ x \\mid G $, then $ x $ divides all elements. So we can change any element to $ x $, and the gcd becomes $ \\gcd(x, \\text{other elements}) $. But since other elements are divisible by $ G $, which is divisible by $ x $, then $ \\gcd(x, \\text{multiple of } x) = x $. So YES.\n\nBut what if $ x \\nmid G $? Then we need to change exactly one element.\n\nLet’s suppose $ x \\nmid G $. Then we must change one element $ a_i $ such that $ \\gcd(\\text{others}) $ is divisible by $ x $, and then we set $ a_i $ to $ x $, so the overall gcd becomes $ \\gcd(\\gcd(\\text{others}), x) = x $, since $ x \\mid \\gcd(\\text{others}) $.\n\nSo condition: $ \\exists i \\in [l, r] $ such that $ x \\mid \\gcd_{j \\ne i} a_j $\n\nAnd since $ \\gcd_{j \\ne i} a_j = \\frac{G}{\\gcd(G, a_i)} \\cdot \\text{?} $\n\nActually, a known trick:\n\nLet $ G = \\gcd(a_l, \\dots, a_r) $\n\nFor each $ i $, define $ g_i = \\gcd(\\text{all except } a_i) $\n\nThen $ g_i = \\gcd(G, \\text{all except } a_i) = \\gcd(G, \\text{gcd of all except } a_i) $ — tautology.\n\nBut note: $ g_i = \\frac{G}{\\gcd(G, a_i / \\gcd(G, a_i))} $? No.\n\nActually, since $ G = \\gcd(g_i, a_i) $, then $ g_i = \\frac{G \\cdot k}{\\gcd(k, a_i / \\gcd(G, a_i))} $ — messy.\n\nStandard solution from Codeforces problems (e.g., CF 1114D, CF 1175E) for \"can we change one element to make gcd = x\":\n\n1. Compute $ G = \\gcd(a_l, \\dots, a_r) $\n2. If $ x \\mid G $: YES\n3. Else:\n   - For each $ i \\in [l, r] $, compute $ g_i = \\gcd(\\text{prefix}[i-1], \\text{suffix}[i+1]) $\n   - Check if $ x \\mid g_i $ for any $ i $\n   - If yes, YES; else NO\n\nBut we can’t iterate over all $ i $ per query.\n\n**Optimization:**\n\nWe can note: if there exists an index $ i $ such that $ x \\mid g_i $, then since $ g_i $ is the gcd of all elements except $ a_i $, and $ G = \\gcd(g_i, a_i) $, then $ g_i $ must be divisible by $ x $, and $ G $ is a divisor of $ g_i $.\n\nSo $ \\text{lcm}(G, x) \\mid g_i $? Not helpful.\n\nAnother idea: the number of indices $ i $ for which $ g_i \\ne G $ is small. In fact, $ g_i \\ne G $ only if $ a_i $ is the unique element that is not divisible by some prime factor of $ G $. So there are at most $ O(\\log \\max a_i) $ such indices.\n\nThus, we can find all indices $ i \\in [l, r] $ such that $ \\gcd(a_l, \\dots, a_r) \\ne \\gcd(a_l, \\dots, a_{i-1}, a_{i+1}, \\dots, a_r) $ — i.e., the indices where removing $ a_i $ changes the gcd. There are at most $ O(\\log \\max a_i) $ such indices, because each time the gcd changes, it drops by a factor of at least 2.\n\nSo algorithm for a query $ (l, r, x) $:\n\n1. Compute $ G = \\gcd(a_l, \\dots, a_r) $\n2. If $ x \\mid G $: return YES\n3. Else:\n   - Find all indices $ i \\in [l, r] $ such that $ g_i \\ne G $. These are the \"critical\" indices where removing $ a_i $ increases the gcd (or changes it). There are at most $ O(\\log \\max a_i) $ such indices.\n   - For each such $ i $, compute $ g_i = \\gcd(\\text{prefix}[i-1], \\text{suffix}[i+1]) $\n   - If $ x \\mid g_i $ for any such $ i $, return YES\n   - Else, return NO\n\nHow to find critical indices quickly?\n\nWe can use a segment tree that stores gcd, and then do a binary search-like traversal to find all positions where the gcd changes when skipping an element.\n\nAlternatively, we can precompute for the entire array a structure that allows us to, for a given range $ [l, r] $, iterate over the \"distinct gcd prefixes\" — but this is complex.\n\nKnown efficient solution: use a segment tree storing gcd, and for a query $ [l, r] $, we can compute the prefix and suffix gcd arrays in $ O(\\log n) $ time per query if we store them in a segment tree — but we need all $ g_i $.\n\nActually, we can do:\n\n- Use a segment tree to get $ \\gcd(l, r) $\n- Use a segment tree to get prefix gcd from $ l $ to any $ i $, and suffix gcd from any $ i $ to $ r $\n- Then, for the entire range $ [l, r] $, we can find the positions where the prefix gcd changes — there are at most $ O(\\log \\max a_i) $ such changes.\n\nSo we can:\n\n- Compute prefix gcd array for $ [l, r] $ by walking through the segment tree and collecting the distinct gcd values and their positions — at most $ O(\\log n) $ distinct values.\n- Similarly for suffix.\n- Then, for each position where the prefix gcd changes, and for each where the suffix gcd changes, we can compute $ g_i $ for those candidate indices.\n\nIn fact, the only indices $ i $ that can yield $ g_i \\ne G $ are those where $ a_i $ is the \"odd one out\" — and there are at most $ O(\\log \\max a_i) $ such candidates.\n\nSo practical solution:\n\nFor query $ (l, r, x) $:\n\n1. Compute $ G = \\gcd(a_l, \\dots, a_r) $\n2. If $ x \\mid G $: return YES\n3. Else:\n   - Let $ \\text{candidates} = \\emptyset $\n   - Compute the prefix gcd array from $ l $ to $ r $, and record the indices where it changes: $ i_1, i_2, \\dots, i_k $ (at most $ O(\\log \\max a_i) $)\n   - Similarly compute suffix gcd array from $ r $ to $ l $, record change points: $ j_1, j_2, \\dots, j_m $\n   - The candidate indices for $ i $ are the union of these change points and $ l, r $ — total $ O(\\log \\max a_i) $\n   - For each candidate $ i \\in \\text{candidates} \\cap [l, r] $:\n     - Compute $ g_i = \\gcd(\\text{prefix}[i-1], \\text{suffix}[i+1]) $\n     - If $ x \\mid g_i $, return YES\n   - Return NO\n\nThis works because if $ g_i \\ne G $, then $ a_i $ must be the reason for the gcd being $ G $, and removing it must cause a change — and there are only logarithmically many such elements.\n\n**Final Formal Statement:**\n\nGiven array $ a $, and queries:\n\n- **Update**: $ a_i \\leftarrow v $\n- **Query**: Given $ l, r, x $, output YES iff  \n  $$\n  x \\mid \\gcd(a_l, \\dots, a_r) \\quad \\text{or} \\quad \\exists\\, i \\in [l, r] \\text{ such that } x \\mid \\gcd(\\{a_j : j \\in [l, r], j \\ne i\\})\n  $$\n\nAnd due to the structure of gcd, the second condition can be checked by examining only $ O(\\log \\max a_i) $ candidate indices per query.\n\nThus, the formal condition is as above.","simple_statement":null,"has_page_source":false}