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>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<class Z> Z rng(Z a, Z b) {
  static mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<Z>(a, b - 1)(mt);
}
namespace PersistentRandomizedBinarySearchTree {
  using T = int;
  static T op(const T& a, const T& b) { return min(a, b); }
  static constexpr T e() { return 2e9; }
  using U = char;
  static T ap(const U& f, T a) { return a; }
  static U cp(const U& g, U f) { return f; }
  static constexpr U id() { return 0; }
  static T op(const T& a, const T& b, const T& c) { return op(op(a, b), c); }

  struct Node;
  using Tree = shared_ptr<Node>;
  struct Node {
    int sz = 0, h = 0;
    Tree lch = nullptr, rch = nullptr;
    T val = e(), acc = e();
    U laz = id();
    bool rev = false;
    Node() {}
    Node(Tree lch, Tree rch, const T& val, const T& acc, const U& laz = id(), bool rev = false) :
      sz(lch->sz + 1 + rch->sz), h(max(lch->h, rch->h) + 1), lch(lch), rch(rch), val(val), acc(acc), laz(laz), rev(rev) {}
  };
  Tree nil = make_shared<Node>();

  Tree apply(Tree t, const U& f) {
    return make_shared<Node>(t->lch, t->rch, ap(f, t->val), ap(f, t->acc), cp(f, t->laz), t->rev);
  }
  Tree reverse(Tree t) {
    return make_shared<Node>(t->rch, t->lch, t->val, t->acc, t->laz, !t->rev);
  }
  void push(Tree t) {
    if (!(t->laz == id())) {
      t->lch->val = ap(t->laz, t->lch->val);
      t->lch->acc = ap(t->laz, t->lch->acc);
      t->lch->laz = cp(t->laz, t->lch->laz);
      t->rch->val = ap(t->laz, t->rch->val);
      t->rch->acc = ap(t->laz, t->rch->acc);
      t->rch->laz = cp(t->laz, t->rch->laz);
      t->laz = id();
    }
    if (t->rev) {
      swap(t->lch->lch, t->lch->rch);
      t->lch->rev ^= true;
      swap(t->rch->lch, t->rch->rch);
      t->rch->rev ^= true;
      t->rev = false;
    }
  }
  Tree update(Tree t, Tree lch, Tree rch) {
    return make_shared<Node>(lch, rch, t->val, op(lch->acc, t->val, rch->acc));
  }

  template<class Itr> Tree build(Itr first, Itr last) {
    int n = distance(first, last);
    if (!n) return nil;
    Itr middle = next(first, n >> 1);
    Tree lch = build(first, middle), rch = build(next(middle), last);
    return make_shared<Node>(lch, rch, *middle, op(lch->acc, *middle, rch->acc));
  }
  template<class Itr> Itr dump(Tree t, Itr res) {
    if (t == nil) return res;
    push(t);
    res = dump(t->lch, res);
    *res++ = t->val;
    return dump(t->rch, res);
  }
  Tree rebuild(Tree t) {
    V<T> v(t->sz);
    dump(t, begin(v));
    return build(begin(v), end(v));
  }

  Tree merge(Tree l, Tree r) {
    if (l == nil) return r;
    if (r == nil) return l;
    if (rng(0, l->sz + r->sz) < l->sz) {
      push(l);
      return update(l, l->lch, merge(l->rch, r));
    } else {
      push(r);
      return update(r, merge(l, r->lch), r->rch);
    }
  }
  Tree merge(Tree l, Tree m, Tree r) { return merge(merge(l, m), r); }
  pair<Tree, Tree> split(Tree t, int i) {
    assert(0 <= i and i <= t->sz);
    if (t == nil) return {nil, nil};
    push(t);
    if (i <= t->lch->sz) {
      Tree l, lch;
      tie(l, lch) = split(t->lch, i);
      return {l, update(t, lch, t->rch)};
    } else {
      Tree r, rch;
      tie(rch, r) = split(t->rch, i - t->lch->sz - 1);
      return {update(t, t->lch, rch), r};
    }
  }
  tuple<Tree, Tree, Tree> split(Tree t, int l, int r) {
    assert(0 <= l and l <= r and r <= t->sz);
    Tree lt, mt, rt;
    tie(lt, rt) = split(t, r);
    tie(lt, mt) = split(lt, l);
    return make_tuple(lt, mt, rt);
  }

