At Aiz Pharmaceutical, research on chemical substances is carried out every day. I am currently studying the code name "Alpha", a chemical substance that has a structure in which molecules from $ 1 $ to $ N $ are linearly arranged from the left end to the right end.

Using the technology developed by Aiz Pharmaceutical, the positions of the molecules that make up alpha can be swapped. Swapping can only be done in a fixed procedure, but you can start in the middle of the procedure and end in the middle. Suppose that the operation of exchanging the $ a $ and $ b $ th numerator from the left end is written as $ (a, b) $. For example, when the procedure determined by $ N = 5 $ is $ (1,3), (2,5), (4,3), (1,5) $, the $ 1 $ th operation $ (1,3) ) Starting with $ and ending with $ 3 $ th operation $ (4,3) $, or starting with $ 2 $ th operation $ (2,5) $ and ending with $ 4 $ th operation $ (1,5) $ You can also.

You decided to select the start and end positions in the alpha molecule replacement procedure and perform a simulation to investigate the state of the molecule after replacement.

A procedure for replacing the molecule of alpha is given. Create a program that answers questions about the position of molecules in each simulation after several simulations. The question has the form of 1. or 2.

1. At the beginning, what position was the molecule located at the $ i $ position from the left end after the end?
2. At what position is the molecule that was originally located at the $ i $ position after the end?



However, each simulation shall start from the initial state of alpha (a state in which molecules from $ 1 $ to $ N $ are linearly arranged from the left end to the right end).



input

The input is given in the following format.


$ N $ $ K $ $ Q $
$ a_1 $ $ b_1 $
$ a_2 $ $ b_2 $
::
$ a_K $ $ b_K $
$ query_1 $
$ query_2 $
::
$ query_Q $


The number of molecules that make up alpha in the first line $ N $ ($ 2 \ leq N \ leq 100,000 $), the length of the replacement procedure $ K $ ($ 1 \ leq K \ leq 100,000 $), and the state of the molecules after replacement Given the number of times to look up $ Q $ ($ 1 \ leq Q \ leq 100,000 $). The following $ K $ line gives each operation $ a_i, b_i $ ($ 1 \ leq a_i, b_i \ leq N $, $ a_i \ ne b_i $) in the swap procedure. The $ i $ th operation represents an operation of swapping the $ a_i $ th and $ b_i $ th numerator from the left end. The following $ Q $ line is given a question asking the state of the molecule after the replacement. Each $ query_i $ is given in one of the following formats:


1 $ s $ $ t $ $ x $


Or


2 $ s $ $ t $ $ x $


If the first number is 1, the swap in the swap procedure is from $ s $ to $ t $ ($ 1 \ leq s \ leq t \ leq K $) and then the $ x $ th ($ 1) from the left. \ leq x \ leq N $) represents a question asking what the numerator number is. If the first number is 2, the swap in the swap procedure is from $ s $ to $ t $ ($ 1 \ leq s \ leq t \ leq K $) and then $ x $ ($ 1 \ leq). x \ leq N $) represents a question asking what number the numerator is from the left.

output

Output the answer to each question on one line.

Examples

Input

6 5 8
1 3
2 5
3 4
2 4
2 5
1 1 5 1
1 1 5 2
1 1 5 3
1 1 5 4
1 1 5 5
1 1 5 6
2 3 4 2
1 1 1 1


Output

3
2
4
5
1
6
4
3


Input

None


Output

None
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0425"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#endif
//BEGIN CUT HERE
struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct Mo{
  using F = function<void(int)>;
  vector<int> ls,rs,ord;
  int n,width,nl,nr,ptr;
  F expandL,expandR;
  F shrinkL,shrinkR;

  Mo(int n,int width,F expandL,F expandR,F shrinkL,F shrinkR):
    n(n),width(width),nl(0),nr(0),ptr(0),
    expandL(expandL),expandR(expandR),
    shrinkL(shrinkL),shrinkR(shrinkR){}

  Mo(int n,int width,F expand,F shrink){
    *this=Mo(n,width,expand,expand,shrink,shrink);
  }

  void add(int l,int r){
    ls.emplace_back(l);
    rs.emplace_back(r);
  }

  void build(){
    ord.resize(ls.size());
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),
         [&](int a,int b){
           if(ls[a]/width!=ls[b]/width) return ls[a]<ls[b];
           return bool((rs[a]<rs[b])^((ls[a]/width)&1));
         });
  }

  int process(){
    if(ptr==(int)ord.size()) return -1;
    const int idx=ord[ptr++];
    while(nl>ls[idx]) expandL(--nl);
    while(nr<rs[idx]) expandR(nr++);
    while(nl<ls[idx]) shrinkL(nl++);
    while(nr>rs[idx]) shrinkR(--nr);
    return idx;
  }
};
//END CUT HERE
#ifndef call_from_test

#define call_from_test
#include "../math/factorize.cpp"
#include "../tools/fastio.cpp"
#include "../tools/vec.cpp"
#include "../tree/eulertourforedge.cpp"
#undef call_from_test

