akhauriyash/Code-Regression huggingface dataset:
// Marcin Knapik
#include<bits/stdc++.h>
#include<unistd.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
 
typedef long double             ld;
typedef long long               ll;
typedef unsigned long long      ull;
typedef pair<ll, ll>            pll;
typedef pair<int, int>          ii;
typedef vector<int>             vi;
typedef vector<ii>              vii;
typedef vector<vi>              vvi;
typedef vector<vector<ii>>      vvii;
typedef vector< ll >            vll;
typedef vector< pll >           vpll;
 
#define boost                   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(a)                   (int)(a).size()
#define pb                      push_back
#define all(c)                  (c).begin(), (c).end()
#define rall(c)                 (c).rbegin(), (c).rend()
#define REP(i, a, b)            for (int i = (a); i <= (b); i++)
#define FOR(i, a)               for (int i = 0; i < (a); i++)
#define TRAV(i, n)              for(auto&i:n)
#define beg(x)                  (*(x.begin()))
#define re(x)                   int x; cin >>x;   
#define f                       first
#define s                       second
 
template <class T> inline bool setmin(T &a, T b){if (a > b)return a = b, 1;return 0;}
template <class T> inline bool setmax(T &a, T b){if (a < b)return a = b, 1;return 0;}
 
template<class T> inline T fast(T a,T b,T mod) {ll res = 1; while(b){if(b&1) res = (res*a)%mod;a = (a*a)%mod;b >>= 1;}return res;}
template<class T> inline T russian(T a, T b, T mod) {ll res = 0; while(b){if(b&1) res = (res + a)%mod; a = (a+a)%mod; b>>=1;}return res;}
template <class T> istream &operator>>(istream &os, vector<T> &container){for (auto &u : container)os >> u;return os;}
template <class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}
template<typename T> inline T gcd(T a, T b) { while (b)swap(a %= b, b); return a; }
 
const ll T = 1 << 20;
const ll INF = 1e9 + 7;
// const ll mod = 998244353;
const ll BIG_INF = 1e18 + 7;
const ll  N = 1e6+7;
const int LOG = 17;
 
int n, m, q;
string w;
int tab[N];
int odp[N];

signed main(){
	boost;
	cin >> n;
	vii vec;
	FOR(i, n){
		int temp;
		cin >> temp;
		vec.pb({temp,i+1});
	}
	sort(all(vec));
	for(int i = 0; i < n; i++){
		cout << vec[i].s << ' ';
	}
}

Measured memory_bytes: 1780
// B.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
using namespace std;
int main()
{
    int k, x;

    cin >> k >> x;

    for (int i = x - k + 1; i <= x + k - 1; i++) {
        cout << i << endl;
    }
    return 0;
}


Measured memory_bytes: 3636
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

class Solution {
public:
    int solve(vector<int>& A, int S) {
        const int MOD = 998244353;
        int n = A.size();
        const int N = 3010;
        vector<int> dp(N, 0);

        long long res = 0;
        dp[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = N - 1; j >= 0; --j) {
                if (dp[j] == 0) {
                    continue;
                }
                int s = j + A[i];
                if (s == S) {
                    // cout << i << " " << A[i] << " " << dp[j] << endl;
                    res += ((j == 0 ? (i + 1) : dp[j]) * 1LL * (n - i)) % MOD;
                }
                if (s > S) {
                    continue;
                }
                if (j == 0) {
                    dp[s] += i + 1;
                    if (dp[s] >= MOD) {
                        dp[s] -= MOD;
                    }
                } else {
                    dp[s] += dp[j];
                    if (dp[s] >= MOD) {
                        dp[s] -= MOD;
                    }
                }
            }
        }
        res %= MOD;
        return res;

    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    Solution sol;
    int n, s;
    cin >> n >> s;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    cout << sol.solve(A, s) << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3+7;

int a[MAXN][MAXN];
int b[MAXN];
bool vis[MAXN];
queue<int> Q[MAXN];
int main(){
        int n;
        cin>>n;
        for(int i=0;i<n;++i){
                b[i] = 0;
                for(int j=0;j<n-1;++j) {
                        cin>>a[i][j];
                        a[i][j]--;
                        Q[i].push(a[i][j]);
                }
        }
        int ans = 0;
        while(true) {
                bool flag = 0;
                for(int i=0;i<n;++i) {
                        if(Q[i].empty())        continue;
                        if(Q[Q[i].front()].front()==i) {
                                b[i] = b[Q[i].front()] = max(b[i],b[Q[i].front()]) + 1;
                                Q[Q[i].front()].pop();
                                Q[i].pop();
                                flag = 1;
                        }
                }
                if(!flag) {
                        cout<<-1<<endl;
                        return 0;
                }
                int num = 0;
                for(int i=0;i<n;++i)
                        num += Q[i].size();
                if(num==0)      break;
        }
        for(int i=0;i<n;++i)
                ans = max(ans, b[i]);
        cout<<ans<<endl;
        return 0;
}


Measured memory_bytes: 8576
#include<bits/stdc++.h>
using namespace std;

int main(){
    int A,B;
    cin>>A>>B;
    int socket=1;
    int p=0;
    while(1){
        if(socket>=B){
            cout<<p<<endl;
            break;
        }
        else{
          socket+=A;
          socket--;
          p++;
        }
    }
    
}

Measured memory_bytes: 3628
import java.util.Scanner;
public class Main {
	static Scanner scan=new Scanner(System.in);
	static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
	static long lcm (int a, int b) {return a*b/gcd(a,b);}
	static int max(int a,int b) {return a>b?a:b;}
	static int min(int a,int b) {return a<b?a:b;}
	static long factorial(int i) {return i==1?1:i*factorial(i-1);}
	static int lower_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<=key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static int upper_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2)if(n%i==0){return false;}
		return true;
	}
	static int upper_division(int a,int b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lupper_division(long a,long b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lmax(long a,long b) {return Math.max(a, b);}
	static long lmin(long a,long b) {return Math.min(a, b);}
	static int[] setArray(int a) {
		int b[]=new int[a];
		for(int i=0;i<a;i++) {
			b[i]=scan.nextInt();
		}
		return b;
	}
	static String reverce(String str) {
		String strr="";
		for(int i=str.length()-1;i>=0;i--) {
			strr+=str.charAt(i);
		}
		return strr;
	}
	public static void main(String[] args) {
		int a=scan.nextInt();
		if(a>=1000) {
			System.out.println("ABD");
		}
		else {
			System.out.println("ABC");
		}
	}
}


Measured memory_bytes: 23636
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)


