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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;

struct Node {
	char val;
	shared_ptr<Node>next;
	Node() :val(0), next(nullptr) {

	}
	Node(const Node&node_) :val(node_.val), next(node_.next) {

	}
};
shared_ptr<Node>insert(shared_ptr<Node>&node, int pos, char value) {
	if (!pos) {
		shared_ptr<Node>newNode = make_shared<Node>();
		newNode->val = value;
		newNode->next = nullptr;
		return newNode;
	}
	else {
		node->next = insert(node->next, pos - 1, value);
		return node;
	}
}

shared_ptr<Node>immutable_insert(const shared_ptr<Node>&node, int pos, char value) {
	shared_ptr<Node> copyNode = make_shared<Node>(*node);
	if (!pos) {
		shared_ptr<Node> newNode = make_shared<Node>();
		newNode->val = value;
		newNode->next = copyNode;
		return newNode;
	}
	else {
		copyNode->next = immutable_insert(node->next, pos - 1, value);
		return copyNode;
	}
}
namespace perseg {
	using Value = int;
	const Value ini = INT_MAX;

	struct permanent_segtree {
		Value val;
		int l, r;
		vector<shared_ptr<permanent_segtree>>chs;
	public:
		permanent_segtree(const int size_) :val(ini), l(0), r(size_), chs(2, nullptr) {

		}
		permanent_segtree(const Value& val_, const int l_, const int r_) :val(val_), l(l_), r(r_), chs(2, nullptr) {

		}
		permanent_segtree(const permanent_segtree&tree_) :val(tree_.val), l(tree_.l), r(tree_.r), chs(tree_.chs) {

		}
		shared_ptr<permanent_segtree>getch(const int num_) {
			const int amid = (l + r) / 2;

			if (chs[num_] == nullptr) {
				if (num_ == 0) {
					chs[0] = make_shared<permanent_segtree>(ini, l, amid);
				}
				else {
					chs[1] = make_shared<permanent_segtree>(ini, amid, r);
				}
			}
			return chs[num_];

		}
		Value eval_value(const Value&l, const Value&r)const {
			return min(l, r);
		}
		// min [a, b)
		Value  query(int a, int b, int k) {
			if (r <= a or b <= l) return ini;
			if (a <= l and r <= b) return val;
			const int m = (l + r) / 2;
			const Value al(getch(0)->query(a, b, k));
			const Value ar(getch(1)->query(a, b, k));
			return eval_value(al, ar);
		}
	};

	shared_ptr<permanent_segtree>immutable_update(const shared_ptr<permanent_segtree>&tree, const int k, const Value a) {
		if (k == tree->l&&tree->l + 1 == tree->r) {
			shared_ptr<permanent_segtree>new_tree(make_shared<permanent_segtree>(a, tree->l, tree->r));
			return new_tree;
		}
		else {
			shared_ptr<permanent_segtree>copy_tree = (make_shared<permanent_segtree>(*tree));
			assert(tree->l + 1 < tree->r);
			const int amid = (tree->l + tree->r) / 2;
			if (k < amid) {
				copy_tree->chs[0] = immutable_update(tree->getch(0), k, a);
			}
			else {
				copy_tree->chs[1] = immutable_update(tree->getch(1), k, a);
			}
			copy_tree->val = copy_tree->eval_value(copy_tree->getch(0)->val, copy_tree->getch(1)->val);

			return copy_tree;
		}
	}
};

int main() {
	int N;cin>>N;
	using namespace perseg;
	vector<std::shared_ptr<permanent_segtree>>trees(2,make_shared<permanent_segtree>(N));
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < N; ++j) {
			int a;cin>>a;
			trees[i]=immutable_update(trees[i],j,a);
		}
	}
	int Q;cin>>Q;
	while (Q--) {
		int x,y,z;cin>>x>>y>>z;
		x--;
		int ope=x/2;
		int to=x%2;
		if (ope == 0) {
			trees[to]=immutable_update(trees[to],y-1,z);
		}
		else if (ope == 1) {
			Value val=trees[to]->query(y-1,z,1);
			cout<<val<<endl;
		}
		else if (ope == 2) {
			trees[to]= (make_shared<permanent_segtree>(*trees[!to]));
		}
	}
	return 0;
}