//INSERT ABOVE HERE
signed DWANGO2017FINAL_B(){
  using ll = long long;
  int n,q;
  cin>>n>>q;
  vector<int> x(n);
  for(int i=0;i<n;i++) cin>>x[i];

  const int RT = 40;
  auto acc=make_v<int>(RT,n+1);
  fill_v<int>(acc,0);

  using P = pair<int, int>;
  vector<vector<P> > v(n);
  for(int i=0;i<n;i++){
    for(auto p:factorize(x[i])){
      if(p.first<RT) acc[p.first][i+1]+=p.second;
      else v[i].emplace_back(p);
    }
  }

  for(int j=0;j<RT;j++)
    for(int i=0;i<n;i++)
      acc[j][i+1]+=acc[j][i];

  ll res=1;
  const ll MOD = 1e9+7;
  const int MAX = 5e5+100;
  vector<int> cnt(MAX,0);
  vector<ll> fact(MAX),invs(MAX);

  fact[0]=1;
  for(int i=1;i<MAX;i++)
    fact[i]=(fact[i-1]*i)%MOD;

  invs[1]=1;
  for(int i=2;i<MAX;i++)
    invs[i]=invs[MOD%i]*(MOD-MOD/i)%MOD;

  auto expand=[&](int idx){
                for(auto p:v[idx]){
                  res*=invs[cnt[p.first]+1];
                  res%=MOD;
                  cnt[p.first]+=p.second;
                  res*=cnt[p.first]+1;
                  res%=MOD;
                }
              };
  auto shrink=[&](int idx){
                for(auto p:v[idx]){
                  res*=invs[cnt[p.first]+1];
                  res%=MOD;
                  cnt[p.first]-=p.second;
                  res*=cnt[p.first]+1;
                  res%=MOD;
                }
              };
  Mo mo(n,400,expand,shrink);

  for(int i=0;i<q;i++){
    int l,r;
    cin>>l>>r;
    l--;
    mo.add(l,r);
  }
  mo.build();

  vector<ll> ans(q);
  for(int i=0;i<q;i++){
    int k=mo.process();
    ans[k]=res;
    int l=mo.ls[k],r=mo.rs[k];
    for(int j=0;j<RT;j++){
      ans[k]*=acc[j][r]-acc[j][l]+1;
      ans[k]%=MOD;
    }
  }

  for(int i=0;i<q;i++) cout<<ans[i]<<"\n";
  cout<<flush;
  return 0;
}
/*
  verified on 2019/11/12
  https://atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_b
*/


signed ABC133_F(){
  int n,q;
  cin>>n>>q;
  vector<int> as(n),bs(n),cs(n),ds(n);
  vector<int> xs(q),ys(q),us(q),vs(q);

  EulerTourForEdge et(n);
  for(int i=1;i<n;i++){
    cin>>as[i]>>bs[i]>>cs[i]>>ds[i];
    as[i]--;bs[i]--;
    et.add_edge(as[i],bs[i]);
  }
  et.build();

  vector<int> idx(n,0);
  for(int i=1;i<n;i++)
    idx[et.child(as[i],bs[i])]=i;

  for(int i=0;i<q;i++){
    cin>>xs[i]>>ys[i]>>us[i]>>vs[i];
    us[i]--;vs[i]--;
  }

  int all=0;
  vector<int> cnt(n),sum(n),app(n,0);
  auto exec=
    [&](int k){
      int v=et.bottom(k);
      int e=idx[v];
      app[v]^=1;
      if(app[v]){
        all+=ds[e];
        cnt[cs[e]]++;
        sum[cs[e]]+=ds[e];
      }else{
        all-=ds[e];
        cnt[cs[e]]--;
        sum[cs[e]]-=ds[e];
      }
    };
  Mo mo(n*2,400,exec,exec);

  for(int i=0;i<q;i++){
    auto f=[&](int l,int r){mo.add(min(l,r),max(l,r));};
    et.query(us[i],vs[i],f);
  }
  mo.build();

  vector<int> ans(q,0);
  for(int i=0;i<q;i++){
    int k=mo.process();
    ans[k]=all-sum[xs[k]]+cnt[xs[k]]*ys[k];
  }

  for(int i=0;i<q;i++) cout<<ans[i]<<"\n";
  cout<<flush;
  return 0;
}
/*
  verified on 2019/11/12
  https://atcoder.jp/contests/abc133/tasks/abc133_f
*/

signed main(){
  //DWANGO2017FINAL_B();
  //ABC133_F();
  return 0;
}
#endif

#undef call_from_test

signed main(){
  int n,k,q;
  cin>>n>>k>>q;
  vector<int> as(k),bs(k);
  for(int i=0;i<k;i++) cin>>as[i]>>bs[i],as[i]--,bs[i]--;

  vector<int> ord(n),pos(n);
  iota(ord.begin(),ord.end(),0);
  iota(pos.begin(),pos.end(),0);
  auto moveL=
    [&](int i){
      int x=pos[as[i]],y=pos[bs[i]];
      swap(ord[x],ord[y]);
      swap(pos[ord[x]],pos[ord[y]]);
    };
  auto moveR=
    [&](int i){
      int x=as[i],y=bs[i];
      swap(ord[x],ord[y]);
      swap(pos[ord[x]],pos[ord[y]]);
    };
  Mo mo(q,400,moveL,moveR,moveL,moveR);

  vector<int> qs(q),ls(q),rs(q),xs(q);
  for(int i=0;i<q;i++){
    cin>>qs[i]>>ls[i]>>rs[i]>>xs[i];
    ls[i]--;xs[i]--;
    mo.add(ls[i],rs[i]);
  }
  mo.build();

  vector<int> ans(q,-1);
  for(int i=0;i<q;i++){
    int p=mo.process();
    if(qs[p]==1) ans[p]=ord[xs[p]]+1;
    if(qs[p]==2) ans[p]=pos[xs[p]]+1;
  }

  for(int a:ans) cout<<a<<"\n";
  cout<<flush;
  return 0;
}