int main() {
    while (true) {
        int n, x;
        cin >> n >> x;
        if (n == 0 && x == 0)return 0;
        int cou = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i+1; j <= n; j++) {
                for (int k = j+1; k <= n; k++) {
                    if (i + j + k == x) {
                        cou++;
                    }
                }
            }
        }
        cout << cou << endl;
    }   
}


Measured memory_bytes: 3100
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int  long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()


template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


void solve(void)
{
  int A,B,C;
  cin>>A>>B>>C;
  if(A == B && B == C && A%2 == 0) 
  {
    cout<<-1<<endl;
    return;
  }
  int ANS = 0;
  while(true)
  {
    if(A%2 != 0 || B%2 != 0 || C%2 != 0)
    {
      break;
    }
    ANS++;
    int nA,nB,nC;
    nA = B/2 + C/2;
    nB = A/2 + C/2;
    nC = A/2 + B/2;
    A = nA;
    B = nB;
    C = nC;
  }
  cout<<ANS<<endl;
  return;
}
int32_t main(int32_t argc, const char *argv[])
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

std::cout << std::fixed;
std::cout << std::setprecision(9);
solve();

return 0;
}


Measured memory_bytes: 256
use std::io::BufRead;

fn main() {
    let handle = std::io::stdin();
    let mut s = String::new();
    handle.lock().read_line(&mut s).unwrap();
    let points: Vec<f64> = s.split_whitespace()
        .map(|a| a.parse().unwrap()).collect();
    let (ax, ay, bx, by) = (points[0], points[1], points[2], points[3]);
    println!("{}", ((ax - bx).powi(2) + (ay - by).powi(2)).powf(0.5));
}



Measured memory_bytes: 5064
#include <bits/stdc++.h>
using namespace std;

