akhauriyash/Code-Regression huggingface dataset:
//#define debug

#include <bits/stdc++.h>

using namespace std;

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

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

int n, m, np, residue;
char a[13][13];
bool used[13], mark[13];
ii all_pairs[13];
vector<pll> d;

pll calc_hash(int col) {
	ll hs = 0, hp = 0;
	for (int j = 1; j <= np; ++j) {
		hp = hp * 27ll + (ll)(a[all_pairs[j].first][col] - 'a' + 1);
		hs = hs * 27ll + (ll)(a[all_pairs[j].second][col] - 'a' + 1);
	}
	if (residue) {
		hp = hp * 27ll + (ll)(a[residue][col] - 'a' + 1);
		hs = hs * 27ll + (ll)(a[residue][col] - 'a' + 1);
	}
	for (int j = np; j >= 1; --j) {
		hp = hp * 27ll + (ll)(a[all_pairs[j].second][col] - 'a' + 1);
		hs = hs * 27ll + (ll)(a[all_pairs[j].first][col] - 'a' + 1);
	}
	return pll(hp, hs);
}

bool check2() {
	int cnt = m & 1;
	for (int i = 1; i <= m; ++i) {
		if (mark[i]) continue;
		for (int j = 1; j <= m; ++j) {
			if (mark[j] || j == i) continue;
			if (d[i - 1].first == d[j - 1].second) {
				mark[i] = mark[j] = true, cnt += 2;
				break;
			}
		}
	}
	return cnt == m;
}

void check() {
	d.clear();
	for (int i = 1; i <= m; ++i) {
		auto tmp = calc_hash(i);
		d.push_back(tmp);
	}
	if (m & 1) {
		for (int i = 1; i <= m; ++i) {
			if (d[i - 1].first != d[i - 1].second) continue;
			fill(mark + 1, mark + m + 1, false);
			mark[i] = true;
			if (check2()) {
				puts("YES");
				exit(0);
			}
		}
	} else if (check2()) {
		puts("YES");
		exit(0);
	}
}

void brute(int cnt) {
	int p1 = -1;
	for (int i = all_pairs[cnt - 1].first + 1; i <= n; ++i) {
		if (!used[i]) {
			used[(p1 = i)] = true;
			break;
		}
	}
	if (p1 == -1) {
		check();
		return;
	}
	all_pairs[cnt].first = p1;
	for (int i = p1 + 1; i <= n; ++i) {
		if (used[i]) continue;
		all_pairs[cnt].second = i;
		used[i] = true;
		brute(cnt + 1);
		used[i] = false;
	}
	used[p1] = false;
}

int main() {
#ifdef debug
	clock_t tStart = clock();
#endif
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", a[i] + 1);
	}
	np = n / 2;
	if (n & 1) {
		for (int residue = 1; residue <= n; ++residue) {
			used[residue] = true;
			brute(1);
			used[residue] = false;
		}
	} else {
		brute(1);
	}
	puts("NO");
#ifdef debug
	printf("Total time: %d ms\n", (int)(1000.0 * (double)(clock() - tStart) / CLOCKS_PER_SEC));
#endif
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<class T>using numr=std::numeric_limits<T>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const ll LLINF = 1e16;
const int MOD = 1000000007;
const int MOD2 = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    if(s == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
}

Measured memory_bytes: 3652
#include <iostream>
#include <math.h>
#include <iomanip>
using namespace  std;
int main(int argc, const char * argv[]) {
    int a,b,c;
    double rad; //ラジアン
    cin >> a >> b >> c;
    rad = c*M_PI/180; //角度->ラジアン表記
    cout << fixed;
    cout << setprecision(8) << a*b*sin(rad)/2 << "\n" << a+b+(sqrt(a*a+b*b-2*a*b*cos(rad))) << "\n" << b*sin(rad) <<endl;
    return 0;
}



Measured memory_bytes: 3536
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cerr << #x << " = " << x << endl

int main(int qtd, char* nome[])
{
	ios::sync_with_stdio(false);
	cin.tie(0);
 
	int five = 0;
	int seven = 0;
	for(int i=0, x; i<3; i++)
		cin >> x, (x == 5? five++: x == 7? seven++: 0);
	if(five == 2 && seven == 1)
		cout << "YES\n";
	else
		cout << "NO\n";
	
	return 0;
}

Measured memory_bytes: 3648
n = int(input())
cnt = 0
d1, d2 = [0] * n, [0] * n
for i in range(n):
    d1[i], d2[i] = map(int, input().split())

for i in range(n):
    if d1[i] == d2[i]:
        cnt += 1
    else:
        cnt = 0
    
    if cnt == 3:
        print("Yes")
        exit()
print("No")

Measured memory_bytes: 9100
#include<stdio.h>
#include<string.h>
int main(void){

	int i,n;
	char gyo[1001];

	scanf("%s",gyo);
	n=strlen(gyo);

	for(i=0;i<n;i++){
		if(gyo[i]=='A'||gyo[i]=='B'||gyo[i]=='C'){
			printf("%c",gyo[i]+23);
		}else printf("%c",gyo[i]-3);
	}
	printf("\n");
	return 0;
}

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

int main() {
    int t = 1;
    while(t--) {
        int h, w;
        cin>>h>>w;
        int m;
        cin>>m;
        int maxCol = 0, maxRow =0;
        vector<int> hc(h+1, 0), wc(w+1, 0);
        map<pair<int, int>, int > mp;
        for(int i=0; i<m; i++) {
            int x, y;
            cin>>y>>x;
            hc[y]++;
            wc[x]++;
            maxCol = max(maxCol, hc[y]);
            maxRow = max(maxRow, wc[x]);
            mp[{y, x}]++;
        }
        
        vector<int> colsWithMax, rowsWithMax;

        for(int i = 1; i<=h; i++) {
            if(hc[i] == maxCol)
                colsWithMax.push_back(i);
        }

        for(int i = 1; i<=w; i++) {
            if(wc[i] == maxRow)
                rowsWithMax.push_back(i);
        }


        int ans = maxCol + maxRow - 1;

        for(auto i: colsWithMax) {
            for(auto j: rowsWithMax) {
                if(mp.find({i, j}) == mp.end()) {
                    ans++;
                    goto outer;
                }                
            }
        }

        outer:
        cout<<ans<<endl;
    }
    return 0;
}

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

