Problem: In the famous Oh-Suit-United tournament, two teams are playing against each other for the grand prize of precious pepper points.

The first team consists of n players, and the second team consists of m players. Each player has a potential: the potential of the i-th player in the first team is a_i, and the potential of the i-th player in the second team is b_i.

In the tournament, all players will be on the stage in some order. There will be a scoring device, initially assigned to an integer k, which will be used to value the performance of all players.

The scores for all players will be assigned in the order they appear on the stage. Let the potential of the current player be x, and the potential of the previous player be y (y equals x for the first player). Then, x-y is added to the value in the scoring device, Afterwards, if the value in the scoring device becomes negative, the value will be reset to 0. Lastly, the player's score is assigned to the current value on the scoring device. The score of a team is the sum of the scores of all its members.

As an insane fan of the first team, Nezzar desperately wants the biggest win for the first team. He now wonders what is the maximum difference between scores of the first team and the second team.

Formally, let the score of the first team be score_f and the score of the second team be score_s. Nezzar wants to find the maximum value of score_f - score_s over all possible orders of players on the stage.

However, situation often changes and there are q events that will happen. There are three types of events:

  * 1 pos x — change a_{pos} to x; 
  * 2 pos x — change b_{pos} to x; 
  * 3 x — tournament is held with k = x and Nezzar wants you to compute the maximum value of score_f - score_s. 



Can you help Nezzar to answer the queries of the third type?

Input

The first line contains three integers n, m, and q (1 ≤ n,m ≤ 2 ⋅ 10^5, 1 ≤ q ≤ 5 ⋅ 10^5).

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^6).

The third line contains m integers b_1, b_2, …, b_m (0 ≤ b_i ≤ 10^6).

The following q lines contain descriptions of events, described in the statement, each in one of the three possible formats:

  * 1 pos x (1 ≤ pos ≤ n, 0 ≤ x ≤ 10^6); 
  * 2 pos x (1 ≤ pos ≤ m, 0 ≤ x ≤ 10^6); 
  * 3 x (0 ≤ x ≤ 10^6). 

Output

For each query of the third type print the answer to this query.

Examples

Input


3 4 3
1 2 7
3 4 5 6
3 5
1 1 10
3 5


Output


-4
9


Input


7 8 12
958125 14018 215153 35195 90380 30535 204125
591020 930598 252577 333333 999942 1236 9456 82390
3 123458
2 4 444444
3 123456
1 2 355555
3 123478
3 1111
2 6 340324
3 1111
2 8 999999
2 7 595959
3 222222
3 100


Output


1361307
1361311
1702804
1879305
1821765
1078115
1675180

Note

In the first query of the first test, the tournament is held with k = 5. It would be optimal to arrange players in such way (here their potentials are written):

\underline{7}, 3, 5, 4, 6, \underline{1}, \underline{2} (underlined numbers are potentials of players that are from the first team). 

The individual scores of players, numbered in the order of their appearance, are:

  * max(5 + (7 - 7), 0) = 5 for the \underline{1}-st player; 
  * max(5 + (3 - 7), 0) = 1 for the 2-nd player; 
  * max(1 + (5 - 3), 0) = 3 for the 3-rd player; 
  * max(3 + (4 - 5), 0) = 2 for the 4-th player; 
  * max(2 + (6 - 4), 0) = 4 for the 5-th player; 
  * max(4 + (1 - 6), 0) = 0 for the \underline{6}-th player; 
  * max(0 + (2 - 1), 0) = 1 for the \underline{7}-th player. 



So, score_f = 5 + 0 + 1 = 6 and score_s = 1 + 3 + 2 + 4 = 10. The score difference is 6 - 10 = -4. It can be proven, that it is the maximum possible score difference.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

/** Binary-indexed tree
 *
 *  A binary indexed tree with N nodes of type T provides the
 *  following two functions for 0 <= i <= N:
 *
 *      prefix(int i) -> prefix_iterator<T>
 *      suffix(int i) -> suffix_iterator<T>
 *
 *  such that size(suffix(i) intersect prefix(j)) = (1 if i < j else 0).
 *  Furthermore, the resulting lists always have size at most log_2(N).
 *
 *  This can be used to implement either point-update/(prefix|suffix)-query or
 *  (prefix|suffix)-update/point-query over a virtual array of size N of a
 *  commutative monoid. This can be generalized to implement
 *  point-update/range-query or range-update/point-query over a virtual array
 *  of size N of a commutative group.
 *
 *  With 0-indexed data, prefixes are more natural:
 *   * For range update/query, use for_prefix for the ranges and for_suffix for the points.
 *   * For prefix update/query, no change.
 *   * For suffix update/query, use for_prefix(point + 1); 1-index the data.
 */
