5063：Operation the Sequence

You have an array consisting of n integers: $a_1=1, a_2=2, a_3=3, \ldots, a_n=n$. Then give you m operators, you should process all the operators in order. Each operator is one of four types:
Type1: O 1 call fun1();
Type2: O 2 call fun2();
Type3: O 3 call fun3();
Type4: Q i query current value of a[i], this operator will have at most 50.
Global Variables: a[1…n],b[1…n];
fun1() {
index=1;
  for(i=1; i<=n; i +=2)
    b[index++]=a[i];
  for(i=2; i<=n; i +=2)
    b[index++]=a[i];
  for(i=1; i<=n; ++i)
    a[i]=b[i];
}
fun2() {
  L = 1;R = n;
  while(L<R) {
    Swap(a[L], a[R]);
    ++L;--R;
  }
}
fun3() {
  for(i=1; i<=n; ++i)
    a[i]=a[i]*a[i];
}

The first line in the input file is an integer $T(1 \leq T \leq 20)$, indicating the number of test cases.
The first line of each test case contains two integer $n(0<n \leq 100000)$, $m(0<m \leq 100000)$.
Then m lines follow, each line represent an operator above.

For each test case, output the query values, the values may be so large, you just output the values mod 1000000007(1e9+7).