using namespace std;

const int Maxn = 100010;
const int INF = 100010;
int dp[Maxn];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        dp[i] = INF;
    }

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

        int k = 1;
        while(i + pow(6, k) <= n){
            dp[i + (int)pow(6, k)] = min(dp[i + (int)pow(6, k)], dp[i] + 1);
            ++k;
        }
        k = 1;
        while(i + pow(9, k) <= n){
            dp[i + (int)pow(9, k)] = min(dp[i + (int)pow(9, k)], dp[i] + 1);
            ++k;
        }
    }

    cout << dp[n] << endl;

}

Measured memory_bytes: 640
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
    input = input.split("\n");
    // 数値の配列を作る
    const numList0 = input[0].split(' ').map(x => parseInt(x, 10));
    const N = numList0[0];
    const D = numList0[1];
    const xListList = [];
    for (var i = 0; i < N; i++) {
        var xList = input[i + 1].split(' ').map(x => parseInt(x, 10));
        xListList.push(xList);
    }

    var count = 0;
    for (var i = 0; i < N - 1; i++) {
        var xBaseList = xListList[i];
        for (var j = i + 1; j < N; j++) {
            var doubleDistance = 0;
            xTargetList = xListList[j];
            for (var k = 0; k < D; k++) {
                var y = xBaseList[k];
                var z = xTargetList[k];
                doubleDistance += (y - z) * (y - z);            
            }
            if (Number.isInteger(Math.sqrt(doubleDistance))) {
                count++;
            }
        }
    }

    console.log(count);
}
 
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21192
import java.util.*;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);		
		int n = sc.nextInt();
		int count = 0;
		for (int i = 0; i < n; i++) {
			int x = sc.nextInt();
			while (x > 0 && x % 2 == 0) {
				count++;
				x /= 2;
			}
		}
		System.out.println(count);
	}
}


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

int main() {
    int n;
    cin >> n;
    ll a[n+1], ans = 0;
    a[0] = 0;
    map<ll, ll> mp;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i-1];
        mp[a[i]]++;
    }
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        ll num = it->second;
        if (num >= 2) {
            ans += num * (num-1) / 2;
        }
        if (it->first == 0) ans += num;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 14336
#include<iostream>

using namespace std;

int main(){

	int H, W;

	while(1){

		cin >> H >> W;

		if( H == 0 && W == 0) break;

		for( int i = 0; i < H; i++){

			for( int j = 0; j < W; j++ ){

				cout << "#" ;

			}

			cout << "\n";

		}

		cout << endl;

	}

	return 0;

}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long

ll dp[101][100001];
ll mod = 1e9 + 7;


int main(){
	IOS;

	int n,K;
	cin >> n >> K;
	int a[n];
	for(int i=1;i<=n ; ++i){
		cin >> a[i];
	}

	dp[0][0] = 1;

	for(int i=1;i<=n ; ++i){
		ll prefix[K+1];
		memset(prefix,0,sizeof(prefix));
		prefix[0] = dp[i-1][0];
		for(int j=1 ; j<= K ; ++j){
			prefix[j] = prefix[j-1] + dp[i-1][j]; 
			if(prefix[j] >= mod) prefix[j] -= mod;
		}
		for(int j = 0 ; j<= K; ++j){
			if(j-a[i]-1>=0) dp[i][j] = prefix[j] - prefix[j-a[i]-1];
			else dp[i][j] = prefix[j];
			if(dp[i][j] >=mod) dp[i][j] = dp[i][j] % mod;
			dp[i][j] = (dp[i][j] + mod)%mod;
		}

	}
	cout << (dp[n][K] + mod) % mod << endl;
}



Measured memory_bytes: 79104
#include<iostream>
using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  if (a < b) {cout << "a < b" << endl;}
  if (a > b) {cout << "a > b" << endl;}
  if (a == b) {cout << "a == b" << endl;}
  return 0;
}

Measured memory_bytes: 1156
X = int(input())
flag = 0
K = 0
n = 1
ans = 0


def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False


while flag == 0:
    K = (360 * n) / X
    if is_integer_num(K):
        flag = 1
        ans = K
    else:
        n = n + 1

print(int(ans))


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

using namespace std;