int n, m, q, l[200002], r[200002], x[502][502], c[502][502];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++){
        cin >> l[i] >> r[i];
        x[l[i]][r[i]]++;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            c[i][j] = c[i][j-1] + x[i][j];
        }
    }
    for(int i = 1; i <= q; i++){
        int p, q;
        cin >> p >> q;
        int ans = 0;
        for(int j = p; j <= q; j++){
            ans += c[j][q] - c[j][p-1];
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4480
#include <bits/stdc++.h>
#define ll long long
#define st first
#define sc second
#define pb push_back

using namespace std;

const int maxn = 1e6 + 69;
const ll mod = 998244353;

int a[maxn][10];
ll dp[maxn];
ll st[4 * maxn];

void update(int id, int l, int r, int pos, ll val)
{
    if(pos < l || pos > r) return ;
    if(l == r){
        st[id] += val;
        st[id] %= mod;
        return ;
    }
    int mid = (l + r)/2;
    update(id * 2, l, mid, pos, val);
    update(id * 2 + 1, mid + 1, r, pos, val);
    st[id] = (st[id * 2] + st[id * 2 + 1]) %mod;

}

ll get(int id, int l, int r, int u, int v)
{
    if(v < l || u > r) return 0;
    if(u <= l && r <= v){
        return st[id];
    }
    int mid = (l + r)/2;
    return (get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v)) %mod;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, t;
    cin >> n >> t;
    vector<pair<int, int>>p;
    for(int i = 1; i <= t; i ++){
         int l, r;
         cin >> l >> r;
         p.pb({l, r});
    }
    sort(p.begin(), p.end());
    update(1, 1, n, 1, 1);
    for(int i = 2; i <= n; i ++){
        for(int k = 0; k < t; k ++){
            int l = p[k].st;
            int r = p[k].sc;
            if(i < l) break;
            if(r < i){
                if(i - l < 1) continue;
                int lf = max(i - l, 1);
                int rg = max(i - r, 1);
                ll cur = get(1, 1, n, rg, lf);
                update(1, 1, n, i, cur);
            }
            else if(l <= i && i <= r){
                if(i - l < 1) continue;
                int lf = max(i - l, 1);
                ll cur = get(1, 1, n, 1, lf);
                update(1, 1, n, i, cur);
            }

        }
    }
    cout << get(1, 1, n, n, n);

}


Measured memory_bytes: 7628
from heapq import heappush,heappop
import itertools
n,m,r=map(int,input().split())
l1=list(map(int,input().split()))
inf=10**10
l=[[] for i in range(n+1)]
for i in range(m):
  a,b,c=map(int,input().split())
  l[a].append([b,c])
  l[b].append([a,c])
def dijkstra(s):
  q=[(0,s)]
  dist=[inf]*(n+1)
  dist[s]=0
  while q:
    c,v=heappop(q)
    if dist[v]<c:
      continue
    for i in l[v]:
      t=i[0]
      cost=i[1]
      if dist[v]+cost<dist[t]:
        dist[t]=dist[v]+cost
        heappush(q,[dist[t],t])
  return dist
dic={}
for i in range(r):
  d=dijkstra(l1[i])
  dic[l1[i]]=d
p=itertools.permutations(l1,r)
ans=inf
for i in p:
  p1=i
  ans1=0
  for j in range(r-1):
    num1=p1[j]
    num2=p1[j+1]
    ans1+=dic[num1][num2]
  if ans>ans1:
    ans=ans1
print(ans)

Measured memory_bytes: 8032
fun main(args: Array<String>){
    val num = readLine()!!.toInt()
    val input = readLine()!!.split(" ").map(String::toInt)
    var result = 0

    populate(result, input)
}

fun populate(result: Int, input: List<Int>){
    val next = mutableListOf<Int>()
    input.forEach {
        if (it % 2 != 0){
            print(result)
            return
        }
        next.add(it/2)
    }
    populate(result + 1, next)
}

Measured memory_bytes: 37828
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int M = 1e5 + 10;
const ll MOD = 1e9 + 7;

int a[210];
int n, x;

ll dp[M];

void add(ll &a, ll b) {
	a = (a + b) % MOD;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> x;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	sort(a, a + n);
	dp[x] = 1;
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j <= x; ++j) {
			ll x = dp[j];
			dp[j] = 0;
			add(dp[j % a[i]], x);
			add(dp[j], x * i);
		}
	}
	ll ans = 0;
	for (int i = 0; i <= x; ++i) {
		ans = (ans + dp[i] * i) % MOD;
	}
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 1024
/*
Sharif Hasan - CSE, PUST
Apr 24, 2020 02: 14 PM
*/
#include<bits/stdc++.h>
#include "string.h"
#define br cout<<"\n"
#define what(x) cout<<"in here var= "<<x<<"\n";

/*STL definations*/
#define pb push_back

#define FOR(i,n) for(int i=0;i<n;i++)
#define FROM(a,i,n) for(int i=a;i<n;i++)
using namespace std;
double clockAngle(double a,double b){
    double f=fabs(b*6-(a*30+b/2));
    if(f>180) f=360-f;
    return  f*acos(-1)/180.0;
}
int main(){
    long long a,b;string s;
        cin >> a >> s;
        b=(s[0]-'0')*100+(s[2]-'0')*10+s[3]-'0';
        cout<<long((a*b)/100)<<endl;
    return 0;
}

Measured memory_bytes: 3588
#include <iostream>
#include <vector>
#include <unordered_map>
#include <deque>
#include <list>
#include <set>
#include <random>
#include <deque>
#include <unordered_set>

using namespace std;
using ll = long long;
const int BIG = 100000007;


int main() {
    string s,t;
    cin >> s >> t;
    ll mi = t.size();
    for(ll i = 0;i < s.size() - t.size() + 1;++i){
        ll k = 0;
        for(ll j = 0;j < t.size();++j){
            if(s[i + j] != t[j])++k;
        }
        if(mi > k)mi = k;
    }
    cout << mi << endl;
}




Measured memory_bytes: 3196
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
using namespace std;

int main() {

	long long N, M;
	cin >> N >> M;

	if (N == 1 && M == 1) {
		cout << 1 << endl;
	}
	else if (N == 1 || M == 1) {
		cout << max(N, M) - 2 << endl;
	}
	else {
		cout << N * M - 2 * N - 2 * M + 4 << endl;
	}

	return 0;
}

Measured memory_bytes: 3572
#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;cin>>str;
    int n=str.size();
    int m=n/2,ans=0;

    for(int i=0;i<m;++i){
        if(str[i] != str[n-1-i])ans+=1;
    }
    
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int n;
   cin >> n;
   string s;
   cin >> s;
   int ans = 1;
   f(i,1,n){
      if(s[i]!=s[i-1]){
         ans++;
      }
   }
   cout << ans << '\n';
   return 0;
} 

Measured memory_bytes: 512
from collections import Counter
 
n = int(input())
d = list(map(int, input().split()))
mod = 998244353
 
c = Counter(d)
 
if d[0] != 0 or c[0] != 1:
    print(0)
    exit()
 
ans = 1
for i in range(1, max(d)+1):
    if i not in c:
        print(0)
        exit()
    ans *= pow(c[i-1], c[i], mod)
 
print(ans % mod)

