Problem

There are $ N $ bus stops clockwise, numbered from $ 1 $ to $ N $ in a circle. Adjacent bus stops are connected by a road. For each $ i \ (1 \ le i \ le N) $, the length of the direct connection between the bus stop $ i $ and the bus stop $ i + 1 $ is $ d_i $ meters. However, bus stop $ N + 1 $ means bus stop $ 1 $.

There are $ M $ buses. The $ j \ (1 \ le j \ le M) $ th bus runs clockwise when $ c_j ='R'$ and counterclockwise when $ c_j ='L' $. It also takes $ t_j $ seconds to depart bus stop $ b_j $ at time $ 0 $ and travel $ 1 $ meters.

In this matter

* The bus keeps running forever
* It doesn't take long to get on and off the bus
* At a bus stop, you can get on and off the bus the moment it passes the bus stop.
* You cannot get on and off the bus except at the bus stop
* You can take as many buses as you like



And.

Process the following query a total of $ Q $ times.

* Find the minimum time required to depart bus stop $ x_k $ at time $ 0 $ and travel to bus stop $ y_k $ using only the bus.

Constraints

The input satisfies the following conditions.

* $ 3 \ leq N \ leq 10 ^ 5 $
* $ 1 \ leq M \ leq 10 ^ 5 $
* $ 1 \ leq Q \ leq 10 ^ 5 $
* $ 1 \ leq d_i \ leq 10 ^ 2 \ (1 \ leq i \ leq N) $
* $ c_j ='R' \ or \'L' \ (1 \ leq j \ leq M) $
* $ 1 \ leq b_j \ leq N \ (1 \ leq j \ leq M) $
* $ 1 \ leq t_j \ leq 10 ^ 5 \ (1 \ leq j \ leq M) $
* $ 1 \ leq x_k, y_k \ leq N \ (1 \ leq k \ leq Q) $
* $ x_k \ neq y_k \ (1 \ leq k \ leq Q) $
* All numbers given in the input are integers

Input

The input is given in the following format.


$ N $ $ M $ $ Q $
$ d_1 $ $ \ ldots $ $ d_N $
$ c_1 $ $ b_1 $ $ t_1 $
$ \ vdots $
$ c_M $ $ b_M $ $ t_M $
$ x_1 $ $ y_1 $
$ \ vdots $
$ x_Q $ $ y_Q $


The number of bus stops $ N $, the number of buses $ M $, and the number of queries $ Q $ are given on the first line, separated by blanks.
Information on the road connecting the adjacent bus stops is given on the second line, separated by blanks.
Bus information is given on the $ M $ line starting from the third line, separated by blanks.
Query information is given in the following $ Q $ line, separated by blanks.

Output

The output consists of $ Q $ lines.
Output the minimum required time for each query.
Print the answer to the $ k $ th query on the $ k $ line.

Examples

Input

3 1 6
1 2 3
R 1 1
1 2
1 3
2 1
2 3
3 1
3 2


Output

1
3
6
3
6
7


Input

4 6 7
45 72 81 47
R 1 47202
L 1 2156
L 2 95728
R 1 30739
L 3 39679
L 4 86568
3 2
3 4
1 2
2 4
4 3
1 4
2 1


Output

431200
629552
431200
629552
275968
101332
528220
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-5;
const ld pi = acos(-1.0);

struct LiChaoTree {
	int sz;
	struct Node {
		int l, r;
		Node* chl; Node* chr;
		LP val;
		Node(int l, int r) :l(l), r(r) {
			val = { 0,INF };
			chl = chr = NULL;
		}
	};
	Node* root;
	LiChaoTree() {
		int max_n = 1e8 + 1;
		sz = 1;
		while (sz < max_n)sz <<= 1;
		root = new Node(0, sz);
	}
	ll calc(LP a, int x) {
		return a.first*x + a.second;
	}
	void add(Node* node, LP a) {
		if (!node)return;
		int l = node->l, r = node->r;
		int m = (l + r) / 2;
		//そのノードでの最小値
		if (calc(node->val, m) > calc(a, m))swap(node->val, a);
		if (r - l == 1)return;
		//左側をさらに更新しなきゃ
		if (calc(node->val, l) > calc(a, l)) {
			if (!node->chl)node->chl = new Node(l, m);
			add(node->chl, a);
		}
		else if (calc(node->val, r) > calc(a, r)) {
			if (!node->chr)node->chr = new Node(m, r);
			add(node->chr, a);
		}
	}
	void add(LP a) {
		add(root, a);
	}
	ll query(int x) {
		ll ret = INF;
		Node* node = root;
		while (node) {
			ret = min(ret, calc(node->val, x));
			int m = (node->l + node->r) / 2;
			if (x < m) {
				node = node->chl;
			}
			else {
				node = node->chr;
			}
		}
		return ret;
	}
};

void solve() {
	int n, m, q; cin >> n >> m >> q;
	vector<int> d(n);
	rep(i, n) {
		cin >> d[i];
	}
	vector<int> rd(n+1);
	rep(i, n) {
		rd[i + 1] = rd[i] + d[i];
	}
	vector<vector<int>> vl(n), vr(n);
	rep(i, m) {
		char c; int b, t;
		cin >> c >> b >> t; b--;
		if (c == 'L') {
			vl[b].push_back(t);
		}
		else {
			vr[b].push_back(t);
		}
	}
	vector<ll> ans(q);
	fill(ans.begin(), ans.end(), INF);
	vector<vector<P>>que(n);
	rep(i, q) {
		int x, y; cin >> x >>y; x--; y--;
		que[x].push_back({ y,i });

	}
	if (vr.size()) {
		LiChaoTree cr;
		rep(i, n) {
			int dist = rd[n]-rd[i];
			rep(j, vr[i].size()) {
				int  t= vr[i][j];
				cr.add({ t,(ll)t*dist });
			}
		}
		rep(i, n) {
			rep(j, vr[i].size()) {
				int t = vr[i][j];
				cr.add({ t,-(ll)t*rd[i] });
			}
			rep(j, que[i].size()) {
				int to = que[i][j].first;
				int id = que[i][j].second;
				ll x = rd[to];
				if (to < i)x += rd[n];
				//if (x < 0)x += rd[n];
				ans[id] = min(ans[id], cr.query(x));
			}
		}
	}
	if (vl.size()) {
		LiChaoTree cl;
		per(i, n) {
			int dist = rd[i];
			rep(j, vl[i].size()) {
				int t = vl[i][j];
				cl.add({ t,(ll)t*dist });
			}
		}
		per(i, n) {
			rep(j, vl[i].size()) {
				int t = vl[i][j];
				cl.add({ t,-(ll)t*(rd[n] - rd[i]) });
			}
			rep(j, que[i].size()) {
				int to = que[i][j].first;
				int id = que[i][j].second;
				ll x = rd[n]-rd[to];
				if (i < to)x += rd[n];
				//if (x < 0)x += rd[n];
				ans[id] = min(ans[id], cl.query(x));
			}
		}
	}
	rep(i, q) {
		cout << ans[i] << endl;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}


