<div>#include <iostream></div> <div>#include <fstream></div> <div>#include <cmath></div> <div>using namespace std;</div> <div><br></div> <div>typedef long long ll;</div> <div><br></div> <div>int rmax, cmax;</div> <div><br></div> <div>inline ll gcd(ll a, ll b) {</div> <div>    if(b>a) return gcd(b, a);</div> <div>    if(b==0) return a;</div> <div>    if(a%2==0 && b%2==0) return 2*gcd(a/2, b/2);</div> <div>    if(a%2==0 && b%2==1) return gcd(a/2, b);</div> <div>    if(a%2==1 && b%2==0) return gcd(a, b/2);</div> <div>    return gcd((a-b)/2, b);</div> <div>}</div> <div><br></div> <div>ll DIGIT_BITS=30;</div> <div>ll BASE = 1 << DIGIT_BITS;</div> <div><br></div> <div>ll nbits(ll n) {</div> <div>    return floor(log2(n))+1;</div> <div>}</div> <div><br></div> <div>inline ll lehmer_gcd(ll a, ll b) {</div> <div>    if(a<b) return lehmer_gcd(b, a);</div> <div>    while(b >= BASE) {</div> <div>        ll push = nbits(a) - DIGIT_BITS;</div> <div>        ll x = a >> push;</div> <div>        ll y = b >> push;</div> <div>        ll A=1, B=0, C=0, D=1;</div> <div>        while(1) {</div> <div>            if(y+C==0 || y+D==0) break;</div> <div>            ll q = (x+A) / (y+C);</div> <div>            if(q!=(x+B)/(y+D)) break;</div> <div>            ll tempA=A, tempB=B, tempx=x;</div> <div>            A=C; B=D; x=y;</div> <div>            C=tempA-q*C; D=tempB-q*D; y=tempx-q*y;</div> <div>        }</div> <div>        if(B) {</div> <div>            ll tempa = a;</div> <div>            a = A*a + B*b;</div> <div>            b = C*tempa + D*b;</div> <div>        }</div> <div>        else {</div> <div>            ll tempa = a;</div> <div>            a = b;</div> <div>            b = tempa % b;</div> <div>        }</div> <div>    }</div> <div>    return gcd(a, b);</div> <div>}</div> <div><br></div> <div>class LONG {</div> <div>private:</div> <div>    ll value;</div> <div>public:</div> <div>    LONG(ll v) {</div> <div>        value = v;</div> <div>    }</div> <div>    ll getvalue() {</div> <div>        return value;</div> <div>    }</div> <div>    void setvalue(ll v) {</div> <div>        value = v;</div> <div>    }</div> <div>};</div> <div><br></div> <div>template<class DataType> class TreeNode{</div> <div>private:</div> <div>    int l;</div> <div>    int r;</div> <div>    DataType* Data;</div> <div>    TreeNode* Left;</div> <div>    TreeNode* Right;</div> <div>public:</div> <div>    static int rmax;</div> <div>    static int cmax;</div> <div>    TreeNode() {</div> <div>        TreeNode(0, 0);</div> <div>    }</div> <div>    TreeNode(int l, int r) {</div> <div>        this->l = l;</div> <div>        this->r = r;</div> <div>        Data = NULL;</div> <div>    }</div> <div>    TreeNode(int l, int r, DataType& Data) {</div> <div>        this->Data = &Data;</div> <div>    }</div> <div>    void setInterval(int l, int r) {</div> <div>        this->l = l;</div> <div>        this->r = r;</div> <div>    }</div> <div>    void setData(DataType& Data) {</div> <div>        this->Data = &Data;</div> <div>    }</div> <div>    friend ll queryIN(TreeNode<LONG>* TN, int l, int r);</div> <div>    friend ll queryOUT(TreeNode<TreeNode<LONG> >* TN, int cl, int cr, int rl, int rr);</div> <div>    friend ll updateIN(TreeNode<LONG>*, int, ll);</div> <div>    friend void updateOUT(TreeNode<TreeNode<LONG> >*, int, int, ll);</div> <div>};</div> <div><br></div> <div>typedef TreeNode<LONG> InnerTree;</div> <div>typedef TreeNode<TreeNode<LONG> > OuterTree;</div> <div><br></div> <div>ll queryIN(InnerTree* TN, int l, int r) {</div> <div>    if(TN==NULL) return 0;</div> <div>    if(r < TN->l || TN->r < l) return 0;</div> <div>    if(l <= TN->l && TN->r <= r) return TN->Data->getvalue();</div> <div>    return gcd(queryIN(TN->Left, l, r), queryIN(TN->Right, l, r));</div> <div>}</div> <div><br></div> <div>ll queryOUT(OuterTree *TN, int cl, int cr, int rl, int rr) {</div> <div>    if(TN==NULL) return 0;</div> <div>    if(cr < TN->l || TN->r < cl) return 0;</div> <div>    if(cl <= TN->l && TN->r <= cr) return queryIN(TN->Data, rl, rr);</div> <div>    return gcd(queryOUT(TN->Left, cl, cr, rl, rr), queryOUT(TN->Right, cl, cr, rl, rr));</div> <div>}</div> <div><br></div> <div>ll updateIN(InnerTree* TN, int r, ll k) {</div> <div>    if(TN->l == TN->r) {</div> <div>        TN->Data->setvalue(k);</div> <div>        return k;</div> <div>    }</div> <div>    if(r <= (TN->l + TN->r)/2) {</div> <div>        if(TN->Left == NULL) {</div> <div>            TN->Left = new InnerTree(TN->l, (TN->l + TN->r)/2);</div> <div>        }</div> <div>        ll other = (TN->Right == NULL ? 0 : TN->Right->Data->getvalue());</div> <div>        TN->Data->setvalue(lehmer_gcd(updateIN(TN->Left, r, k), other));</div> <div>    }</div> <div>    else {</div> <div>        if(TN->Right == NULL) {</div> <div>            TN->Right = new InnerTree((TN->l + TN->r)/2 + 1, TN->r);</div> <div>        }</div> <div>        ll other = (TN->Left == NULL ? 0 : TN->Left->Data->getvalue());</div> <div>        TN->Data->setvalue(lehmer_gcd(updateIN(TN->Right, r, k), other));</div> <div>    }</div> <div>    return TN->Data->getvalue();</div> <div>}</div> <div><br></div> <div>void updateOUT(OuterTree* TN, int r, int c, ll k) {</div> <div>    if(TN->Data == NULL) {</div> <div>        TN->Data = new InnerTree(0, rmax);</div> <div>    }</div> <div>    updateIN(TN->Data, r, k);</div> <div>    if(TN->l == TN->r) return;</div> <div>    if(c <= (TN->l + TN->r)/2) {</div> <div>        if(TN->Left == NULL) {</div> <div>            TN->Left = new OuterTree(TN->l, (TN->l + TN->r)/2);</div> <div>        }</div> <div>        updateOUT(TN->Left, r, c, k);</div> <div>    }</div> <div>    else {</div> <div>        if(TN->Right == NULL) {</div> <div>            TN->Right = new OuterTree((TN->l + TN->r)/2 + 1, TN->r);</div> <div>        }</div> <div>        updateOUT(TN->Right, r, c, k);</div> <div>    }</div> <div>}</div> <div><br></div> <div>int main() {</div> <div>    //ifstream cin;</div> <div>    //cin.open("input.txt");</div> <div>    int r, c, n, command;</div> <div>    int cl, cr, rl, rr;</div> <div>    int k;</div> <div>    int i;</div> <div>    cin >> r >> c >> n;</div> <div><br></div> <div>    OuterTree * OutTree = new OuterTree(0, c-1);</div> <div><br></div> <div>    rmax = r-1;</div> <div>    cmax = c-1;</div> <div><br></div> <div>    for(i=0; i<n; i++) {</div> <div>        cin >> command;</div> <div>        if(command==1) {</div> <div>            cin >> rl >> cl;</div> <div>            cin >> k;</div> <div>            updateOUT(OutTree, rl, cl, k);</div> <div>        }</div> <div>        else {</div> <div>            cin >> rl >> cl >> rr >> cr;</div> <div>            cout << queryOUT(OutTree, cl, cr, rl, rr) << endl;</div> <div>        }</div> <div>    }</div> <div>    //cin.close();</div> <div>    return 0;</div> <div>}</div> <div> </div>