Measured memory_bytes: 19936
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e5;
const int size=1e5;
const int inf=1e9;
int main(){
	string s;cin>>s;
	int cnt=0;
	rep(i,0,s.size()){
		if(s[i]!=s[s.size()-1-i]) cnt++;
	}cout<<cnt/2<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args){
    	int cards[][] = new int[4][13];
        int n;
        
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		
		for(int i = 0;i < n;i++){
			String kind = scanner.next();
			int num     = scanner.nextInt();
			
			if(kind.equals("S")){
				cards[0][num-1] = num;
			}
			else if(kind.equals("H")){
				cards[1][num-1] = num;
			}
			else if(kind.equals("C")){
				cards[2][num-1] = num;
			}
			else{
				cards[3][num-1] = num;
			}
		} 
		
		for(int i = 0;i < 4;i++){
			for(int j = 0;j < 13;j++){
				if(cards[i][j] == 0){
					if(i == 0){
						System.out.println("S "+(j+1));
					}
					else if(i == 1){
						System.out.println("H "+(j+1));
					}
					else if(i == 2){
						System.out.println("C "+(j+1));
					}
					else{
						System.out.println("D "+(j+1));
					}
					
				}
			}	
		}
    	scanner.close();
    }
}

Measured memory_bytes: 26004
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>

using namespace std;
typedef long long LL;
static const double EPS = 1e-9;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n) 

const static int dx[13] = {0,1,0,-1,0,1,-1,-1,1,2,0,-2,0};
const static int dy[13] = {0,0,1,0,-1,1,1,-1,-1,0,2,0,-2};
int main(void){  
  int date[14][14]={0};
  int x,y,s,c=0,m=0;
  
  while(scanf("%d,%d,%d",&x,&y,&s) != EOF)
    REP(i,4*s+1) date[x+2+dx[i]][y+2+dy[i]] += 1;

  FOR(i,2,12)
    FOR(j,2,12){
      if(date[i][j]==0) c++;
      m = max(date[i][j], m);
    }
  cout << c << endl;
  cout << m << endl;
}

Measured memory_bytes: 0
//Utkarsh-raj

#include<bits/stdc++.h>

#define ll long long int
#define vc vector
#define mod 100000000007
#define mp make_pair
#define pb push_back
#define nl cout<<endl;
#define ff first
#define ss second

using namespace std;

typedef vector<pair<ll, ll> > vpp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ifstream myFile("task.in");
    if(!myFile.fail())
    {
        assert(freopen("task.in", "r", stdin));
    }

    int n;
    cin>>n;

    ll arr[n];
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }

    vector<vpp> dp(n, vpp(n, {0, 0}));

    for(int i=0; i<n; i++){
        dp[i][i] = {0, arr[i]};
    }

    for(int i=0; i<n-1; i++){
        dp[i][i+1] = {arr[i] + arr[i+1], arr[i] + arr[i+1]};
    }

    for(int len = 3; len <= n; len++){
        for(int i=0; i <= n - len; i++){
            int j = i + len - 1;
            // cout<<i<<" "<<j<<endl;
            dp[i][j] = {LONG_MAX, LONG_MAX};
            for(int k = i; k < j; k++){
                ll x = dp[i][k].first + dp[k+1][j].first + dp[i][k].second + dp[k+1][j].second;
                ll y = dp[i][k].second + dp[k+1][j].second;
                dp[i][j] = min(dp[i][j], {x, y});
            }
        }
    }

    // for(int i=0; i<n; i++){
    //     for(int j=0; j<n; j++){
    //         cout<<"("<<dp[i][j].first<<" "<<dp[i][j].second<<") ";
    //     }
    //     cout<<endl;
    // }

    cout<<dp[0][n-1].first<<endl;

    return 0;
}


Measured memory_bytes: 5836
// ARC085D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2020;

int n, X, Y, ai[MAX_N], dp[MAX_N][2];

int main()
{
    scanf("%d%d%d", &n, &X, &Y);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    if (n == 1)
        printf("%d\n", abs(ai[1] - Y));
    else
        printf("%d\n", max(abs(ai[n - 1] - ai[n]), abs(ai[n] - Y)));
    return 0;
}

Measured memory_bytes: 3856
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const int INF = 1000000000;
#define SF 61


int visit[130][130],ans;
int dx[]={1,1,0,-1,-1,0},dy[]={1,0,-1,-1,0,1};

int t,n;

void func(int x,int y,int rem){
	if (visit[y][x] >= rem) {
		return;
	}
	if (visit[y][x] == -1) ans++;
	visit[y][x] = rem;
	
	if (rem == 0) return;
	int nx,ny;
	for(int i=0;i<6;i++){
		nx=dx[i]+x;
		ny=dy[i]+y;
		func(nx,ny,rem-1);
	}
	
}