int main(){

    string s;
    cin >> s;

    if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]){
        cout << "Bad" << endl;
    }
    else{
        cout << "Good" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void run(void){
  int n;
  scanf("%d",&n);
  int *array=(int *)malloc(sizeof(int)*n);
  int i;
  for(i=0;i<n;i++) scanf("%d",array+i);
  int64 ans=0;
  int t=0;
  int l=0;
  int r=0;
  while(r<n){
    while(r<n && (t&array[r])==0){
      t^=array[r];
      r++;
    }
    ans+=(int64)(r-l)*(r-l+1)/2;
    if(r==n) break;
    while(l<r && (t&array[r])!=0){
      t^=array[l];
      l++;
    }
    ans-=(int64)(r-l)*(r-l+1)/2;
  }
  printf("%lld\n",ans);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 896
#include <stdio.h>
int main(void){
  int i,l,a,x,b,r,num;
  for(i = 0; i <1000; i++){
      scanf("%d %d", &a, &b);
      if(a == 0 && b == 0) break;
      if(a < b){
      x = b;
      b = a;
      a = x;
      }
   num = 0;
  for(l = 0; b != 0; l++){
      r = a%b;
      a = b;
      b = r;
      num++;
  }
  printf("%d %d\n", a, num);
  }
  return 0; 
}


Measured memory_bytes: 2036
#include <stdio.h>
int n, g, x, t;
char s[1000005];
int a[1000000];
int c[1000000];
int main() {
	scanf("%d", &n);
	scanf(" %s", s);
	for (int i = 0; i < n; i++) {
		a[i] = s[i] - '1';
	}
	n--;
	c[0] = 0;
	for (int i = 0; i < n; i++) {
		c[i + 1] = c[i];
		x = n - i;
		g = 0;
		while (x % 2 == 0) {
			g++;
			x /= 2;
		}
		c[i + 1] += g;
		g = 0;
		x = i + 1;
		while (x % 2 == 0) {
			g++;
			x /= 2;
		}
		c[i + 1] -= g;
	}
	for (int i = 0; i <= n; i++) {
		if (c[i] <= 0) {
			t += a[i];
			t %= 2;
		}
	}
	if (t % 2) {
		printf("1\n");
		return 0;
	}
	g = 0;
	for (int i = 0; i <= n; i++) {
		if (a[i] == 1)g = 1;
	}
	if (g) {
		printf("0\n");
		return 0;
	}
	for (int i = 0; i <= n; i++)a[i] /= 2;
	t = 0;
	for (int i = 0; i <= n; i++) {
		if (c[i] <= 0) {
			t += a[i];
			t %= 2;
		}
	}
	if (t % 2) {
		printf("2\n");
	}
	else {
		printf("0\n");
	}
}

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

long long intPow(long long x, long long y){
    long long z = 1;
    for(long long i=0; i<y; i++){
        z *= x;
    }
    return z;
}

int main(){
    long long N, M;
    cin >> N >> M;
    cout << (1800*M+100*N)*intPow(2, M);
    return EXIT_SUCCESS;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long 
using namespace std;
using Graph = vector<vector<int>>;
const int MOD = 998244353;

signed main() {
  int N;
  cin >> N;
  
  vector<int> A(N-1);
  vector<int> B(N-1);
  Graph G(N);
  for( int i = 0; i < N-1; i++ ){
    cin >> A.at(i) >> B.at(i);
    A.at(i)--;
    B.at(i)--;
    G.at(A.at(i)).push_back(B.at(i));
    G.at(B.at(i)).push_back(A.at(i));
  }
  
  int V = 0;
  int Vn = 0;
  for( int i = 0; i < N; i++ ){
    if( G.at(i).size() > Vn ){
      Vn = G.at(i).size();
    }
  }
  
  vector<int> dist(N, -1);
  queue<int> que;
  
  dist.at(0) = 1;
  que.push(0);
  
  while( !que.empty() ){
    int v = que.front();
    que.pop();
    
    int color = dist.at(v);
    for( int nv : G.at(v) ){
      if( dist.at(nv) != -1 ) continue; //すでに通っていたらスルー
      color++;
      if( color > Vn ) color = 1;
      dist.at(nv) = color;
      que.push(nv);
    }
  }
  cout << Vn << endl;
  for( int i = 0; i < N-1; i++ ){
    cout << dist.at(B.at(i)) << endl;
  }
}


Measured memory_bytes: 9088
N,M=map(int,input().split())
ship=[list(map(int,input().split())) for _ in range(M)]
port1=[]
port2=[]
for i in range(M):
    if ship[i][0]==1:
        port1.append(ship[i][1])
    if ship[i][1]==N:
        port2.append(ship[i][0])

port1=set(port1)
port2=set(port2)
if len(port1&port2)>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

int main() {
    /* S, T, and U are strings of lengths between 1 and 10 (inclusive) consisting of lowercase English letters.
    S≠T
    S=U or T=U.
    1 ≤ A,B≤ 10 */
   
    string  S, T, U ;
    cin >> S >> T ; // 1 ≤ H,A ≤ 10^4
    int A , B ;
    cin >> A >> B ;
    cin >> U ;
    if (U == S) A-- ;
    if (U == T) B-- ;
    cout << A << " " << B << endl ;
	return 0;
}

Measured memory_bytes: 3628
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const long double PI = acos(-1);

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

	ll n;
	cin >> n;

	vector<ll> a(n);
	rep(i, n) cin >> a[i];

	ll ans = inf;
	for (int i = -100; i <= 100; i++) {
		ll sum = 0;
		rep(j, n) {
			sum += (i - a[j]) * (i - a[j]);
		}
		chmin(ans, sum);
	}

	out(ans);

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fort(i,n) for (int i = 1; i <= n; i++)
#define ll long long
#define pi pair<int,int>
#define sz size()
#define er erase
#define fr first
#define sc second
using namespace std;

int n,x[105],y[105],h[105],ans,v,a,b,c,X[105],Y[105];

int32_t main()
{
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n;
    fort(i,n)
    {
        cin >> x[i] >> y[i] >> h[i];
        if (h[i]) a=x[i], b=y[i], c=h[i];
    }
    if (c==0)
    {
        fort(i,n)
            ++X[x[i]], ++Y[y[i]];
        fort(i,101)
            if (Y[i-1]==0) b=i-1;
        cout << 0 << ' ' << b << ' ' << 1;
        return 0;
    }
    fort(i,101)
    {
        fort(j,101)
        {
            v=abs(a-i+1)+abs(b-j+1)+c, ans=0;
            fort(k,n)
            {
                if (h[k]==0&&v<=abs(i-1-x[k])+abs(j-1-y[k])) ++ans;
                if (h[k]!=0&&v==abs(i-1-x[k])+abs(j-1-y[k])+h[k]) ++ans;
            }
            if (ans==n)
            {
                cout << i-1 << ' ' << j-1 << ' ' << v;
                return 0;
            }
        }
    }
}


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

int main(void){
    long n;
    cin >> n;
    vector<long> a(n);
    for(long i=0; i<n; i++){
        cin >> a[i];
    }
    long count=0;
    for(long i=0; i<n-1; i++){
        if(a[i]==a[i+1]){
            a[i+1]=101+count;
            count++;
        }
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
<?php
fscanf(STDIN, '%d', $cnt);
$nums = array_map('intval', explode(' ', trim(fgets(STDIN))));
$ans = true;
for ($i=0; $i < $cnt; $i++) { 
    (int)$ans *= $nums[$i];
}
$limit = pow(10, 18);
if ($ans > $limit) {
    $ans = -1;
} 
echo (int)$ans;

Measured memory_bytes: 28692
fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map(String::toInt)

    val kList = mutableListOf<Int>()
    val sMap = mutableMapOf<Int, List<Int>>()
    for (i in 1..m) {
        val input = readLine()!!.split(' ').map(String::toInt)
        val k = input[0]
        kList.add(k)
        sMap[i] = input.takeLast(k)
    }
    val pList = readLine()!!.split(' ').map(String::toInt)

    val last = Math.pow(2.0, n.toDouble()).toInt() - 1
    var ans = 0
    for (i in 0..last) {
        val charArray = String.format("%010d", Integer.toBinaryString(i).toInt()).toCharArray().reversedArray()
        var allTrue = true
        for (j in 1..m) {
            var sum = 0
            for (s in sMap[j]!!) {
                sum += charArray[s - 1].toInt()
            }
            if (sum % 2 != pList[j - 1]) {
                allTrue = false
                break
            }
        }
        if (allTrue) ans++
    }

    println(ans)
}


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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    rep(i, n) cin >> d[i];
    ll ans = 0;
    rep(i, n) {
        for (int j = i + 1; j < n; j++) {
            ans += d[i] * d[j];
        }
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    INT_BITS = 64
    n = ni()
    a = nl()[::-1]
    s = ns()[::-1]
    lis = [0]*64
    for i in range(n):
        if s[i] == '1':
            c = a[i]
            for x in lis[::-1]:
                if x == 0:
                    continue
                if c & (1 << (x.bit_length() - 1)):
                    c ^= x
            if c:
                print(1)
                return
        else:
            c = a[i]
            for x in lis[::-1]:
                if x == 0:
                    continue
                if c & (1 << (x.bit_length() - 1)):
                    c ^= x
            if c:
                lis[c.bit_length() - 1] = c
    print(0)
    return

T = ni()
for _ in range(T):
    solve()


Measured memory_bytes: 9256
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

const int N = 3e5 + 5;
const int MOD = 1e9 + 7;
const int64_t INF = 5e18;
const double PI = 2 * acos(0.0);
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int64_t ans = -INF, mn = INF, mx = -INF, mn2 = INF, mx2 = -INF, mn3 = INF, mx3 = -INF, mn4 = mn, mx4 = mx;
    for (int i = 0; i < n; i++) {
        int64_t x, y;
        cin >> x >> y;
        mx = max(mx, x + y);
        mn = min(mn, x + y);
        mx2 = max(mx2, x - y);
        mn2 = min(mn2, x - y);
        mx3 = max(mx3, -x + y);
        mn3 = min(mn3, -x + y);
        mx4 = max(mx4, -x -y);
        mn4 = min(mn4, -x -y);
        ans = max(ans, abs(mx - mn));
        ans = max(ans, abs(mx2 - mn2));
        ans = max(ans, abs(mx3 - mn3));
        ans = max(ans, abs(mx4 - mn4));
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<string>
using namespace std;
using lint=long long;
int main(){
  int N; cin>>N;
  int P[10]={0,0,0,0,0,0,1,1,1,2};
  int Q[10]={1,1,1,2,2,3,2,2,3,3};
  int R[10]={2,3,4,3,4,4,3,4,4,4};
  lint C[5]={0,0,0,0,0};
  for(int i=0;i<N;i++){
    string S; cin>>S;
    if(S[0]=='M') C[0]++;
    if(S[0]=='A') C[1]++;
    if(S[0]=='R') C[2]++;
    if(S[0]=='C') C[3]++;
    if(S[0]=='H') C[4]++;
  }
  lint ans=0;
  for(int i=0;i<10;i++)
    ans+=(C[P[i]]*C[Q[i]]*C[R[i]]);
  cout<<ans<<endl;  
  return 0;
}

Measured memory_bytes: 256
n, k, c = list(map(int, input().split()))
s = input()

mae, usiro = [-1] * n, [-1] * n

now, at = 1, 0
while at < n:
    if s[at] == 'x':
        at += 1
    else:
        mae[at] = now
        at += c + 1
        now += 1
        if now > k:
            break

now, at = k, n-1
while at >= 0:
    if s[at] == 'x':
        at -= 1
    else:
        usiro[at] = now
        at -= c + 1
        now -= 1
        if now <= 0:
            break

for i in range(n):
    if mae[i] != -1 and mae[i] == usiro[i]:
        print(i + 1)


Measured memory_bytes: 20628
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

const int N = 500005;

// [1, n]
int bit[N], n, q;

int sum(int i) {
  int s = 0;
  while (i > 0) {
    s += bit[i];
    i -= i & -i;
  }
  return s;
}

void add(int i, int x) {
  while (i <= n) {
    bit[i] += x;
    i += i & -i;
  }
}

int main() {
  cin >> n >> q;
  vector<int> c(n);
  rep(i, n) cin >> c[i];
  rep(i, n) c[i]--;
  vector<pair<P, int>> query(q);
  rep(i, q) {
    int l, r;
    cin >> l >> r;
    query[i] = make_pair(make_pair(r, l), i);
  }
  sort(query.begin(), query.end());

  vector<int> gb(n, -1);
  rep(i, n+1) bit[i] = 0;
  vector<int> ans(q);

  int qi = 0;
  rep(i, n) {
    if (gb[c[i]] != -1) add(gb[c[i]], -1);
    gb[c[i]] = i+1;
    add(i+1, 1);
    while (query[qi].first.first == i+1) {
      int ai = query[qi].second;
      int l = query[qi].first.second;
      int r = query[qi].first.first;
      ans[ai] = sum(r) - sum(l-1);
      qi++;
    }
  }

  rep(i, q) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 17376
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
using namespace std;
typedef long long ll;
const double PI=3.14159265358979323846/180.0;

const ll MOD = 1e9+7;

int main()
{
	double a,b,x;
	cin>>a>>b>>x;
	double s=x/a;
	double ans=0.0;
	if(s==a*b)
		ans=0;
	else if(s<=a*b/2.0)
	{
		double a2=s*2.0/b;
		cerr<<s<<" "<<a2<<endl;
		ans=atan2(b,a2)/PI;
	}else{
		double b2=s*2.0/a-b;
		double a2=a*b/(b-b2);
		cerr<<b2<<" "<<a2<<endl;
		ans=atan2(b,a2)/PI;
	}
	cout<<setprecision(12)<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;
int inf = 100000000;

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,x;
    cin >> n >> m >> x;
    vector<vector<int>> a(n,vector<int>(m));
    vector<int> c(n);
    rep(i,n){
        cin >> c[i];
        rep(j,m){
            cin >> a[i][j];
        }
    }
    // int q = pow(2,n);
    ll ans = 100000000;
    for(int bit = 0;bit < (1<<n);++bit){
        vector<int> S;
        rep(i,n){
            if(bit&(1<<i)){
                S.push_back(i);
            }
        }
        vector<int> sum(m);
        ll res = 0;
        for(auto v:S){
            rep(j,m){
                sum[j]+=a[v][j]; 
            }
            res += c[v];
        }

        bool w = false;
        rep(k,m){
            if(sum[k]>=x){
                w =true;
            }
            else{
                w = false;
                break;
            }
        }
        if(w){
            ans = min(ans,res);
        }
    }
    if(ans == 100000000){
        cout << -1;
    }
    else{
        cout << ans;
    }
    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>

int main(void)
{
	using namespace std;
	int data[3];
	for(int i=0; i<3; i++){
		cin >> data[i];
	}

	int count = 0;
	for(int j=data[0]; j <= data[1]; j++){
		if(data[2] % j == 0) count++;
	}
	cout << count << endl;

	return 0;

}

Measured memory_bytes: 3120
//  ____            _                  _                       _       _
// |  _ \ _   _ ___| |_    ___ _ __   | |_ ___ _ __ ___  _ __ | | __ _| |_ ___
// | |_) | | | / __| __|  / __| '_ \  | __/ _ \ '_ ` _ \| '_ \| |/ _` | __/ _ \
// |  _ <| |_| \__ \ |_  | (__| |_) | | ||  __/ | | | | | |_) | | (_| | ||  __/
// |_| \_\\__,_|___/\__|  \___| .__/___\__\___|_| |_| |_| .__/|_|\__,_|\__\___|
//                            |_| |_____|               |_|

//https://github.com/manta1130/Competitive_Programming_Template_Rust

#[macro_use]
mod input {

    use std;
    use std::io;

    const SPLIT_DELIMITER: char = ' ';

    #[macro_export]
    #[allow(unused_macros)]
    macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

    #[allow(dead_code)]
    pub fn input_line_str() -> String {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        s.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn p<T>(t: T)
    where
        T: std::fmt::Display,
    {
        println!("{}", t);
    }

    #[allow(dead_code)]
    pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<Vec<T>> = Vec::new();

        for _ in 0..line {
            let vec_line = input_vector();
            v.push(vec_line);
        }
        v
    }

    #[allow(dead_code)]
    pub fn input_vector<T>() -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<T> = Vec::new();

        let s = input_line_str();
        let split_result = s.split(SPLIT_DELIMITER);
        for z in split_result {
            let buf = match z.parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error"),
            };
            v.push(buf);
        }
        v
    }

    #[allow(dead_code)]
    pub fn input_vector_row<T>(n: usize) -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v = Vec::with_capacity(n);
        for _ in 0..n {
            let buf = match input_line_str().parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error"),
            };
            v.push(buf);
        }
        v
    }

    pub trait ToCharVec {
        fn to_charvec(&self) -> Vec<char>;
    }

    impl ToCharVec for String {
        fn to_charvec(&self) -> Vec<char> {
            self.to_string().chars().collect::<Vec<_>>()
        }
    }
}

use input::*;

fn gcd(a: isize, b: isize) -> isize {
    if b == 0 {
        return a;
    }
    gcd(b, a % b)
}

fn main() {
    let (a, b, c, d): (isize, isize, isize, isize);
    input!(a, b, c, d);
    p((a - c).abs() + (b - d).abs() - gcd((a - c).abs(), (b - d).abs()));
}


Measured memory_bytes: 4352
#include <algorithm>
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
const int inf = 1000000007;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % inf;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), inf - 2, inf) % inf * mod_pow(kai(y), inf - 2, inf) % inf;
}
struct union_find {
	int par[200010], size_[200010];
	void init(int x) {
		rep(i, x) { par[i] = i; size_[i] = 1; }
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (size_[x] < size_[y]) {
			par[x] = y;
			size_[y] += size_[x];
		}
		else {
			par[y] = x;
			size_[x] += size_[y];
		}
	}
};
struct edge { int to, cost; };
int a[30];
signed main() {
	int n;
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}
	int ans = 0;
	rep(i, n - 2) {
		if (a[i] < a[i + 1] && a[i + 1] < a[i + 2])ans++;
		else if (a[i] > a[i + 1] && a[i + 1] > a[i + 2])ans++;
	}
	cout << ans << endl;
}



Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  string s;
  ll q;
  cin >> s >> q;
  deque<char> dq;
  rep(i, s.size()) dq.push_back(s[i]);
  bool r = false;
  rep(i, q) {
    ll t;
    cin >> t;
    if(t == 1) {
      r = !r;
    } else {
      ll f;
      char c;
      cin >> f >> c;
      f--;
      if(f ^ r)
        dq.push_back(c);
      else
        dq.push_front(c);
    }
  }
  rep(i, dq.size()) {
    char c;
    if(r) {
      c = dq.back();
      dq.pop_back();
    } else {
      c = dq.front();
      dq.pop_front();
    }
    cout << c;
  }
  cout << endl;
}

