#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

typedef __int128_t lll;
ll quick_p(lll b, ll p,ll mod){
  lll r = 1;
  while(p){
    if(p%2)(r*=b)%=mod;
    (b*=b)%=mod;
    p/=2;
  }
  return r % mod;
}

bool miller_robin(ll v, ll base, ll startpwr){
  lll r = quick_p(base,startpwr,v);
  for(ll p = startpwr; p < v-1; p *=2){
    if(r == v-1) return true; // -1 开始的序列
    if(r == 1) return p == startpwr; // 全1序列
    (r*=r)%=v;
  }
  return false;
}

bool is_prime_64(ll v){
  if(v == 2)return true;
  if(v < 2 || v % 2 == 0)return false;
  ll p = v-1;
  while(p % 2 == 0) p /= 2;
  for(auto base:{2, 325, 9375, 28178, 450775, 9780504, 1795265022}){
    if(base % v == 0) continue; // don't break may cause 4033 bug
    // 需要所有都能找到-1开始, 或奇数次开始 全1
    if(!miller_robin(v,base,p)) return false;
  }
  return true;
}

ll my_sqrt(ll v){
  if(v <= 1) return v;
  ll l = 1; // 左ok
  ll r = v; // 右not ok
  while(r - l > 1){
    ll m = (l+r)/2;
    (v/m < m ? r : l) = m; // 防止 overflow
  }
  return l;
}
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);

ll randll(ll low,ll hi){
  return low + (rand_num() % static_cast<ll>(hi - low + 1));
}

ll Pollard_Rho(ll N) { // 返回一个> 1的因数
  assert(N > 1);
  if (N == 4) return 2;
  lll ret = my_sqrt(N); // 质数平方 效率低 提前判断
  if(ret * ret == N) return ret;
  while(true) {
    ll c = randll(1, N - 1); // 生成随机的c
    auto f = [=](lll x) { return ((lll)x * x + c) % N; }; // ll 表示__int128，防溢出
    ll t = 0, r = 0; // 初始两个相同
    do{
      t = f(t); // 1倍速度
      r = f(f(r)); // 2倍速度
      ll d = gcd(abs(t - r), N);
      if (d > 1 && d < N) return d;
    }while (t != r);
  }
}

// 分解x为质因数, sorted
vector<ll> fenjie(ll x) {
  vector<ll> res = {};
  deque <ll> arr = {x};
  while(arr.size()){
    ll v = arr.front();
    arr.pop_front();
    if(v == 1) continue;
    if(is_prime_64(v)) {
      res.pb(v);
      continue;
    }
    ll divisor = Pollard_Rho(v);
    arr.push_back(divisor);
    arr.push_back(v/divisor);
  }
  sort(res.begin(),res.end());
  return res;
}