int main(){
	while(cin>>t>>n,n||t){
		ans=0;
		int x,y,sx,sy;
		for(int i=0;i<130;i++)
		for(int j=0;j<130;j++){
			visit[i][j]=-1;
		}
		for(int i=0;i<n;i++){
			cin>>x>>y;
			visit[y+SF][x+SF]=10000;
		}
		cin>>sx>>sy;
		
		func(sx+SF,sy+SF,t);
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 940
#include<iostream>
#include<vector>
using namespace std;


long long calc_gcd(long long a, long long b){
  long long x = max(a, b), y = min(a, b);
  if(y == 0){
    return x;
  }else{
    return calc_gcd(b, a % b);
  }
}

int main(){
  long long A, B;
  cin >> A >> B;

  long long gcd = calc_gcd(A, B);
  // cout << "gcd: " << gcd << endl;

  int ans = 1; // for 1
  for(long long i = 2; i * i <= gcd; i++){
    if(gcd % i == 0){
      ans++;
    }
    while(gcd % i == 0){
      gcd /= i;
    }
  }
  if(gcd != 1){
    ans++;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
namespace C1
{
    class MainClass
    {

        public static List<string[]> getinputdata (){

            List<string[]> list_temp = new List<string[]>();
            string strdata = Console.ReadLine ();

            while (strdata!=null) {

                string[] s_temp = strdata.Split (' ');

                list_temp.Add (s_temp);

                strdata = Console.ReadLine ();

            }

            return list_temp;
        }



        public static void Main (string[] args)
        {
            List<string[]> arr_result = new List<string[]>();
            arr_result = getinputdata ();

            Console.WriteLine (Math.Pow(double.Parse(arr_result[0][0]),3));


        }
    }
}

Measured memory_bytes: 9672
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
#define erep1(i,n) for(int i = 1;i<=n;i++)
typedef long long ll;
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>:
#define vbool vector<bool>
#define INF 100000000000000009
#define MOD 1000000007
#define int long long
using P = pair<int,int>;
signed main(){
  int n,c;
  cin >> n >> c;
  vvint D(c,vint(c));
  rep(i,c) rep(j,c) cin >> D[i][j];
  vvint C(n,vint(n));
  rep(i,n) rep(j,n){
    cin >> C[i][j];
    C[i][j]--;
  }
  vint one(c);
  vint two(c);
  vint three(c);
  rep(i,n) rep(j,n){
    if((i + j + 2) % 3 == 1){
      one[C[i][j]]++;
    }
    if((i + j + 2) % 3 == 2){
      two[C[i][j]]++;
    }
    if((i + j + 2) % 3 == 0){
      three[C[i][j]]++;
    }
  }
  int ans = INF;
  rep(i,c) rep(j,c) rep(s,c){
    if(i != j && i != s && j != s){
      int temp = 0;
      rep(t,c){
        temp += one[t] * D[t][i];
        temp += two[t] * D[t][j];
        temp += three[t] * D[t][s];
      }
      ans = min(ans,temp);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    int h1,m1,h2,m2,k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int zikan;
    zikan = 60*(h2-h1) + (m2-m1);
    if(zikan - k > 0) cout << zikan -k << endl;
    else cout << 0 <<endl;

    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  string s; cin >> s;
  for(int i=0;i<SZ(s);++i) {
    cout << 'x';
  }
  cout << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,A[N];
struct ed{int nxt,to;}G[N<<1];int lnk[N],pp;
void ae(int k1,int k2){G[++pp]=(ed){lnk[k1],k2},lnk[k1]=pp;}
int dfs(int k1,int k2){
	for(int i=lnk[k1];i;i=G[i].nxt){
		int j=G[i].to;if(j==k2)continue;
		if(A[k1]>A[j]&&!dfs(j,k1))return 1;
	}
	return 0;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i)scanf("%d",&A[i]); 
	for(int i=2;i<=n;++i){int k1,k2;scanf("%d%d",&k1,&k2),ae(k1,k2),ae(k2,k1);}
	for(int i=1;i<=n;++i)if(dfs(i,0))printf("%d ",i);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> L(N);
  for (int i = 0; i < N; i++) cin >> L[i];
  int ans = 1;
  int D = 0;
  for (int i = 0; i < N; i++) {
    D += L[i];
    if (D <= X) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <list>
#include <vector>

using namespace std;
typedef long long LL;

#define MIN(x, y) x<y?x:y

int main()
{
	LL x, y;
	LL year=0;

	cin>>x;
	y=100;

	while(y<x) {
		year++;
		y=y*1.01;
	}

	cout<<year<<endl;

	return 0;
}


Measured memory_bytes: 3636
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

N = int(input())
G = [[] for _ in range(N+1)]

for _ in range(N-1):
  v, u, w = map(int, input().split())
  G[v].append((u, w))
  G[u].append((v, w))

deq = deque()
deq.append(1)
res = [-1]*(N+1)
res[1] = 0

while deq:
  x = deq.popleft()
  for e, w in G[x]:
    if res[e] == -1:
      res[e] = (res[x]+w)%2
      deq.append(e)
[print(r) for r in res[1:]]

Measured memory_bytes: 40700
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cmath>
#include <cstdlib>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
#define ALL(x) x.begin(), x.end()
#define INF (1001000000)
#define SZ(a) int((a).size())
#define EACH(i,c) for(auto i:c)
#define EXIST(cs,v) (find(ALL(cs),(v))!=cs.end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define UNIQ(c) (c).erase(unique((c).begin(),(c).end()), (c).end());
#define P(p) cout<<(p)<<endl;

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b, c;
    cin >> a >> b >> c;

    P((a * b) / 2);

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

int dp[5001][5001];

int get(const vector<int> &xs, const vector<int> &ys, int x, int y) {
    if (*xs.begin() > x || *ys.begin() > y) return 0;
    int px = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    int py = lower_bound(ys.begin(), ys.end(), y) - ys.begin();
    if (lower_bound(xs.begin(), xs.end(), x) == xs.end()
        || *lower_bound(xs.begin(), xs.end(), x) != x) px--;
    if (lower_bound(ys.begin(), ys.end(), y) == ys.end()
        || *lower_bound(ys.begin(), ys.end(), y) != y) py--;
    //cout<<x<<" "<<y<<" "<<px<<" "<<py<<endl;
    return dp[py][px];
}

int main() {
    int n,m;
    cin>>n>>m;
    set<int> xs, ys;
    vector<int> inx(n), iny(n);
    for (int i=0; i<n; ++i) {
        cin>>inx[i]>>iny[i];
        xs.insert(inx[i]);
        ys.insert(iny[i]);
    }
    map<int,int> xmap, ymap;
    int cnt = 0;
    vector<int> vx, vy;
    for (set<int>::iterator x = xs.begin(); x != xs.end(); ++x) {
        xmap[*x] = cnt++;
        vx.push_back(*x);
    }
    cnt = 0;
    for (set<int>::iterator y = ys.begin(); y != ys.end(); ++y) {
        ymap[*y] = cnt++;
        vy.push_back(*y);
    }
    for (int i=0; i<n; ++i)
        dp[ymap[iny[i]]][xmap[inx[i]]] += 1;

    const int ny = ys.size();
    const int nx = xs.size();
    for (int i=0; i<ny; ++i)
        for (int j=0; j<nx; ++j) {
            int r = i?dp[i-1][j]:0;
            r += j?dp[i][j-1]:0;
            r -= (i>0&&j>0)?dp[i-1][j-1]:0;
            dp[i][j] += r;
        }

    for (int i=0; i<m; ++i) {
        int x1,y1,x2,y2;
        cin>>x2>>y2>>x1>>y1; x2--, y2--;
        int ans = get(vx,vy,x1,y1) - get(vx,vy,x2,y1) - get(vx,vy,x1,y2) + get(vx,vy,x2,y2);
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 99916
use std::io;
use std::cmp;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::f64::consts::PI;

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}


fn main() {
    let line: Vec<usize> = read_line().split_whitespace().map(|s| s.parse().unwrap()).collect();

    let n = line[0];
    let m = line[1];

    let s: Vec<char> = read_line().trim().chars().collect();

    let mut ans = Vec::new();
    let mut pos = s.len() - 1;
    while pos > 0 {
        let mut step = cmp::min(pos, m);
        while step > 0 && s[pos - step] == '1' {
            step -= 1;
        }
        if step == 0 {
            break;
        }

        ans.push(step);
        pos -= step;
    }
    if pos != 0 {
        println!("-1");
    } else {
        ans.reverse();
        println!("{}", ans.iter().map(|i| i.to_string()).collect::<Vec<String>>().connect(" "));
    }
}


Measured memory_bytes: 10620
#include <iostream>
#include <cmath>

using namespace std;

int X;
int res = 1;
int main()
{
  cin >> X;
  if (X == 1)
  {
    cout << 1 << endl;
    return 0;
  }
  for (int i = 2; i <= sqrt(X); i++)
  {
    int j = 2;
    while (true)
    {
      int temp = 1;
      for (int h = 0; h < j; h++)
      {
        temp *= i;
      }
      if (temp > X)
      {
        break;
      }
      res = max(res, temp);
      j++;
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lowbit(i) ((i)&(-i))
#define ls (p << 1)
#define rs (p << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MAXN = 26 + 15;
int main() {
#ifdef CitricAcid
    freopen ("input.txt", "rt", stdin);
#endif

    ll n;
    scanf("%lld", &n);
    string ans;

    while(n > 0) {
        n--;
        ans += (n % 26) + 'a';
        n /= 26;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;


#ifdef CitricAcid
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}
/*
# author : CitricAcid
# date : 2020/07/27
*/

Measured memory_bytes: 3716
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

int main() {
    int N, W; cin >> N >> W;
    vector<int> v(N), w(N);
    REP(i, N) {
        cin >> v[i] >> w[i];
    }
    // dp[i][j] : i番目までで重さjを作るときの価値の最大
    vector<ll> dp(W + 1, 0);
    REP(i, N) {
        REP(j, W + 1) {
            if (j - w[i] >= 0) {
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
    }
    cout << dp[W] << endl;
    return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll s, w; cin >> s >> w;
    if(s <= w) cout << "unsafe" << endl;
    else cout << "safe" << endl;
}


Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef vector<ll> vi;
#define MOD 998244353

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, S;
	cin >> N >> S;
	vi A(N+1);
	for(int i = 1; i <= N; ++i) cin >> A[i];
	vector<vi> d(N+1, vi(S+1));
	for(int i = 0; i <= S; ++i) d[0][i] = 0;
	d[0][0] = 1;
	for(int i = 1; i <= N; ++i) {
		for(int s = 0; s <= S; ++s) {
			d[i][s] = (2*d[i-1][s]) % MOD;
			if(s-A[i] >= 0) d[i][s] = (d[i][s] + d[i-1][s-A[i]]) % MOD;
		}
	}
	cout << d[N][S] << endl;

	return 0;
}

Measured memory_bytes: 73676
#include<iostream>
using namespace std ;
#include<string>
int main()
{
	int n,a=0,w=0,t=0,r=0;
	cin>>n;
	string c;
for(int i=0;i<n;i++)
{
	cin>>c;
	if(c[0]=='A')
		a++;
	else if (c[0]=='W')
		w++;
	else if (c[0]=='T')
		t++;
	else
		r++;
}
cout<<"AC x "<<a<<endl;
cout<<"WA x "<<w<<endl;
cout<<"TLE x "<<t<<endl;
cout<<"RE x "<<r<<endl;
}


Measured memory_bytes: 3140
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
  
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define uint unsigned int
#define ull  unsigned long long
#define pb push_back
#define mk make_pair
#define ins insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define X first
#define Y second
#define umap unordered_map
#define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
#define mset multiset
#define pqueue priority_queue
   
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
        
const int  N = 2e5 + 314;
const int INF = 1e9;
const double PI = acos(-1);
const int MOD = 1e9 + 7;
const double eps = 1e-9;
 
void solve(){
    string a, b, c;
    cin >> a >> b >> c;
    if(a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0]) {
        cout << "YES";
    }
    else {
        cout << "NO";
    }
}
 
int main(){
    speed();
    int t = 1;
    // cin >> t;
    while(t--)solve();
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)n; i++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007//1e9+7
typedef long long ll;
using namespace std;
int main()
{
  vector<vector<int > >  c(3,vector<int>(3,0));
  REP(i,3){
  REP(j,3){
    cin >> c[i][j];
  }
  }
  REP(i,3){
    for(int j = i + 1;j < 3;j++){
      bool flag = false;
      if(c[0][i] - c[0][j] == c[1][i] - c[1][j]){
	if(c[1][i] - c[1][j] == c[2][i] - c[2][j]){
	  if(c[2][i] - c[2][j] == c[0][i] - c[0][j]){
	    flag = true; 
	  }
	}
      }
      if(!flag){
	cout << "No" << endl;
	return 0;
      }
      flag = false;
      if(c[i][0] - c[j][0] == c[i][1] - c[j][1]){
	if(c[i][1] - c[j][1] == c[i][2] - c[j][2]){
	  if(c[i][2] - c[j][2] == c[i][0] - c[j][0]){
	    flag = true; 
	  }
	}
      }
      if(!flag){
	cout << "No" << endl;
	return 0;
      }
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 256
k, n = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
# Ignore the longest yard.


def gen(a):
    for i, d in enumerate(a):
        if i < n - 1:
            yield a[i + 1] - d
        elif i == n - 1:
            yield k + a[0] - d


max_d = max(gen(a))
print(k - max_d)


Measured memory_bytes: 26444
#include<bits/stdc++.h>
using namespace std;
# define ll long long int
# define M 1000000007
ll n;
ll dp[30][1<<22];
ll solve(vector<vector<ll>>&v,ll i,ll mask,ll jod)
{
  if(i>n)
  {
    if(mask==jod)
    {
      return 1;
    }
    else{
      return 0;
    }
  }

  if(dp[i][mask]!=-1)
  {
    return dp[i][mask];
//    cout<<"Here"<<endl;
  }
  //cout<<"mask "<<mask<<endl;
  ll final=0;
  //cout<<"final "<<final<<endl;
  for(ll j=0;j<v[i].size();j++)
  {
    ll r= v[i][j];
    if(((1<<r)&mask)==0)
    {
      final=(final + solve(v,i+1,(mask|(1<<r)),jod))%M;
      dp[i][mask]=final;
    }

  }

  return dp[i][mask]=final;
}

int main()
{

  cin>>n;
  //int mat[n][n];
  memset(dp,-1,sizeof(dp));
  vector<vector<ll>>v(n+1);
  for(ll i=0;i<n;i++)
  {
    for(ll j=0;j<n;j++)
    {
      ll a;
      cin>>a;
      if(a==1)
      { //cout<<"deal "<<endl;
        v[i+1].push_back(j+1);
        //cout<<" element inserted "<<j+1<<endl;
      }
    }
  }

  // for(int i=1;i<=n;i++)
  // {
  //   cout<<i<<" : ";
  //   for(int j=0;j<v[i].size();j++)
  //   {
  //     cout<<v[i][j]<<" ";
  //   }
  //   cout<<endl;
  // }
//
// cout<<" output "<<endl;
//   cout<<v[1][0]<<endl;
//   cout<<v[1][1]<<endl;
//   cout<<v[1][2]<<endl;
//   cout<<v[1][3]<<endl;
// ll total=2*(pow(2,22)-1);
// cout<<"Total "<<total<<endl;
  ll jod=2*(pow(2,n)-1);
  // cout<<"jod "<<jod<<endl;
  cout<<solve(v,1,0,jod)<<endl;
}


Measured memory_bytes: 987008
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <iomanip>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
// #include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb push_back
#define res(v) v.resize(unique(v.begin(), v.end()) - v.begin());
#define cnt_res(v) std::distance(v.begin(),std::unique(v.begin(), v.end())); 
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
using namespace std;
const int N=2e3+10;
const int inf = /*0x3f3f3f3f*/1e18+10;
// const ll M = 998244353 ; // Mulo
// const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
int a[N],dp[N][N];string s;
void solve(){
  int n;cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  cin>>s;s='#'+s;
  int x=0;
  vector<int>V;
  memset(dp,0,sizeof dp);
  for(int i=n;i>=1;i--){
    int num=a[i];
    for(auto z:V)num=min(num,num^z);
    if(num!=0){
      if(s[i]=='1'){cout<<1;return;}
      V.pb(num);
    }
  }
  cout<<0;
}
int32_t main()
{
  ibs;cti;
  cout<<fixed<<setprecision(20);
  // solve()
  /*,cout<<"\n"*/;
  // cout<<"\n";
  int xx=0;
  int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<":\n"*/;solve();cout<<"\n";}
  return 0;
}

Measured memory_bytes: 35212
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD 1000000007

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

signed main() {
	int H, W;
	cin >> H >> W;

	vector<string> board(H);
	rep(i, H) cin >> board[i];

	int x = 0, y = 0;
	bool ok = true;
	while (x != W - 1 || y != H - 1) {
		board[y][x] = '.';
		if (x < W - 1 && board[y][x + 1] == '#') x++;
		else if (y < H - 1 && board[y + 1][x] == '#') y++;
		else {
			ok = false;
			break;
		}
	}
	board[y][x] = '.';

	rep(y, H) rep(x, W) {
		if (board[y][x] == '#') ok = false;
	}

	cout << (ok ? "Possible" : "Impossible") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;

bool isPrime(int x) {
  if (x < 2) return false;
  if (x == 2) return true;
  if (x % 2 == 0) return false;
  double s = sqrt(x);
  for (int i = 3; i <= s; i+=2) {
    if (x % i == 0) return false;
  }
  return true;
}

int main() {
  int n, e;
  int count = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> e;
    if (isPrime(e)) count++;
  }
  cout << count << endl;

  return 0;
}

Measured memory_bytes: 1160
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;

int main() {
  ll N, K;
  cin >> N >> K;
  vec<ll> A(N);
  REP(i, N) cin >> A[i];

  const ll res = 1 + static_cast<ll>(
                         ceil(static_cast<ld>(N - K) / static_cast<ld>(K - 1)));
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3940
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int long long
using P = pair<int, int>;

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
int in() {int x; cin>>x; return x;}
string stin() {string s; cin>>s; return s;}
/***** MAIN *****/
signed main() {
  int n = in();
  set<string> ss;
  REP(i,n) {
    string s = stin();
    ss.insert(s);
  }
  cout << ss.size();
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 19176
#include <bits/stdc++.h>

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod =(1e9)+7;
using P = pair<ll,ll>;

int main(){
    ll n;cin >>n;
    ll a,b;cin >>a>>b;
    ll mint=a*(n-1)+b;
    ll mx=b*(n-1)+a;
    ll ans=mx-mint+1;
    if(ans<0)ans=0;
    cout <<ans <<endl;
    return 0;
}



Measured memory_bytes: 256
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define all(x) begin(x),end(x)
#define pii pair<int,int>
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vi vector<int>
#define ld long double
#define ll long long
#define pb push_back
#define mid (l+r)/2
#define S second
#define F first
using namespace std;
const ll inf = 1e18;
const int mod = 1e9+7;
ll n,k;
int main(){
    fast,cin>>n>>k;
    ll x = n / k;
    n -= x*k;
    cout<<min(n,k-n)<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int main(){
  int h,w,k;cin>>h>>w>>k;
  string a[h];
  for(int i=0;i<h;i++)cin>>a[i];
  vector<pii> v;
  int sh,sw;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a[i][j]=='S'){
        sh=i;
        sw=j;
      }
    }
  }
  queue<pii> q;
  queue<int> d;
  q.push(make_pair(sh,sw));
  d.push(0);
  bool used[h][w];
  for(int i=0;i<h;i++)fill(used[i],used[i]+w,false);
  used[sh][sw]=true;
  int dh[4]={1,-1,0,0};
  int dw[4]={0,0,1,-1};
  while(q.size()>0){
    pii p=q.front();q.pop();
    v.push_back(make_pair(p.first,p.second));
    int dis=d.front();d.pop();
    if(dis==k)continue;
    for(int i=0;i<4;i++){
      int nh=p.first+dh[i];
      int nw=p.second+dw[i];
      if(nh<0||nh>=h||nw<0||nw>=w)continue;
      if(a[nh][nw]=='#')continue;
      if(used[nh][nw])continue;
      used[nh][nw]=true;
      q.push(make_pair(nh,nw));
      d.push(dis+1);
    }
  }
  int mi=1000000000;
  for(int i=0;i<v.size();i++){
    int e=v[i].first,r=v[i].second;
    mi=min(e-0,mi);
    mi=min(h-1-e,mi);
    mi=min(r-0,mi);
    mi=min(w-1-r,mi);
  }
  int ans=1;
  ans+=ceil((double)mi/(double)k);
  cout<<ans<<endl;
}
           
                           

Measured memory_bytes: 11892