Measured memory_bytes: 896
#include<iostream>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    int sub[n] = {0};
    int a;
    for (int i = 0; i < n - 1; i++) {
        cin >> a;
        sub[a - 1]++;
    }
    for (int i = 0; i < n; i++) {
        cout << sub[i] << '\n';
    }
    return 0;
}

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



int main(){
  int N,M;
  cin >> N >> M;
  vector<int> s(M);
  vector<char> c(M);
  for(int i=0;i<M;++i) cin >> s[i] >> c[i];
  int ans= -1;
  if(N==1){
  for(int i=0;i<10;++i){
    bool flag = true;
    for(int j=0;j<M;++j){
      if(to_string(i)[s[j]-1]!=c[j]) flag = false;
    }
    if(flag){
      ans = i;
      break;
    }
  }
  }
  else if(N>=2) {
  for(int i=pow(10,(N-1));i<pow(10,N);++i){
    bool flag = true;
    for(int j=0;j<M;++j){
      if(to_string(i)[s[j]-1]!=c[j]) flag = false;
    }
    if(flag){
      ans = i;
      break;
    }
  }
  }
  cout << ans << endl;
}

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

using namespace std;

int main(){
    long long int N,K,now=1;
    cin >> N >> K;
    for(int i=0;i<N;i++){
        if(N<now*K){
            cout << i+1 << endl;
            break;
        }else{
            now *= K;
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string a,b;
int main(){
    getline(cin,a);
    getline(cin,b);
    sort(a.begin(),a.end());
    sort(b.begin(),b.end(),greater<char>());
    if(a<b)
        cout<<"Yes"<<endl;
    else 
        cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ALL(n) begin(n),end(n)
#define IN(a, x, b) (a<=x && x<b)
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
template<class T> inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T & a, const T b) { return a = (a > b) ? b : a; }

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);

int main()
{
    INIT;
    int n;
    cin >> n;
    int sum = 0;
    int ma = -1;
    int p;
    REP(i,n){
        cin >> p;
        sum += p;
        ma = max(ma, p); 
    }
    cout << sum - ma / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define debug2(x, y)                       \
  cerr << "(" << #x << "," << #y << ") = " \
       << "(" << x << "," << y << ")\n"
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5 << 28, MOD = 1e9 + 7;

int N, M;
string S;
vi va, vb;

void input() {
  ;
  cin >> N;
  va.resize(N + 1);
  vb.resize(N + 1);
  rep(i, 1, N) { cin >> va[i]; };
}

void solve() {
  set<int> ans;
  rrep(i, N, 1) {
    int bl = 0;
    for (int k = i; k <= N; k += i) {
      bl ^= vb[k];
    }

    if (va[i] ^ bl) {
      // ireru.
      ans.insert(i);
      vb[i] = 1;
    }
  };
  cout << ans.size() << endl;
  for (auto x : ans) {
    cout << x << " ";
  }
  cout << endl;
  ;

  ;
}
signed main() {
  input();
  solve();
  return 0;
}

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

using namespace std;

int main(void) {
	int bingo[3][3];	

	for (int i = 0; i < 3; i++) {
		for (int j= 0; j < 3; j++) {
			int c;
			cin >> c;
			bingo[i][j] = c;
		}
	}

	int n;
	cin >> n;
	bool indices[3][3];
	for (int i = 0; i < 3; i++) {
		for (int j = 0;j< 3 ; j++){
			indices[i][j] = false;
		}
	}


	for (int x = 0; x < n; x++) {		
		int b;
		cin >> b;
		bool stop = false;
		
		// find b
		for (int i =0; i< 3 && !stop; i++){
			for (int j = 0; j < 3 && !stop;j++) {
				if (bingo[i][j] == b) {
					indices[i][j] = true;
					stop = true;
				}
			}
		}
	}
	// check
	
	if (n == 0) {
		cout << "No" << endl;
		return 0;
	}

	// horizontal

	for (int i = 0; i < 3; i++) {
		bool res = (indices[i][0] && indices[i][1] && indices[i][2]);
		if (res) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	// Vertical
	for (int i = 0; i < 3; i++) {
		bool res = (indices[0][i] && indices[1][i] && indices[2][i]);
		if (res) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	// diagonal	
	
	bool res = (indices[0][0] && indices[1][1] && indices[2][2]);
	if (res) {
		cout << "Yes" << endl;
		return 0;
	}
	
	res = (indices[0][2] && indices[1][1] && indices[2][0]);
	if (res) {
		cout << "Yes" << endl;
		return 0;
	}


	cout << "No" << endl;
}


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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vvll = vector<vll>;
using vst = vector<st>;
using vchar = vector<char>;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
ll mod = 1000000007;

int main(){
  ll n, k;
  cin >> n >> k;
  vll a(n);
  vin(a);

  vll count(200001, 0);
  vrep(i, a) count.at(i)++;
  sort(all(count));
  auto itlow = lower_bound(all(count), 1);
  ll x = distance(itlow, count.end()) - k;
  ll y = 0;
  ll kind = max(y, x);
  cout << accumulate(itlow, itlow + kind, 0) << endl;
}

Measured memory_bytes: 3328
import itertools
n=int(input())
a=[]
for i in range(1,n+1):
  a.append(i)
aa=list(itertools.permutations(a))

p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))

ap=aa.index(p)
aq=aa.index(q)

print(abs(ap-aq))

Measured memory_bytes: 8052
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int inf = 1000000000;

int main(){
    int n,m;
    cin >> n >> m;
    int a[m];
    int b[m];
    vector<vector<int>> edge(n);
    rep(i,m){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        edge.at(a[i]).push_back(b[i]);
        edge.at(b[i]).push_back(a[i]);
    }
    /*rep(i,n){
        for(int x : edge.at(i)){
            cout << x << endl;
        }
    }*/
    bool visited[n];
    rep(i,n){
        visited[i] = false;
    }
    int ans = 1;
    for(int i=0; i<n; i++){
        int cnt = 0;
        if(!visited[i]){
            queue<int> q;
            q.push(i);
            while(!q.empty()){
                int c = q.front(); 
                //cout << c << endl;
                q.pop();
                if(!visited[c]){
                    visited[c] = true;
                    cnt++;
                    for(int x : edge.at(c)){
                        if(!visited[x]){
                            q.push(x);
                        }
                    }
                }
            }
            ans = max(ans,cnt);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 16456
#include <bits/stdc++.h>
using namespace std;
#define N 5010
#define mod 1000000007
inline int read() {
    int x=0;
    char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x;
}
int tot=1;
int fir[N<<1],nex[N<<1],got[N<<1];
inline void AddEdge(int x,int y) {
    nex[++tot]=fir[x],fir[x]=tot,got[tot]=y;
}
int siz[N],g[N];
int f[N][N],_[N];
inline void dfs(int x,int fa) {
    f[x][siz[x]=1]=1;
    for (int i=fir[x];i;i=nex[i]) {
        int y=got[i];
        if (y==fa) continue;
        dfs(y,x);
        for (int j=1;j<=siz[x]+siz[y];j++) _[j]=0;
        for (int j=1;j<=siz[x];j++) {
            for (int k=0;k<=siz[y];k++) {
                (_[j+k]+=1LL*f[x][j]*f[y][k]%mod)%=mod;
            }
        }
        for (int j=1;j<=siz[x]+siz[y];j++) f[x][j]=_[j]; siz[x]+=siz[y];
    }
    for (int i=2;i<=siz[x];i+=2) {
        (f[x][0]+=mod-1LL*f[x][i]*g[i]%mod)%=mod;
    }
}
int main() {
    int n=read();
    for (int i=1;i<=n-1;i++) {
        int x=read(),y=read();
        AddEdge(x,y),AddEdge(y,x);
    }
    g[0]=1;
    for (int i=2;i<=n;i+=2) {
        g[i]=1LL*g[i-2]*(i-1)%mod;
    }
    dfs(1,0);
    cout<<mod-f[1][0]<<endl;
    return 0;
}

Measured memory_bytes: 97024
import sys
input=sys.stdin.readline

n=int(input())
xyu=[]
for _ in range(n):
  x,y,u=input().split()
  x,y=int(x),int(y)
  xyu.append((x,y,u))

ans=10**20
ud=[[]for _ in range(200001)]
lr=[[]for _ in range(200001)]
for x,y,u in xyu:
  if u in "UD":
    ud[x].append((y,u))
  else:
    lr[y].append((x,u))
for i in range(200001):
  ud[i].sort()
  for j in range(1,len(ud[i])):
    if ud[i][j-1][1]+ud[i][j][1]=="UD":
      ans=min(ans,(ud[i][j][0]-ud[i][j-1][0])*5)
  lr[i].sort()
  for j in range(1,len(lr[i])):
    if lr[i][j-1][1]+lr[i][j][1]=="RL":
      ans=min(ans,(lr[i][j][0]-lr[i][j-1][0])*5)

rup_rd=[[]for _ in range(400001)]
rup_lu=[[]for _ in range(400001)]
lup_ld=[[]for _ in range(400001)]
lup_ru=[[]for _ in range(400001)]
for x,y,u in xyu:
  if u=="U":
    rup_lu[x-y+200000].append((x,y,u))
    lup_ru[x+y].append((x,y,u))
  if u=="D":
    rup_rd[x-y+200000].append((x,y,u))
    lup_ld[x+y].append((x,y,u))
  if u=="L":
    rup_lu[x-y+200000].append((x,y,u))
    lup_ld[x+y].append((x,y,u))
  if u=="R":
    rup_rd[x-y+200000].append((x,y,u))
    lup_ru[x+y].append((x,y,u))
for i in range(400001):
  rup_rd[i].sort()
  rup_lu[i].sort()
  lup_ld[i].sort()
  lup_ru[i].sort()
  for j in range(1,len(rup_rd[i])):
    sx,sy,su=rup_rd[i][j-1]
    tx,ty,tu=rup_rd[i][j]
    if su+tu=="RD":ans=min(ans,(abs(sx-tx)+abs(sy-ty))*5)
  for j in range(1,len(rup_lu[i])):
    sx,sy,su=rup_lu[i][j-1]
    tx,ty,tu=rup_lu[i][j]
    if su+tu=="UL":ans=min(ans,(abs(sx-tx)+abs(sy-ty))*5)
  for j in range(1,len(lup_ld[i])):
    sx,sy,su=lup_ld[i][j-1]
    tx,ty,tu=lup_ld[i][j]
    if su+tu=="DL":ans=min(ans,(abs(sx-tx)+abs(sy-ty))*5)
  for j in range(1,len(lup_ru[i])):
    sx,sy,su=lup_ru[i][j-1]
    tx,ty,tu=lup_ru[i][j]
    if su+tu=="RU":ans=min(ans,(abs(sx-tx)+abs(sy-ty))*5)
if ans==10**20:
  print("SAFE")
else:
  print(ans)

Measured memory_bytes: 248728
#include <iostream>
#include <vector>
using namespace std;
typedef int64_t I;
typedef vector<I> vI;

const I M = 1000000007;

I pow(I x, I y) {
  if (y == 0) return 1;
  else if (y == 1) return x;
  I y2 = y / 2;
  return pow(x, y2) * pow(x, y - y2) % M;
}

int main() {
  I n, k; cin >> n >> k;
  vI counts(k + 1);
  for (I i = 1; i <= k; i++) {
    I k1 = k / i;
    if (i > 1 && k1 == k / (i - 1))
      counts[i] = counts[i - 1];
    else
      counts[i] = pow(k1, n);
  }
  I r = 0;
  for (I i = k; i >= 1; i--) {
    for (I j = i * 2; j <= k; j += i) {
      counts[i] = (counts[i] - counts[j] + M) % M;
    }
    r = (r + counts[i] * i) % M;
  }
  cout << r << endl;
}



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

int main(){
    int n;
    cin >> n;
    vector<int>high(n);
    for (int i = 0; i < n; i++) {
        cin >> high.at(i);
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
        bool okey = true;
        for (int j = 0; j < i; j++) {
            if (high.at(i) < high.at(j)) {
                okey = false;
            }
        }
        if (okey) {
            count++;
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}


int main()
{
  string s ;
  cin >> s ;
  int n = SZ(s) ;
  
  REP(i,n-8){
    cout << s.at(i) ;
  }
  
  cout <<endl ;

  return 0 ;
}




Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int n;
string s[100005];
int t[100005];
string S;
bool x=false;
ll ans;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i]>>t[i];
    }
    cin>>S;
    for(int i=0;i<n;i++){
        if(x) ans+=t[i];
        if(s[i]==S){
            x=true;
        }
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 6740
#include <bits/stdc++.h>
//Fast io
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
//Class shorthands
#define ll long long
#define db long double
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
//Function Shorthands
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mp make_pair
#define po pop_back
#define eb emplace_back
//Code Shorthands
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repe(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=b;i>=a;i--)
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
//Constants
#define hell 1000000007
#define PI acos(-1.0)
using namespace std;
bool check(ll a, ll b, ll c){
	int m = max({a,b,c});
	if(a==b || a==c || b==c) return false;
	return a+b+c-m>m;
}
void solve(){
	int n;
	cin>>n;
	ll a[n];
	rep(i,0,n) cin>>a[i];
	ll ans = 0;
	sort(a, a+n);
	rep(i,0,n){
		rep(j,i+1,n){
			rep(k,j+1,n){
				if(check(a[i],a[j],a[k])) ans++;
			}
		}
	}
	cout<<ans<<endl;
}

int main(){
	io;
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
using LL  = long long;
using VI  = vector<LL>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using VS  = vector<string>;
using PII = pair<LL, LL>;
using VP  = vector<PII>;
#define PB           push_back
#define MP           make_pair
#define SZ(a)        LL((a).size())
#define EACH(x, c)   for (auto x : (c))
#define ALL(c)       (c).begin(), (c).end()
#define REVERSE(c)   reverse(ALL(c))
#define SORT(c)      stable_sort(ALL(c))
#define RSORT(c)     stable_sort((c).rbegin(), (c).rend())
#define FSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first < y.first;});
#define FRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first > y.first;});
#define SSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second < y.second;});
#define SRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second > y.second;});
#define FOR(i, a, b) for (LL i = (a); i < (b); ++i)
#define REP(i, n)    FOR(i, 0, n)
#define $(x) {cout << #x << " = " << (x) << endl;}

LL calc(PII& x, PII& y, VP& X) {
    LL dx = y.first - x.first;
    LL dy = y.second - x.second;
    //$(dx);
    //$(dy);
    unordered_set<string> Y;
    EACH(e, X) {
        string s = to_string(e.first) + "," + to_string(e.second);
        Y.insert(s);
    }
    LL ret = 0;
    EACH(e, X) {
        LL nx = e.first + dx;
        LL ny = e.second + dy;
        //$(nx);
        //$(ny);
        string q = to_string(nx) + "," + to_string(ny);
        if (Y.count(q) != 0) {
            ret++;
        }
    }
    return ret;
}
        

int main() {
    LL N;
    cin >> N;
    VP X(N);
    REP(i, N) {
        LL x, y;
        cin >> x >> y;
        X[i] = MP(x, y);
    }

    LL ans = N;
    REP(i, N - 1) {
        for (LL j = i + 1; j < N; ++j) {
            LL tmp = N - calc(X[i], X[j], X);
            /*$(i);
            $(j);
            $(tmp);*/
            if (ans > tmp) ans = tmp;
        }
    }
    cout << ans << endl;
	
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[10];
    int i,c=0,j=0;
    for(i=0;i<3;i++){
        cin>>s[i];
    }
    for(i=0;i<3;i++){
       if(s[i]=='o')
        c++;
    }
    j=j+700+(c*100);
    cout<<j<<endl;
   return 0;
}




Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner stdin = new Scanner(System.in);
		int n = stdin.nextInt();
		String s =stdin.next();
		int k = stdin.nextInt();
		char[] c = s.toCharArray();
		for(int i = 0;i<n;i++) {
			if(c[i]!=c[k-1]) {
				c[i]='*';
			}
		}
		for(int i = 0;i<n;i++) {
			System.out.print(c[i]);
		}


	}

}


Measured memory_bytes: 21844