Problem: Problem

Given two sequences of length $ N $, $ A $ and $ B $. First, the $ i $ item in the sequence $ A $ is $ a_i $, and the $ i $ item in the sequence $ B $ is $ b_i $.

Since a total of $ Q $ of statements of the following format are given, create a program that processes in the given order.

Each statement is represented by three integers $ x, y, z $.

* Set the value of the $ y $ item in the sequence $ A $ to $ z $. (When $ x = 1 $)
* Set the value of the $ y $ item in the sequence $ B $ to $ z $. (When $ x = 2 $)
* Find and report the smallest value in the $ z $ item from the $ y $ item in the sequence $ A $. (When $ x = 3 $)
* Find and report the smallest value in the $ z $ item from the $ y $ item in the sequence $ B $. (When $ x = 4 $)
* Change the sequence $ A $ to be exactly the same as the sequence $ B $. (When $ x = 5 $)
* Change the sequence $ B $ to be exactly the same as the sequence $ A $. (When $ x = 6 $)

Constraints

The input satisfies the following conditions.

* $ 2 \ le N \ le 2 \ times 10 ^ 5 $
* $ 2 \ le Q \ le 2 \ times 10 ^ 5 $
* $ 1 \ le a_i \ le 10 ^ 9 $
* $ 1 \ le b_i \ le 10 ^ 9 $
* $ 1 \ le x_i \ le 6 $
* $ 1 \ le y_i \ le N $ (when $ 1 \ le x_i \ le 4 $)
* $ y_i = -1 $ (when $ x_i = 5, 6 $)
* $ 1 \ le z_i \ le 10 ^ 9 $ (when $ x_i = 1, 2 $)
* $ y_i \ le z_i \ le N $ (when $ x_i = 3, 4 $)
* $ z_i = -1 $ (when $ x_i = 5, 6 $)
* All inputs are integers

Input

The input is given in the following format.

$ N $
$ a_ {1} $ $ a_ {2} $ ... $ a_ {N} $
$ b_ {1} $ $ b_ {2} $ ... $ b_ {N} $
$ Q $
$ x_1 $ $ y_1 $ $ z_1 $
$ x_2 $ $ y_2 $ $ z_2 $
...
$ x_Q $ $ y_Q $ $ z_Q $

Output

Every time a statement of $ x = 3 $ or $ x = 4 $ is given by input, the found value is output on one line.

Example

Input

5
1 3 5 7 9
6 2 3 2 6
10
1 3 4
3 4 5
4 2 3
5 -1 -1
2 3 8
3 2 5
4 3 3
1 1 1
6 -1 -1
3 1 5


Output

7
2
2
8
1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
????????????????????????????????? ??§?????§  
??????????????? ??§?????§ ???????´<_??? ?????? Welcome to My Coding Space!
???????????? ??? ?´_???`??????/??? ???i     
?????????????????????????????? ???  |???|     
????????? /?????? /??£??£??£??£/??????|  
??? ???_(__??????/???    ???/ .| .|????????????  
??? ????????????/????????????/??????u??????  
---------------------------------------------------------------------------------------------------*/




int N, A[201010], B[201010], Q;
//--------------------------------------------------------------------------------------------------
#define INF INT_MAX/2
int S, Ami[1010], Bmi[1010];
int AorB[1010]; // -1:none 0:A 1:B
void update(int s) {
    int L = s * S, R = (s + 1) * S;

    Ami[s] = Bmi[s] = INF;
    rep(i, L, R) if (i < N) {
        Ami[s] = min(Ami[s], A[i]);
        Bmi[s] = min(Bmi[s], B[i]);
    }
}
void lazy(int s) {
    int L = s * S, R = (s + 1) * S;

    if (AorB[s] == 0) {
        rep(i, L, R) if (i < N) B[i] = A[i];
        AorB[s] = -1;
    }
    if(AorB[s] == 1) {
        rep(i, L, R) if (i < N) A[i] = B[i];
        AorB[s] = -1;
    }
}
void init() {
    S = sqrt(N);
    rep(i, 0, N / S + 1) update(i);
    rep(i, 0, N / S + 1) AorB[i] = -1;
}
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];

    init();

    cin >> Q;
    rep(i, 0, Q) {
        int x, y, z; cin >> x >> y >> z;

        if (x == 1) {
            y--;
            int s = y / S;
            lazy(s);
            A[y] = z;
            update(s);
        }

        if (x == 2) {
            y--;
            int s = y / S;
            lazy(s);
            B[y] = z;
            update(s);
        }

        if (x == 3) {
            y--;

            int ans = INF;
            rep(i, 0, N / S + 1) {
                int a = i * S, b = (i + 1) * S;
                if (y <= a && b <= z) {
                    if (AorB[i] == 1) ans = min(ans, Bmi[i]);
                    else ans = min(ans, Ami[i]);
                }
                else {
                    if (max(a, y) < min(b, z)) {
                        lazy(i);
                        update(i);
                        rep(j, max(a, y), min(b, z)) ans = min(ans, A[j]);
                    }
                }
            }

            printf("%d\n", ans);
        }

        if (x == 4) {
            y--;

            int ans = INF;
            rep(i, 0, N / S + 1) {
                int a = i * S, b = (i + 1) * S;
                if (y <= a && b <= z) {
                    if (AorB[i] == 0) ans = min(ans, Ami[i]);
                    else ans = min(ans, Bmi[i]);
                }
                else {
                    if (max(a, y) < min(b, z)) {
                        lazy(i);
                        update(i);
                        rep(j, max(a, y), min(b, z)) ans = min(ans, B[j]);
                    }
                }
            }

            printf("%d\n", ans);
        }

        if (x == 5) {
            rep(i, 0, N / S + 1) if (AorB[i] != 0) AorB[i] = 1;
        }

        if (x == 6) {
            rep(i, 0, N / S + 1) if (AorB[i] != 1) AorB[i] = 0;
        }
    }
}