ll Pollard_Rho(ll N) {
  assert(N!=1);
  if (N == 4) return 2;
  if (is_prime(N)) return N;
  if (is_prime_square(N)) return prime_square(N);
  while(true){
    ll c = randint(1, N - 1);
    auto f = [=](ll x) { return ((lll)x * x + c) % N; };
    ll t = 0, r = 0, p = 1, q;
    do {
      for (int i = 0; i < 128; ++i) { // 令固定距离C=128
        t = f(t), r = f(f(r));
        if (t == r || (q = (lll)p * abs(t - r) % N) == 0) break; // 如果发现环，或者积即将为0，退出
        p = q;
      }
      ll d = gcd(p, N);
      if (d > 1) return d;
    } while (t != r);
  }
}

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;} // read
int p[400010];
int q[400010];
char s[400010];
char sets(int i,char ch){
  return (s[i] && s[i] != ch) ? 0 : (s[i] = ch);
}
bool work(){
  int n = read() * 2; // 2e5 * 2
  rep(i,0,n) p[i] = read() - 1;
  rep(i,0,n) q[i] = read() - 1;
  for(auto [arr, cmp]:vector<pair<int *,int> > {{p, 1},{q,-1}}){
    rep(i,0,n-1) {
      if((arr[i] - arr[i+1]) * cmp <= 0) continue; // 出现反序列
      if(!sets(arr[i],'(') || !sets(arr[i+1],')')) return false;
    }
  }
  rep(i,0,n) if(!s[i]) return false; // 不唯一
  // check 可能一个合法 另一个不合法
  for(auto [arr,st,d]:vector<tuple<int*,int,int> >{{p,0,1},{q,n-1,-1}}){
    // 双指针
    int i0 = st; // 找所有值
    int i1 = st; // 只找左括号
    int cnt = 0;
    vector<bool> vis(n,false);
    rep(i,0,n){
      int pos ; // 选取的位置
      if(cnt == 0){
        while(vis[i1] || s[i1] != '(') i1+=d;
        pos = i1;
      }else{ // cnt > 0
        while(vis[i0])i0+=d;
        pos = i0;
      }
      if(arr[i] != pos) return false; // 和提供的不一致
      vis[pos] = true;
      cnt += s[pos] == '('?1:-1;
    }
    if(cnt) return false;
  }
  printf("%s\n",s);
  return true;
}
int main(){
  if(!work()) printf("-1\n");
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
bool exist[600010];
 
vector<int> ys[600010]; // 所有真奇数约数
 
int L[600010];
int R[600010];
int a[600010];
 
int n,m;
bool w(){
  n = read();
  m = read()*2;
  rep(i,0,n) {
    exist[a[i] = read()] = 1;
  }
  rep(i,1,m/2+1){
    if(i%2 == 0)continue;
    rep(t,3,m/2+1){
      if(t%2 == 0)continue;
      if(i*t > m)break;
      ys[i*t].push_back(i);
    }
  }
  // 先检查是否所有组都有
  rep(i,1,m+1){
    if(i%2==0)continue;
    bool found = false;
    int itr = i;
    while(itr <= m){
      if(exist[itr]){
        found = true;
        break;
      }
      itr*=2;
    }
    if(!found)return false;
  }
  // 计算R
  rep(i,1,m){
    if(i%2 == 0) continue;
    int pwr = 20;
    // 计算它因数对它的限制
    for(auto item:ys[i]){
      pwr = min(pwr,R[item]-1);
    }
    // 找一个范围内且存在的
    bool found = false;
    while(pwr >= 0){
      if(i * (1<<pwr) <= m){ // 小心 out bound
        if(exist[i * (1<<pwr)]){
          R[i] = pwr;
          found = true;
          break;
        }
      }
      pwr--;
    }
    // printf("L %lld => %d\n",i,pwr);
    if(!found) return false; // 不存在合法范围的值
  }
  // 计算L
  per(i,1,m){
    if(i%2 == 0) continue;
    int pwr = 0;
    // 计算它倍数对它的限制
    rep(k,3,m+1){
      if(k%2==0)continue;
      if(i*k > m)break;
      pwr = max(pwr,L[i*k]+1);
    }
    // 找一个范围内且存在的
    bool found = false;
    while( i*(1<<pwr) <= m){
      if(exist[i * (1<<pwr)]){
        L[i] = pwr;
        found = true;
        break;
      }
      pwr++;
    }
    if(!found) return false; // 不存在合法范围的值
    if(L[i] > R[i]) return false;
  }
  // 计算答案
  rep(i,0,n){
    int v = a[i];
    int pwr = 0;
    while(v%2 == 0){
      pwr++;
      v/=2;
    }
    printf("%s\n", L[v] <= pwr && pwr <= R[v]?"Yes":"No");
  }
  return true;
}
int main(){
  if(!w()) rep(i,0,n) printf("No\n");
  return 0;
}

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

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read
int gcd(int a,int b){
  while(b!=0){
    a=a%b;
    swap(a,b);
  }
  return a;
}

int fa[200010];
int a[4];
int inner[200010]; // 组内部最小间隔, 一定是n的因子
int tofa[200010]; // 跨组偏移距离
ll n;

int getfa(int i){
  if(i == fa[i]) return i;
  int newfa = getfa(fa[i]);
  tofa[i] = ((tofa[i] + tofa[fa[i]])%n)%inner[newfa];
  return fa[i] = newfa;
}

// new root u
// u and v is old root
void link(int u,int v,int off){
  fa[v] = u;
  inner[u] = gcd(inner[u],inner[v]);
  tofa[v] = off % inner[u];
}

int main(){
  n = read();
  ll q = read();
  ll ans = n*n;
  iota(fa,fa+n,0);
  fill(inner,inner+n,n);
  rep(i,0,q){
    rep(j,0,4) a[j] = read();
    per(j,0,4) (a[j] += n-a[0])%=n;
    int g1 = a[1] - a[0];
    int g2 = (a[3]-a[2]+n)%n;
    int off = a[2] - a[0];
    int f1 = getfa(g1);
    int f2 = getfa(g2);
    // 同组更新内部间隔
    if(f1 == f2){
      // ans -= inner[f1] - inner[f1];
      // printf("SAME %d[%d] => ",f1,inner[f1]);
      ans -= inner[f1];
      inner[f1] = gcd(inner[f1], 2*n + tofa[g1] - tofa[g2] + off); // 不是off
      ans -= -inner[f1];
      // printf("%d \n",inner[f1]);
    }else{ // 不同组 合并组
      // printf("DIFF %d[%d] + %d[%d] => ",f1,inner[f1],f2,inner[f2]);
      // g1->f1, g2->f2
      // f2->f1?
      // f1 - f2 = (f1 - g1) - (f2 - g2) + (g2 - g1)
      // ans -= inner[f1] + inner[f2] - inner[f1];
      ans -= inner[f1] + inner[f2];
      link(f1,f2, (2*n + tofa[g1] - tofa[g2] + off)%n);
      ans -=  - inner[f1];
      // printf("%d \n",inner[f1]);
    }
    printf("%lld\n",ans);
  }

  return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
// n对括号
// reverse substring
 
char s[200010];
int n;
 
int pre[200010];
 
void calc(int st){
  int last = -1;
  per(i,0,n){
    if(pre[i+1] < 0){
      last = i;
      break;
    }
  }
  // printf("[%d %d]\n",st,last);
  int ml = 0;
  int mr = 0;
  rep(i,0,st){
    ml = max(ml,pre[i+1]);
  }
  rep(i,last,n){
    mr = max(mr,pre[i+1]);
  }
  rep(i,st,last+1){
    if(pre[i+1] > ml+mr){
      // rev2
      printf("2\n");
      int maxi = 0;
      rep(i,0,n){
        if(pre[i+1] > pre[maxi]){
          maxi = i+1;
        }
      }
      printf("1 %d\n",maxi);
      printf("%d %d\n",maxi+1,n);
      return ;
    }
  }
  printf("1\n");
  int maxl = 0;
  rep(i,0,st){
    if(pre[i+1] > pre[maxl]) maxl = i+1;
  }
  int maxr = n-1;
  rep(i,last,n){
    if(pre[i+1] > pre[maxr]) maxr = i+1;
  }
  printf("%d %d\n",maxl+1,maxr);
}
 
 
void w(){
  n = read();
  n*=2;
  scanf("%s",s);
  rep(i,0,n) pre[i+1] = pre[i] + (s[i] =='('?1:-1);
  rep(i,0,n){
    if(pre[i+1] < 0){
      calc(i);
      return ;
    }
  }
  printf("0\n");
}
 
 
int main(){
  int t = read();
  while(t--)w();
  return 0;
}

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

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int p[210];
int p2i[210];
int c[210]; // 染色
void w(){
  int n = read();
  fill(c+1,c+n+1,-1);
  rep(i,1,n+1) {
    p[i] = read();
    p2i[p[i]] = i;
  }
  int color = 0;
  rep(i,1,n+1) {
    if(~c[i])continue;
    int itr = i;
    do{
      c[itr] = color;
      itr = p2i[itr];
    }while(itr != i);
    color++;
  }
  // 单个环唯一
  if(color == 1){
    int itr = 1;
    do{
      printf("%d ",itr);
      itr = p2i[itr];
    }while(itr != 1);
    printf("\n");
    return ;
  }
  vector<int>cnt(color,0); // 当前滑窗各种颜色个数
  // 答案 起始位置
  int ansst = 0;
  int anssz = n+1;
  // 滑窗
  int l = 1;
  int r = 0;
  int cur = 0; // 滑窗内颜色种数
  while(cur < color && r+1 < n+1) if(++cnt[c[++r]] == 1) cur ++;
  // [l..r] 包含所有颜色
  while(l <= r){
    if( r-l+1 <= anssz){
      anssz = r-l+1;
      ansst = l;
      // printf("[%d %d]\n",l,r);
    }
    if( -- cnt[c[l++]] == 0 ) cur--;
    while(cur < color && r+1 < n+1){
      ++r;
      cnt[c[r]] ++;
      if(cnt[c[r]] == 1) cur ++;
    }
    if(cur < color)break;
  }
  // [ansst..ansst+anssz-1]
  fill(c+1,c+n+1,-1);
  rep(i,ansst,ansst+anssz - 1 + 1){
    if(~c[i])continue;
    int itr = i;
    do{
      printf("%d ",p2i[itr]);
      c[itr] = 1;
      itr = p2i[itr];
    }while(itr != i);
  }
  printf("\n");
}
int main(){
  int t = read();
  while(t--)w();
  return 0;
}

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

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int p[210];
int p2i[210];
int vis[210]; // 染色
int fa[210];

int getfa(int i){ return i==fa[i]?i:(fa[i] = getfa(fa[i]));}

void link(int u,int v){
  int fu = getfa(u);
  int fv = getfa(v);
  if(fu == fv)return;
  fa[fu] = fv;
}

void w(){
  int n = read();
  fill(vis+1,vis+n+1,false);
  iota(fa,fa+n+1,0);
  rep(i,1,n+1) {
    p[i] = read();
    p2i[p[i]] = i;
  }
  rep(i,1,n+1){
    if(vis[i])continue;
    int itr = i;
    do{
      vis[itr] = true;
      link(itr,i);
      itr = p2i[itr];
    }while(itr != i);
  }
  rep(v,1,n){
    if(getfa(v) == getfa(v+1))continue;
    swap(p[p2i[v]],p[p2i[v+1]]);
    swap(p2i[v],p2i[v+1]);
    link(v,v+1);
  }
  int itr = 1;
  do{
    printf("%d ",itr);
    itr = p2i[itr];
  }while(itr != 1);
  printf("\n");
}
int main(){
  int t = read();
  while(t--)w();
  return 0;
}

#include <bits/stdc++.h>
// jiangly
// https://codeforces.com/contest/1682/submission/158055817
// power 和 norm 和std有冲突
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
// 基于 mod P 的整数, structZ
constexpr int P = 1000000007;
// assume -P <= x < 2P
int mynorm(int x) {
  if (x < 0) {
    x += P;
  }
  if (x >= P) {
    x -= P;
  }
  return x;
}
template<class T>
T mypow(T a, ll b) {
  T res = 1;
  for (; b; b /= 2, a *= a) {
    if (b % 2) {
      res *= a;
    }
  }
  return res;
}
struct Z {
  int x;
  Z(int x = 0) : x(mynorm(x)) {}
  Z(ll x) : x(mynorm(x % P)) {}
  int val() const {
    return x;
  }
  Z operator-() const {
    return Z(mynorm(P - x));
  }
  Z inv() const {
    assert(x != 0);
    return mypow(*this, P - 2);
  }
  Z &operator*=(const Z &rhs) {
    x = ll(x) * rhs.x % P;
    return *this;
  }
  Z &operator+=(const Z &rhs) {
    x = mynorm(x + rhs.x);
    return *this;
  }
  Z &operator-=(const Z &rhs) {
    x = mynorm(x - rhs.x);
    return *this;
  }
  Z &operator/=(const Z &rhs) {
    return *this *= rhs.inv();
  }
  friend Z operator*(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res *= rhs;
    return res;
  }
  friend Z operator+(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res += rhs;
    return res;
  }
  friend Z operator-(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res -= rhs;
    return res;
  }
  friend Z operator/(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res /= rhs;
    return res;
  }
  friend istream &operator>>(istream &is, Z &a) {
    ll v;
    is >> v;
    a = Z(v);
    return is;
  }
  friend ostream &operator<<(ostream &os, const Z &a) {
    return os << a.val();
  }
};
 
// 树状数组 0-index
template <typename T>
struct Fenwick {
  const int n;
  vector<T> a;
  Fenwick(int n) : n(n){
    a.resize(n);
  }
  // [x] += v
  void add(int x, T v) {
    for (int i = x + 1; i <= n; i += i & -i) {
      a[i - 1] += v;
    }
  }
  // [0..x)
  T sum(int x) {
    T ans = 0;
    for (int i = x; i > 0; i -= i & -i) {
      ans += a[i - 1];
    }
    return ans;
  }
  // [l,r)
  T rangeSum(int l, int r) {
    return sum(r) - sum(l);
  }
};
 
int main() {
 
  int n = read(), q = read();
 
  vector<int> a(n);
  vector<ll> b(n + 1);
  rep(i,0,n) a[i] = read();
  // 倒序做差分
  per(i,1,n) a[i] -= a[i - 1];
  rep(i,1,n+1) {
    b[i] = read();
    // 前缀和
    b[i] += b[i - 1];
  }
  // 离线
  vector<array<ll, 4>> qry(q); // 查询 按照 {b[l-1],l-1,r,qidx} 排序
  rep(i,0,q) {
    int l = read()-1, r = read();
    qry[i] = {b[l], l, r, i};
  }
  sort(qry.begin(), qry.end());
 
  // https://en.cppreference.com/w/cpp/algorithm/ranges/iota
  // https://www.cplusplus.com/reference/numeric/iota/
  // 按照bi 前缀和 大小排序下标
  vector<int> p(n);
  iota(p.begin(), p.end(), 0);
  sort(p.begin(), p.end(), [&](int i, int j) { return b[i] < b[j]; });
 
  Fenwick<Z> s(n), c(n);
 
  rep(i,0,n) {
    // 先全部正贡献
    s.add(i, Z(b[i]) * a[i]);
    c.add(i, a[i]);
  }
  vector<Z> ans(q);
 
  int j = 0;
  for (auto [v, l, r, i] : qry) {
    while (j < n && b[p[j]] <= v) { // 根据 bi 前缀大小 决定贡献正负
      int k = p[j++];
      // 树状数组不支持修改, 只支持增量 ,实际是改成负贡献
      s.add(k, -2*Z(b[k]) * a[k]);
      c.add(k, -2*a[k]);
    }
 
    ans[i] = s.rangeSum(l, r) - c.rangeSum(l, r) * v;
  }
 
  for (auto x : ans) {
    printf("%d\n",x.val());
  }
  return 0;
}