For scoreboard analytics, Wasif's system must support both updating individual scores AND querying the GCD across ranges of scores, fast, as the contest is still running. Read N integers and Q operations: "U l r v" (add v to every element in [l,r]) or "Q l r" (print the GCD of all elements in [l,r]). Implement a segment tree with lazy propagation supporting both range updates and range GCD queries in O(log N) each — this needs a custom merge (GCD of children) combined with careful lazy-add propagation (note: GCD doesn't distribute over addition the way sum does, so think about how lazy values interact with the stored GCDs).
Input
Line1: N Q. Line2: N integers. Next Q lines: "U l r v" or "Q l r".
Output
One line per Q operation: the requested GCD.
Constraints
1 ≤ N,Q ≤ 10^5
Sample Input
5 2 4 8 12 16 20 Q 1 3 Q 2 4
Sample Output
4 4
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.