template <typename T> class binary_indexed_tree {
private:
	std::vector<T> dat;
public:
	binary_indexed_tree() {}
	explicit binary_indexed_tree(size_t N) : dat(N) {}
	binary_indexed_tree(size_t N, const T& t) : dat(N, t) {}

	size_t size() const { return dat.size(); }
	const std::vector<T>& data() const { return dat; }
	std::vector<T>& data() { return dat; }

private:
	template <typename I, typename S = I> struct iterator_range {
	private:
		I begin_;
		S end_;
	public:
		iterator_range() : begin_(), end_() {}
		iterator_range(const I& begin__, const S& end__) : begin_(begin__), end_(end__) {}
		iterator_range(I&& begin__, S&& end__) : begin_(begin__), end_(end__) {}
		I begin() const { return begin_; }
		S end() const { return end_; }
	};

public:
	class const_suffix_iterator {
	private:
		const T* dat;
		int a;
		const_suffix_iterator(const T* dat_, int a_) : dat(dat_), a(a_) {}
		friend class binary_indexed_tree;
	public:
		friend bool operator != (const const_suffix_iterator& i, const const_suffix_iterator& j) {
			assert(j.dat == nullptr);
			return i.a < j.a;
		}
		const_suffix_iterator& operator ++ () {
			a |= a+1;
			return *this;
		}
		const T& operator * () const {
			return dat[a];
		}
	};
	using const_suffix_range = iterator_range<const_suffix_iterator>;
	const_suffix_range suffix(int a) const {
		assert(0 <= a && a <= int(dat.size()));
		return const_suffix_range{const_suffix_iterator{dat.data(), a}, const_suffix_iterator{nullptr, int(dat.size())}};
	}

	class suffix_iterator {
	private:
		T* dat;
		int a;
		suffix_iterator(T* dat_, int a_) : dat(dat_), a(a_) {}
		friend class binary_indexed_tree;
	public:
		friend bool operator != (const suffix_iterator& i, const suffix_iterator& j) {
			assert(j.dat == nullptr);
			return i.a < j.a;
		}
		suffix_iterator& operator ++ () {
			a |= a+1;
			return *this;
		}
		T& operator * () const {
			return dat[a];
		}
	};
	using suffix_range = iterator_range<suffix_iterator>;
	suffix_range suffix(int a) {
		assert(0 <= a && a <= int(dat.size()));
		return suffix_range{suffix_iterator{dat.data(), a}, suffix_iterator{nullptr, int(dat.size())}};
	}

	class const_prefix_iterator {
	private:
		const T* dat;
		int a;
		const_prefix_iterator(const T* dat_, int a_) : dat(dat_), a(a_) {}
		friend class binary_indexed_tree;
	public:
		friend bool operator != (const const_prefix_iterator& i, const const_prefix_iterator& j) {
			assert(j.dat == nullptr);
			return i.a > 0;
		}
		const_prefix_iterator& operator ++ () {
			a &= a-1;
			return *this;
		}
		const T& operator * () const {
			return dat[a-1];
		}
	};
	using const_prefix_range = iterator_range<const_prefix_iterator>;
	const_prefix_range prefix(int a) const {
		return const_prefix_range{const_prefix_iterator{dat.data(), a}, const_prefix_iterator{nullptr, 0}};
	}

	class prefix_iterator {
	private:
		T* dat;
		int a;
		prefix_iterator(T* dat_, int a_) : dat(dat_), a(a_) {}
		friend class binary_indexed_tree;
	public:
		friend bool operator != (const prefix_iterator& i, const prefix_iterator& j) {
			assert(j.dat == nullptr);
			return i.a > 0;
		}
		prefix_iterator& operator ++ () {
			a &= a-1;
			return *this;
		}
		T& operator * () const {
			return dat[a-1];
		}
	};
	using prefix_range = iterator_range<prefix_iterator>;
	prefix_range prefix(int a) {
		return prefix_range{prefix_iterator{dat.data(), a}, prefix_iterator{nullptr, 0}};
	}
};

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int N, M, Q; cin >> N >> M >> Q;

	vector<int> A(N); for (auto& a : A) cin >> a;
	vector<int> B(M); for (auto& b : B) cin >> b;
	const int V = int(1.1e6);

	int64_t A_tot = 0;
	set<pair<int, int>> A_set;
	for (int i = 0; i < N; i++) {
		A_tot += A[i];
		A_set.insert({A[i], i});
	}
	int64_t B_tot = 0;
	set<pair<int, int>> B_set;
	binary_indexed_tree<pair<int, int64_t>> B_bit(V);
	for (int j = 0; j < M; j++) {
		B_tot += B[j];
		B_set.insert({B[j], j});
		for (auto& a : B_bit.suffix(B[j])) {
			a.first++;
			a.second += B[j];
		}
	}

	auto get_B_sum = [&](int v0) -> int64_t {
		if (v0 <= 0) {
			return int64_t(v0) * M;
		}
		int64_t res = int64_t(v0) * M;
		for (const auto& a : B_bit.prefix(v0)) {
			res -= a.first * int64_t(v0);
			res += a.second;
		}
		return res;
	};

	auto get_A_val = [&](int v0) -> int64_t {
		int min_all = min(A_set.begin()->first, B_set.begin()->first);
		int64_t res = v0 + (N-1) * int64_t(min(v0, min_all)) - get_B_sum(v0);
		return res;
	};
	auto get_B_val = [&](int v0) -> int64_t {
		int min_all = min(A_set.begin()->first, B_set.begin()->first);
		int64_t res = N * int64_t(min(v0, min_all)) - get_B_sum(v0);
		return res;
	};

	auto query = [&](int K) -> int64_t {

		int64_t res = min({
			get_A_val(A_set.begin()->first - K),
			get_B_val(B_set.begin()->first - K),
			get_A_val(A_set.rbegin()->first - K),
			get_B_val(B_set.rbegin()->first - K)
		});
		int min_all = min(A_set.begin()->first, B_set.begin()->first);
		// Check things just under to min_all + K
		{
			auto it = A_set.lower_bound({min_all + K + 1, -1});
			if (it != A_set.begin()) {
				res = min(res, get_A_val(prev(it)->first - K));
			}
		}
		{
			auto it = B_set.lower_bound({min_all + K + 1, -1});
			if (it != B_set.begin()) {
				res = min(res, get_B_val(prev(it)->first - K));
			}
		}

		// Check choices of A around B_set.rbegin()->first + K
		{
			auto it = A_set.lower_bound({B_set.rbegin()->first + K + 1, -1});
			if (it != A_set.end()) {
				res = min(res, get_A_val(it->first - K));
			}
			if (it != A_set.begin()) {
				res = min(res, get_A_val(prev(it)->first - K));
			}
		}

		return res;
	};

	for (int q = 0; q < Q; q++) {
		int op; cin >> op;
		if (op == 1) {
			int i; cin >> i; i--;
			A_tot -= A[i];
			A_set.erase({A[i], i});
			cin >> A[i];
			A_tot += A[i];
			A_set.insert({A[i], i});
		} else if (op == 2) {
			int j; cin >> j; j--;
			B_tot -= B[j];
			B_set.erase({B[j], j});
			for (auto& a : B_bit.suffix(B[j])) {
				a.first--;
				a.second -= B[j];
			}
			cin >> B[j];
			B_tot += B[j];
			B_set.insert({B[j], j});
			for (auto& a : B_bit.suffix(B[j])) {
				a.first++;
				a.second += B[j];
			}
		} else if (op == 3) {
			int k; cin >> k;
			cout << A_tot - B_tot - query(k) << '\n';
		}
	}

	return 0;
}

// Just add a player of potential P[0] - K at the start; then, player's score is P[i] - min(players before him)
// The main choice is P[0]; then, take all the B's in decreasing order and all the A's in increasing order
// We can simplify down to minimizing
//   sum min(players before A) - sum min(players before B)
// If we move an A to the front,
//   = P[0]-K + (N-1) * min(P[0]-K, min(everything)) - sum min(P[0]-K, B[i])
// If we move a B to the front:
//   = N * min(P[0]-K, min(everything)) - sum min(P[0], B[i]+K)
//
// If P[0] - K <= min(everything), then everything gets P[0] - K, which equals
//
// If P[0]-K >= min(everything), we just want it to be either maximum B, or one of the A's closest to Bmax + K, Bmax2 + K
//
// If we move an A[i] to the start, we lose a flat min(A,B)