  Tree insert(Tree t, int i, const T& a) {
    assert(0 <= i and i <= t->sz);
    Tree l, r;
    tie(l, r) = split(t, i);
    return merge(l, make_shared<Node>(nil, nil, a, a), r);
  }
  Tree erase(Tree t, int i) {
    assert(0 <= i and i < t->sz);
    Tree l, r;
    tie(l, ignore, r) = split(t, i, i + 1);
    return merge(l, r);
  }

  T get(Tree t, int i) {
    assert(0 <= i and i < t->sz);
    if (i == t->lch->sz) return t->val;
    push(t);
    if (i < t->lch->sz) return get(t->lch, i);
    else return get(t->rch, i - t->lch->sz - 1);
  }
  Tree set(Tree t, int i, const T& a) {
    assert(0 <= i and i < t->sz);
    push(t);
    if (i == t->lch->sz) {
      return make_shared<Node>(t->lch, t->rch, a, op(t->lch->acc, a, t->rch->acc));
    } else if (i < t->lch->sz) {
      return update(t, set(t->lch, i, a), t->rch);
    } else {
      return update(t, t->lch, set(t->rch, i - t->lch->sz - 1, a));
    }
  }

  T acc(Tree t, int l, int r) {
    if (l <= 0 and t->sz <= r) return t->acc;
    push(t);
    T resl = l < t->lch->sz ? acc(t->lch, l, r) : e();
    T resr = t->lch->sz + 1 < r ? acc(t->rch, l - t->lch->sz - 1, r - t->lch->sz - 1) : e();
    T resm = l <= t->lch->sz and t->lch->sz < r ? t->val : e();
    return op(resl, resm, resr);
  }
  Tree act(Tree t, int l, int r, const U& f) {
    if (l <= 0 and t->sz <= r) return apply(t, f);
    push(t);
    Tree lch = nil, rch = nil;
    T val = e();
    if (l < t->lch->sz) lch = act(t->lch, l, r, f);
    if (t->lch->sz + 1 < r) rch = act(t->rch, l - t->lch->sz - 1, r - t->lch->sz - 1, f);
    if (l <= t->lch->sz and t->lch->sz < r) val = ap(f, t->val);
    return make_shared<Node>(lch, rch, val, op(lch->acc, val, rch->acc));
  }
  Tree reverse(Tree t, int l, int r) {
    Tree lt, mt, rt;
    tie(lt, mt, rt) = split(t, l, r);
    return merge(lt, reverse(mt), rt);
  }

  int lower_bound(Tree t, const T& a) {
    if (t == nil) return 0;
    push(t);
    if (t->val < a) return t->lch->sz + 1 + lower_bound(t->rch, a);
    else return lower_bound(t->lch, a);
  }
  int upper_bound(Tree t, const T& a) {
    if (t == nil) return 0;
    push(t);
    if (a < t->val) return upper_bound(t->lch, a);
    else return t->lch->sz + 1 + upper_bound(t->rch, a);
  }
  int count(Tree t, const T& a) { return upper_bound(t, a) - lower_bound(t, a); }
  Tree set_insert(Tree t, const T& a, bool multi = true) {
    if (!multi and count(t, a)) return t;
    return insert(t, lower_bound(t, a), a);
  }
  Tree set_erase(Tree t, const T& a) {
    assert(count(t, a));
    return erase(t, lower_bound(t, a));
  }
}
namespace PRBST = PersistentRandomizedBinarySearchTree;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> a(n); for (auto&& e : a) cin >> e;
  V<> b(n); for (auto&& e : b) cin >> e;
  auto ta = PRBST::build(begin(a), end(a));
  auto tb = PRBST::build(begin(b), end(b));
  int q; cin >> q;
  while (q--) {
    int x, y, z; cin >> x >> y >> z, --y;
    if (x == 1) {
      ta = PRBST::set(ta, y, z);
    } else if (x == 2) {
      tb = PRBST::set(tb, y, z);
    } else if (x == 3) {
      cout << acc(ta, y, z) << '\n';
    } else if (x == 4) {
      cout << acc(tb, y, z) << '\n';
    } else if (x == 5) {
      ta = tb;
    } else {
      tb = ta;
    }
  }
}