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 <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 1000000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
#define dmp(x) cerr << __LINE__ << " " << #x << " " << x << endl;
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
template<class T>
void dump(vector<T> &vec){
	for(int i=0;i<vec.size();i++){
		cout << vec[i];
		if(i+1<vec.size())cout << ' ';
		else cout << endl;
	}
	return;
}
template<class T>
void input(vector<T>& vec,int n){
	vec.resize(n);
	for(int i=0;i<n;i++){
		cin >> vec[i];
	}
}
// verifyed EDPC Z
// https://atcoder.jp/contests/dp/tasks/dp_z
// Comptype true : min, false : max
template<class T,bool Comptype = true>
struct LiChaoTree{
	using Line = pair<T,T>;	
	int sz = 1;
	vector<Line> seg;
	vector<T> xs;
	LiChaoTree(){}
	void init(vector<T>& x,T id){
		xs = x;
		int n = x.size();
		while(sz<n)sz<<=1;
		xs.resize(sz,x.back());
		seg.resize(sz*2,Line(T(0),id));
	}
	void dump_tree(){
		for(int i=0;i<seg.size();i++){
			cout << i << ':' << seg[i].fi << ' ' << seg[i].sec << endl;
		}
		// dump(xs);
	}
	static inline T f(Line l,ll x){
		return l.fi*x+l.sec;
	}	
	void add(Line line,int k,int l ,int r){
		int mid = (l+r)/2;
		T lx = xs[l];
		T mx = xs[mid];
		T rx = xs[r-1];
		bool lb = (f(line,lx)<f(seg[k],lx));
		bool mb = (f(line,mx)<f(seg[k],mx));
		bool rb = (f(line,rx)<f(seg[k],rx));
		if((lb==Comptype)&&(rb==Comptype)){
			seg[k] = line;
			return;
		}else if((lb!=Comptype)&&(rb!=Comptype)){
			return;
		}else{
			if(mb==Comptype)swap(seg[k],line);
			if(lb!=mb){
				add(line,2*k+1,l,mid);
			}else{
				add(line,2*k+2,mid,r);
			}
		}
	}
	void add(Line line){
    // cout << "add :" << line.fi << ' ' << line.sec << endl;
		add(line,0,0,sz);
	}
	T query(int k){
		T x = xs[k];
		k += sz-1;
		T ret = f(seg[k],x);
		while(k>0){
			k = (k-1)/2;
			T tmp = f(seg[k],x);
			if((tmp<ret)==Comptype)ret = tmp;
		}
		return ret;
	}
};
int solve(){
	int N;
	ll C;
	vector<ll> h;
	LiChaoTree<ll> seg;
	vector<ll> dp;
	cin >> N >> C;
	input(h,N);
	dp.resize(N,0ll);
	seg.init(h,LLINF);
	seg.add(make_pair(-2*h[0],dp[0]+h[0]*h[0]));
	for(int i=1;i<N;i++){
		// seg.dump_tree();
		dp[i] = h[i]*h[i]+C+seg.query(i);
		// cout << i << ' ' << dp[i] << endl;
		seg.add(make_pair(-2ll*h[i],h[i]*h[i]+dp[i]));
	}
	cout << dp[N-1] << endl;
	return 0;
}
int N,M,Q;
ll d[100100];
ll rui[300100];
struct bus{
  char c;
  ll b,t;
  bus(){}
  bus(char c,ll b,ll t):c(c),b(b),t(t){}
  bool operator < (const bus& a) const{
    return b < a.b;
  }
};
bus bs[200100];
struct query{
  int x,y,id;
  query(){}
  query(int x,int y,int id):x(x),y(y),id(id){}
  bool operator < (const query& a) const{
    return x < a.x;
  }
};
query qs[100100];
ll rans[100100],lans[100100];
vector<ll> qpos;
void solveR(){
  vector<bus> rb;
  for(int i=0;i<M;i++){
    if(bs[i].c=='R'){
      rb.pb(bs[i]);
      rb.pb(bus(bs[i].c,bs[i].b+N,bs[i].t));
      rb.pb(bus(bs[i].c,bs[i].b+2*N,bs[i].t));
    }
  }
  sort(all(rb));
  LiChaoTree<ll> seg;
  seg.init(qpos,LLINF);
  int idx = 0; 
  for(int i=0;i<Q;i++){
    query q = qs[i];
    while(idx<rb.size()&&rb[idx].b<=q.x+N){
      bus& b = rb[idx];
      seg.add(make_pair(b.t,-b.t*rui[b.b]));
      idx++;
    }
    if(q.x<q.y){
      rans[q.id] = seg.query(q.y+N);
    }else{
      rans[q.id] = seg.query(q.y+2*N);
    }
  }
  // cout << "rans" << endl;
  // for(int i=0;i<Q;i++){
  //   cout << rans[i] << endl;
  // }
  return;
}
void solveL(){
  vector<bus> lb;
  for(int i=0;i<M;i++){
    if(bs[i].c=='L'){
      lb.pb(bs[i]);
      lb.pb(bus(bs[i].c,bs[i].b+N,bs[i].t));
      lb.pb(bus(bs[i].c,bs[i].b+2*N,bs[i].t));
    }
  }
  sort(all(lb));
  reverse(all(lb));
  LiChaoTree<ll> seg;
  seg.init(qpos,LLINF);
  int idx = 0; 
  for(int i=Q-1;i>=0;i--){
    query q = qs[i];
    while(idx<lb.size()&&lb[idx].b>=q.x+N){
      bus& b = lb[idx];
      seg.add(make_pair(-b.t,b.t*rui[b.b]));
      idx++;
    }
    if(q.x<q.y){
      lans[q.id] = seg.query(q.y);
    }else{
      lans[q.id] = seg.query(q.y+N);
    }
  }
  // cout << "lans" << endl;
  // for(int i=0;i<Q;i++){
  //   cout << lans[i] << endl;
  // }
  return;
}
int main(){
  cin >> N >> M >> Q;
  for(int i=1;i<=N;i++){
    cin >> d[i];
    rui[i] = rui[i-1]+d[i];
  }
  for(int i=1;i<=N;i++){
    rui[N+i] = rui[N+i-1]+d[i];
  }
  for(int i=1;i<=N;i++){
    rui[2*N+i] = rui[2*N+i-1]+d[i];
  }
  for(int i=0;i<=3*N;i++){
    qpos.pb(rui[i]);
    //cout << rui[i] << ' ';
  }
  //cout << endl;
  for(int i=0;i<M;i++){
    cin >> bs[i].c >> bs[i].b >> bs[i].t;
    bs[i].b--;
  }
  for(int i=0;i<Q;i++){
    int x,y;
    cin >> x >> y;
    x--;y--;
    qs[i] = query(x,y,i);
  }
  sort(qs,qs+Q);
  solveR();
  solveL();
  for(int i=0;i<Q;i++){
   cout << min(lans[i],rans[i]) << endl;
  } 
  return 0;
}

