akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(int i = (a); i >= (b); i--)
#define LLFOR(i, a, b) for(long long i = (a); i < (b); ++i)
#define LLRFOR(i, a, b) for(long long i = (a); i >= (b); i--)
#define SORT(v, n) sort(v, v+n)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define LLREP(i, n) for(long long i = 0; i < (n); ++i)
#define RREP(i, n) for(int i = n; i >= n; i--)
#define LLRREP(i, n) for(long long i = n; i >= n; i--)

#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))

#define endl "\n"
#define pb push_back
#define ret return

#define INF 2000000000	//int型は2 * 10^9ぐらいまで
#define MOD 1000000007
 
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};

typedef long long ll;
typedef unsigned long long ull;

int MAX(int a,int b){if(a>b){return a;}return b;}
int MIN(int a,int b){if(a<b){return a;}return b;}
int GCD(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
int LCM(int a,int b){int c=GCD(a,b);a/=c;return a*b;}
int nCr(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
int nHr(int a,int b){return nCr(a+b-1,b);}
int POW(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
ll LLMAX(ll a,ll b){if(a>b){return a;}return b;}
ll LLMIN(ll a,ll b){if(a<b){return a;}return b;}
ll llGCD(ll a,ll b){ll c;while(b!=0){c=a%b;a=b;b=c;}return a;}
ll llLCM(ll a,ll b){ll c=llGCD(a,b);a/=c;return a*b;}
ll llnCr(ll a,ll b){ll i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
ll llnHr(ll a,ll b){return llnCr(a+b-1,b);}
ll llpow(ll a,ll b){ll i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

signed main(){
	//solve AXCxxx-X
	cin.tie(0);
	ios::sync_with_stdio(false);

	int a, b;
	cin >> a >> b;
	if(a + b == 15) cout << '+' << endl;
	else if(a * b == 15) cout << '*' << endl;
	else cout << 'x' << endl;

	ret 0; 
}

Measured memory_bytes: 896
import java.util.*;
public class Main {
    public static void main(String[] args){
      // 入力
      Scanner sc = new Scanner(System.in);
      long N = sc.nextLong();
      long A = sc.nextLong();
      long B = sc.nextLong();
      
      // 周期数と余りをカウント
      long roop = N / (A+B);
      long remain = N % (A+B);
      
      // 青いボールをカウント
      long result = A * roop;
      if(remain < A){
        result += remain;
      }else{
        result += A;
      }
        
      // 出力
      System.out.println(result);
    }
    
}

Measured memory_bytes: 23892
N,M = map(int,input().split())
es = []
for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    es.append((a,b))

parent = None
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    parent[ra] = rb;

ans = 0
for i in range(M):
    parent = [k for k in range(N)]
    for j,e in enumerate(es):
        if j == i: continue
        a,b = e
        unite(a,b)
    a,b = es[i]
    if not is_same(a,b):
        ans += 1
print(ans)


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

int R[100001];

int main(void) {
    int N, a;
    cin >> N;
    rep(i, N) {
        cin >> a;
        R[i] = a-1;
    }
    int ans = 0;
    rep(i, N) {
        if(R[R[i]] == i) ans++;
    }
    cout << ans/2 << endl;
}

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

using namespace std;

#define rep(i, a) for (int i = 0; i < a; i++)
#define reps(i, a, b) for (int i = a; i < b; i++)
#define MP(a, b) make_pair(a, b)

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	cout << (a ^ b ^ c) << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long h,w,m,i,j,x,y,mr=-1,mc=-1,m1=-1,m2=-1,ans=0;
    cin>>h>>w>>m;
    map<long long,long long>r,c;
    map<pair<long long,long long>,long long>vis;
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        vis[{x,y}]=1;
        r[x]++;
        if(r[x]>m1)
        {
            mr=x;
            m1=r[x];
        }
        c[y]++;
        if(c[y]>m2)
        {
            mc=y;
            m2=c[y];
        }
    }
    long long p,q;
    if(m1>=m2)
        {
            ans+=m1;
            long long haha=-1;
            for(j=1;j<=w;j++)
            {
                if(c[j]>haha)
                {
                    p=j;
                    haha=c[j];
                }
            }
            for(j=1;j<=w;j++)
            {
                if(c[j]==haha)
                {
                    if(vis[{mr,j}]==0){
                    p=j;
                    haha=c[j];
                    break;
                    }
                }
            }
            ans+=haha;
            //cout<<mr<<" "<<p<<endl;
            if(vis[{mr,p}]==1)
                ans--;
                //ans--;
        }
        else
        {
            ans+=m2;
            long long haha=-1;
            for(j=1;j<=h;j++)
            {
                if(r[j]>haha)
                {
                    q=j;
                    haha=r[j];
                }
            }
            for(j=1;j<=h;j++)
            {
                if(r[j]==haha)
                {
                    if(vis[{j,mc}]==0){
                    q=j;
                    haha=r[j];
                    break;
                    }
                }
            }

            ans+=haha;
            if(vis[{q,mc}]==1)
                ans--;
        }
        cout<<ans<<endl;

}


Measured memory_bytes: 59876
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>

using namespace std;
typedef long long ll;

ll A[6] = {};
ll Min = 10;
ll box = 1;
ll ans = 0;

int main() {
	cin >> A[1];
	if (A[1] % 10 != 0)Min = A[1] % 10;
	for (int i = 2; i <= 5; i++) {
		cin >> A[i];
		if (A[i] % 10 != 0 &&  A[i] % 10 < Min) {
			Min = A[i] % 10;
			box = i;
		}
	}
	for (int i = 1; i <= 5; i++) {
		if (i != box) {
			while (A[i] % 10 != 0)A[i]++;
			ans += A[i];
		}
	}
	cout << ans + A[box] << endl;
	return 0;
}

Measured memory_bytes: 256
// 2020-07-25 02:35:32
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  int n, t;
  cin >> n >> t;
  deque<P> c;
  rep(i, n) {
    int a, b;
    cin >> a >> b;
    c.emplace_back(P(b, a));
  }
  sort(c.rbegin(), c.rend());
  {
    auto first = c.front(); c.pop_front();
    c.emplace_back(first);
  }
  vector<vector<int> > dp(n+1, vector<int>(t, 0));
  rep(i, n) {
    int a, b;
    tie(b, a) = c[i];
    rep(j, t) {
      dp[i+1][j] = dp[i][j];
      if(a <= j) chmax(dp[i+1][j], dp[i][j-a] + b);
    }
  }
  int v = dp[n][t-1], w = t-1;
  multiset<int> remain;
  remain.insert(0);
  REPCM(i, n-1, 0) {
    int a, b;
    tie(b, a) = c[i];
    if(dp[i][w-a] + b == v) {
      v -= b;
      w -= a;
    } else {
      remain.insert(b);
    }
  }
  int ans1 = dp[n-1][t-1] + c.back().first;
  int ans2 = dp[n][t-1] + (*(remain.rbegin()));
  cout << max(ans1, ans2) << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 39080
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE RankNTypes #-}
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Maybe
-- import Data.List
-- import qualified Data.Vector.Unboxed as VU
-- import qualified Data.Vector.Unboxed.Mutable as VUM
-- import Control.Monad
-- import Control.Monad.ST
-- import Debug.Trace
-- trace _ = id

solve :: String -> Bool
solve s = "keyence" `elem` ts
  where
    len = length s
    ts = [ take i s ++ drop j s | i <- [0..len], j <- [i..len] ]
    

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

tmain :: B.ByteString -> Bool
tmain cont =
  let remLines0 = map B.words (B.lines cont)
      [bs_s]:remLines1 = remLines0
      s = B.unpack bs_s
  in solve s

outAnswer :: Bool -> IO ()
outAnswer x = if x then putStrLn "YES" else putStrLn "NO"

main :: IO ()
main = outAnswer . tmain =<< B.getContents



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

typedef long long int ll;

int main()
{
    string s;
    ll q;
    cin >> s >> q;
    vector<pair<ll,char>> fc(q);
    vector<ll> t(q);
    for(ll i = 0;i < q;i++){
        cin >> t[i];
        if(t[i] == 2){
            cin >> fc[i].first >> fc[i].second;
        }
    }

    ll e = 2;
    string ans1, ans2;
    for(ll i = 0;i < q;i++){
        if(t[i] == 1){
            e++;
        }
        else{
            if(fc[i].first == 1){
                if(e % 2 == 0){
                    ans1 += fc[i].second;
                }
                else{
                    ans2 += fc[i].second;
                }
            }
            else{
                if(e % 2 == 1){
                    ans1 += fc[i].second;
                }
                else{
                    ans2 += fc[i].second;
                }
            }
        }
    }

    if(e % 2 == 0){
        for(ll i = ans1.size() - 1;i >= 0;i--){
            cout << ans1[i];
        }
        cout << s;
        cout << ans2;
    }
    else{
        for(ll i = ans2.size() - 1;i >= 0;i--){
            cout << ans2[i];
        }
        for(ll i = s.size() - 1;i >= 0;i--){
            cout << s[i];
        }
        cout << ans1;
    }

    return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0 ; i < (n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;
using p = pair<int, int>;

int main()
{
    int k;
    string s;
    cin >> k;
    cin >> s;

    if (k < size(s))
        cout << s.substr(0,k) << "..." << endl;
    else
        cout << s << endl;
    
    return 0;
}

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

int asc(const void *a, const void *b) {
  return *(int *)a - *(int *)b;
}

int main()
{
    int N,M,X,Y;
    scanf("%d%d%d%d",&N,&M,&X,&Y);

    int xi[110],yi[110];
    for(int i=0;i<N;i++)scanf("%d",&xi[i]);
    for(int i=0;i<M;i++)scanf("%d",&yi[i]);

    qsort(xi,N,sizeof(int),asc);
    qsort(yi,M,sizeof(int),asc);

    if( X < Y && xi[N-1] < yi[0] && X < yi[0] && Y > xi[N-1] ){
        printf("No War\n");
        return 0;
    }
    printf("War\n");

    return 0;
}

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

        #define ll long long
        #define pb push_back
        #define printV(v) for(int i=0;i<(int)v.size();i++){cout << v[i]<< " ";} cout << endl
        #define printRev(v) for(int i=(int)v.size()-1;i >= 0;i--){cout << v[i] << " ";} cout << endl
        #define sortV(v) sort(v.begin(),v.end())
        #define revV(v) reverse(v.begin(),v.end())
    

        ll a,b,c,d,e,f,g,n,m,k,t,x,h,w,p,q,y;
        string str = "";
        ll mod = 1e9 + 7;
        const int N = 3009;
       



        void solve(){
            cin >> n;
            ll answer = 1;
            for(int i=1; i<= n;i++){
                answer *= 10;
                answer %= mod;
            }
            answer += mod;
            ll newAns = 1;
            for(int i=1;i<=n;i++){
                newAns *= 9;
                newAns %= mod;
            }
            answer -= newAns;
            answer += mod;
            newAns = 1;
            for(int i=1;i<=n;i++){
                newAns *= 9;
                newAns %= mod;
            }
            answer -= newAns;
            answer = (answer + mod)% mod;
            newAns = 1;
            for(int i=1;i<=n;i++){
                newAns *= 8;
                newAns %= mod;
            }
            answer += newAns;
            answer = (answer + mod)% mod;




            
            cout << answer << endl;
        }

        


        int main(){
            ios_base::sync_with_stdio(false);

           

            int cases = 1;
            //cin >> cases;

            while(cases--) solve();
            return 0;

        }

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	vector<long long> B(N + 1, 0); //累積和テーブル
	int mod = 1000000007;
 
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		B[i + 1] = B[i] + A[i];
	}
 
	long ans = 0;
 
	//i について全探索する
	for (int i = 0; i < N; i++)
	{
		//累積和を使ってA[i+1] + ... + A[N] を求める
		long long sum = (B[N] - B[i + 1]) % mod;
 
		ans += A[i] * sum;
		ans %= mod;
	}
 
	cout << ans << endl;
}

Measured memory_bytes: 5576
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<typename T> using rev_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class S, class T> void map_init(map<S, T> &m, S k, T v){if(!m.count(k)) m[k] = v;}
void R_YESNO(bool p) { cout << (p ? "YES" : "NO") << endl; }
void R_YesNo(bool p) { cout << (p ? "Yes" : "No") << endl; }

void GetPrimes(int N, vector<int> &v) {
    v = vector<int>();
    int c = 1;
    while (c < N) {
        c++;
        bool flag = true;
        int d = (int)sqrt(c);
        for (int i = 0; i < v.size(); i++) {
            if (c % v[i] == 0) {
                flag = false;
                break;
            }
            if (d < v[i])
                break;
        }
        if (flag)
            v.push_back(c);
    }
}

// 75 = 3 * 5 * 5

int main() {
    int N;
    cin >> N;
    vector<int> p;
    GetPrimes(N, p);
    int M = p.size();
    vector<int> x(M, 0);
    i64 ans = 0;
    for(int n = 2; n <= N; n++) {
        int v = n;
        for(int i = 0; v && i < M; i++) {
            while(v % p[i] == 0) {
                v /= p[i];
                x[i]++;
            }
        }
    }
    i64 dp[100][2][3] = {0};
    dp[0][0][0] = 1;
    // 75 = 75, 3 * 25, 5 * 15, 3 * 5 * 5
    for(int i = 0; i < M; i++) {
        for(int a = 0; a < 2; a++) {
            for(int b = 0; b < 3; b++) {
                dp[i + 1][a][b] += dp[i][a][b];
                if(x[i] >= 3 - 1 && a + 1 < 2) {
                    dp[i + 1][a + 1][b] += dp[i][a][b];
                }
                if(x[i] >= 5 - 1 && b + 1 < 3) {
                    dp[i + 1][a][b + 1] += dp[i][a][b];
                }
                if(x[i] >= 15 - 1 && a + 1 < 2 && b + 1 < 3) {
                    dp[i + 1][a + 1][b + 1] += dp[i][a][b];
                }
                if(x[i] >= 25 - 1 && b + 2 < 3) {
                    dp[i + 1][a][b + 2] += dp[i][a][b];
                }
                if(x[i] >= 75 - 1 && a + 1 < 2 && b + 2 < 3) {
                    dp[i + 1][a + 1][b + 2] += dp[i][a][b];
                }
            }
        }
    }
    cout << dp[M][1][2] << endl;
    return 0;
}

Measured memory_bytes: 256
import java.nio.CharBuffer;
import java.util.Scanner;

class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Scanner sc) {
		String S = sc.next();
		int Q = sc.nextInt();
		int st = 1;
		StringBuilder head = new StringBuilder();
		StringBuilder tail = new StringBuilder();
		for (int i = 0; i < Q; i++) {
			int T = sc.nextInt();
			switch (T) {
				case 1: {
					st *= -1;
					break;
				}
				case 2: {
					int F = sc.nextInt();
					int f = (F * 2 - 3) * st;
					String C = sc.next();
					switch (f) {
						case -1: {
							head.append(C);
							break;
						}
						case 1: {
							tail.append(C);
						}
					}
				}
			}
		}
		head.reverse().append(S).append(tail);
		System.out.println((st > 0 ? head : head.reverse()).toString());
	}
}

class Main {
	public static void main(String... args) {
		Scanner in = new Scanner(System.in);

		Solver.INSTANCE.solve(in);

		in.close();
	}
}

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

static const int N = 1000;

int main(){
    int n,commandNum,a[N],b,c,d;
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> a[i];
    }
    cin >> commandNum;
    
    for(int i = 0;i < commandNum;++i){
        cin >> b >> c >> d;
        switch(b){
                // min
            case 0:
                cout << *min_element(a + c,a + d) << endl;
                break;
                // max
            case 1:
                cout << *max_element(a + c,a + d) << endl;
                break;
        }
    }
}


Measured memory_bytes: 3116
s = str(input())
t = str(input())
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for j in range(1, len(s)+1):
    for k in range(1, len(t)+1):
        if s[j-1] == t[k-1]:
            dp[j][k] = dp[j-1][k-1]+1
        else:
            dp[j][k] = max(dp[j-1][k], dp[j][k-1])

j = len(s)
k = len(t)
answer = ""
c = dp[len(s)][len(t)]
while c!=0:
    if s[j-1] == t[k-1]:
        answer += s[j-1]
        j -= 1
        k -= 1
        c = dp[j][k]
    elif dp[j][k] == dp[j-1][k]:
        j -= 1
    else:
        k -= 1
print(answer[::-1])

Measured memory_bytes: 112348
#include <bits/stdc++.h>
using namespace std;
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
const HASH B = 1e9 + 7;

int n, m;
int a[105], b[105];
int ans[105];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    rep(i, m) cin >> a[i];
    rep(i, m) {
        rep(j, n) {
            cin >> b[j];
            if (b[j] == a[i]) ans[j]++;
            else ans[a[i] - 1]++;
        }
    }
    rep(i, n) cout << ans[i] << endl;
}

Measured memory_bytes: 3144
import Control.Applicative
import Data.List 

main :: IO ()
main = do
    [a, _] <- map read . words <$> getLine
    ns <- map read . words <$> getLine
    putStrLn $ solve a ns
    
solve :: Int ->  [Int] -> String
solve a ns = if a <= (sum ns) then "Yes" else "No"

Measured memory_bytes: 45436
a = 0
while True:
    H, W = map(int, input(). split())
    if H == 0 and W == 0:
        break
    for j in range(1, H+1):
        for i in range(1, W+1):
            if i%2 == 0 and j%2 == 0 :
                print("#", end='')
            elif i%2 == 1 and j%2==1:
                print("#", end='')
            else:
                print(".", end='')
        print()
    print()    
    a += 1


Measured memory_bytes: 7000
let h, w, k = Scanf.scanf "%d %d %d\n" (fun h w k -> h, w, k)
let c = Array.init h (fun _ -> Scanf.scanf "%s\n" (fun s -> s))

let rec f0 i ans =
  if i = 1 lsl h then ans
  else
    let rec f1 j ans =
      if j = 1 lsl w then ans
      else
        let rec f2 h' black =
          if h' = h then black
          else
            let b = (i lsr h' land 1) = 0 in
            let rec f3 w' black =
              if w' = w then black
              else
                let b' = b && (j lsr w' land 1) = 0 && c.(h').[w'] = '#' in
                if b' then f3 (w' + 1) (black + 1)
                else f3 (w' + 1) black in
            let black = f3 0 black in
            f2 (h' + 1) black in
        let black = f2 0 0 in
        if black = k then f1 (j + 1) (ans + 1)
        else f1 (j + 1) ans in
    f0 (i + 1) (f1 0 ans)

let () =
  let ans = f0 0 0 in
  Printf.printf "%d\n" ans


Measured memory_bytes: 5368
card = {}

N = int(input())

for i in range(N):
    s = input()
    card.setdefault(s, 0)
    card[s] += 1

M = int(input())

for i in range(M):
    t = input()
    card.setdefault(t, 0)
    card[t] -= 1

print(max(0, max(x for x in card.values())))

Measured memory_bytes: 38256
use std::str::FromStr;
use std::fmt::Debug;

fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}


fn main(){
    let s: Vec<u16> = read_as_string().chars().map(|c| c as u16 -97).collect();
    let t: Vec<u16> = read_as_string().chars().map(|c| c as u16 -97).collect();

    let dummy: u16 = 255;
    let mut table = vec![dummy;26];
    let mut table2 = vec![dummy;26];
    for (&c1, &c2) in s.iter().zip(t.iter()){
        if table[c1 as usize] == dummy && table2[c2 as usize] == dummy{
            table[c1 as usize] = c2;
            table2[c2 as usize] = c1;
        }else if table[c1 as usize] != c2 || table2[c2 as usize] != c1{
            println!("No");
            return;
        }
    }
    println!("Yes");
    
}


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

//____________________________________________________________________________________________________________________________________

#define PI  2*acos(0.0)
#define pf  printf
#define sf  scan
#define ff  first
#define ss  second
#define mp  make_pair
#define pb  push_back
typedef long long ll;
typedef unsigned long long ull;
typedef std::vector<int> vi;
typedef vector<long long> vll ;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define sc(n)       scanf("%d",&n);
#define scf(f)      scanf("%f",&f);
#define FOR(i,a,n)  for(int i = a; i < n; i++)
#define TEST(test)  for(int cse = 1; cse <= test; cse++)
#define all(x) (x).begin(), (x).end()
#define fap(x) cout << __LINE__ << " says: " << #x << " = " << x << "\n"
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mst(arr, n) memset(arr, n, sizeof arr)
const ll INF = 2000000000000000000LL;
const int inf = 0x3f3f3f3f;
const long double EPS = 1e-9;
const ll MOD = 1e9 + 7;
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
//____________________________________________________________________________________________________________________________________
const int maxn = 1e5 + 8;
ll range, n, qsum[maxn];


ll f(vll &v, ll i, ll mx_brach)
{
   if(i > n) return 0;

   ll branch = mx_brach - v[i];
   
   if(branch < 0) return -1;

   range = qsum[i + 1];
   branch = min(branch, range);

   if( i == n) return v[i];
   ll sum = f(v, i + 1, branch * 2);

   if(sum == -1){
      return sum;
      }

   return branch + v[i] + sum;
}


int main()
{
#ifdef PARTHO
   freopen("C:\\Users\\rnoji\\Desktop\\Partho Code\\IO\\input.txt","r",stdin);
   freopen("C:\\Users\\rnoji\\Desktop\\Partho Code\\IO\\output.txt","w",stdout);
   int start_time = clock();
#endif
//FastIO

cin >> n;

vll v(n + 1);

for(auto &it : v) cin >> it;

qsum[n] = 0;
for(int i = n; i >= 0; i--)
   qsum[i] = v[i] + qsum[i + 1];

range = qsum[0];

ll sum = 0;

if(range == 0)sum = -1;
else sum = f(v, 0, 1);

cout << sum << endl;


#ifdef PARTHO
   int end_time = clock();
   printf("Time = %.4f\n",(end_time-start_time+0.0)/CLOCKS_PER_SEC);
#endif

    return 0;
}
///Before submit=>
///    *check for integer overflow,array bounds
///    *check for n=1







Measured memory_bytes: 8008
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <chrono>
#include <stack>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <tuple>
#include <iomanip>
#include <random>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod = 1e9 + 7;
void solve(){
    string a, b, s;
    int x, y;
    cin >> a >> b >> x >> y >> s;
    if(s == a) x--;
    else if(s == b) y--;
    cout << x << ' ' << y;
}
int main(){
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++){
        solve();
    }
}

Measured memory_bytes: 256
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lf else if

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=600000+19;

int s[N];
int n,sum;
char str[N];

void gao(){
	s[1]+=9;
	sum+=9;
	n++;
	For(i,1,n+1){
		if (s[i]>=10){
			sum+=s[i]/10;
			sum+=s[i]%10-s[i];
			s[i+1]+=s[i]/10;
			s[i]%=10;
		} else break;
	}
	while (n>1&&!s[n]) n--;
}

int main(){
	scanf("%s",str+1);
	n=strlen(str+1);
	For(i,1,n+1){
		s[i]=str[n-i+1]-'0';
	}
	n++;
	For(i,1,n+1) s[i]*=9;
	For(i,1,n+1){
		s[i+1]+=s[i]/10;
		s[i]%=10;
		sum+=s[i];
	}
	for (int k=1;;k++){
		gao();
		if (sum<=9*k){
			printf("%d\n",k);
			return 0;
		}
	}
}

Measured memory_bytes: 2816
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        long a[] = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(sc.next());
        }
        sc.close();
        long sum = Arrays.stream(a).sum();
        long min = Long.MAX_VALUE;
        long x = 0;
        for (int i = 0; i < n - 1; i++) {
            x += a[i];
            if (min > Math.abs(sum - x - x))
                min = Math.abs(sum - x - x);
        }
        System.out.println(min);
    }
}

Measured memory_bytes: 51008
program A177
    implicit none
    integer(8) :: D, T, S
    real(8) :: dr, tr, sr

    read(5,*) D, T, S
    dr = real(D)
    tr = real(T)
    sr = real(S)

    if (dr/sr <= tr) then
        write(6,*) "Yes"
    else
        write(6,*) "No"
    end if    
end program A177


Measured memory_bytes: 2856
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N=105;
int hx[N<<1];

inline int nxi(){
	int x=0;
	char c;
	while((c=getchar())>'9'||c<'0');
	while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
	return x;
}

int main(){
#ifndef ONLINE_JUDGE
//	freopen("a.in","r",stdin);
#endif
	int n=nxi(),ans=0;
	for(int i=1;i<=n<<1;++i){
		hx[i]=nxi();
	}
	std::sort(hx+1,hx+(n<<1)+1);
	for(int i=1;i<n<<1;i+=2){
		ans+=hx[i];
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int, int> P;
typedef long long ll;

int main(){
    int n, m; cin >> n >> m;
    ll sum = 0;
    vector<int> a(n); 
    rep(i,n){
        cin >> a[i];
        sum += a[i];
    }

    sort(all(a));
    reverse(all(a));

    if(4 *m*a[m-1] >=sum) cout << "Yes" <<endl;
    else cout << "No" << endl;
}

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

int main(){
    string s; cin >> s;
    int k; cin >> k;
    string cur;
    map<string,int> m;
    int n = s.size();
    for(int i = 0; i < n; i++){
        cur = "";
        for(int j = i; j < i + k && j < n; j++){
            cur += s[j];
            m[cur]++;
        }
    }
    auto p = m.begin();
    rep(i,k-1) p++;
    cout << p->first << endl;
}

Measured memory_bytes: 1920
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
typedef vector<P> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
const int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30);
const int INF = (1LL << 60);
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}



signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    int n,k;
    cin>>n>>k;
    int ans=0;
    while(n!=0){
        ans++;
        n/=k;
    }
    cout<<ans<<endl;
    
}

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

int main(){
  int h,w;
  cin>>h>>w;
  vector<vector<char>> a(h+1,vector<char>(w+1));
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++)cin>>a[i][j];
    a[i][w]='.';
  }
  for(int i=0; i<w+1; i++)a[h][i]='.';

  bool ans=true;
  int i=0, j=0;
  a[i][j]='.';
  while(i!=h-1 || j!=w-1){
    if(a[i+1][j]==a[i][j+1]){
      ans=false;
      break;
    }else if(a[i+1][j]=='#'){
      a[i+1][j]='.';
      i++;
    }else if(a[i][j+1]=='#'){
      a[i][j+1]='.';
      j++;
    }
  }
  a[i][j]='.';

  for(i=0; i<h; i++){
    for(j=0; j<w; j++){
      if(a[i][j]=='#'){
        ans=false;
        break;
      }
    }
  }
  
  if(ans)cout<<"Possible"<<endl;
  else cout<<"Impossible"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <math.h>
#include <stack>
#include <cctype>
using namespace std;
#define int long long
#define pi 2*acos(0.0)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)

signed main()
{
	string o, e;
	cin >> o;
	cin >> e;
	REP(i, e.length()){
		cout << o[i];
		cout << e[i];
	}
	if (o.length() != e.length()) cout << o[o.length() - 1];
	cout << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

pair<int, int> p[3];
int d[5];

int main(){
	for(int i=0; i<3; i++){
		scanf("%d %d", &p[i].first, &p[i].second);
		d[p[i].first]++; d[p[i].second]++;
	}
	int cnt1=0, cnt2=0;
	for(int i=1; i<=4; i++){
		if(d[i]==1)	cnt1++;
		else if(d[i]==2)	cnt2++;
	}
	if(cnt1==2 && cnt2==2)	printf("YES");
	else	printf("NO");
	return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int n;
  cin >> n;
  vector<LL> a(n+1);
  for(int i=1;i<=n;i++) cin >> a[i];
  for(int i=1;i<=n;i++) a[i]+=a[i-1];
  LL ans=LINF;
  for(int i=2;i<=n-2;i++){
    int p=distance(a.begin(),lower_bound(a.begin(),a.begin()+i,a[i]/2));
    int q=distance(a.begin(),lower_bound(a.begin()+i,a.end(),(a[n]+a[i])/2));
    for(int x=p-1;x<=p+1;x++){
      for(int y=q-1;y<=q+1;y++){
        ans=min(ans,max(max(a[x],a[i]-a[x]),max(a[y]-a[i],a[n]-a[y]))
        -min(min(a[x],a[i]-a[x]),min(a[y]-a[i],a[n]-a[y])));
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    cin >> s >> t;
    for(int i = 0;i < s.size();i++)
    {
        bool flag = true;
        for(int j = 0;j < s.size();j++)
        {
            if(s[(i + j) % s.size()] != t[j])
            {
                flag = false;
                break;
            }
        }
        if(flag)
        {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int i,j,n,m,a[1000],s,s1;

  while(1)
    {
      scanf("%d",&n);
      scanf("%d",&m);
      if(n==0&&m==0){
          break;
      }
      for(i=0;i<=n-1;i++){
	  scanf("%d",&a[i]);
	}
      s1=0;
      for(i=0;i<=n-1;i++){
	  for(j=i+1;j<=n-1;j++){
	      s=a[i]+a[j];
	      if(s<=m && s1<s) s1=s;
	    }
	}
      if(s1==0) printf("NONE\n");
      else printf("%d\n",s1);
    }
  return 0;
}


Measured memory_bytes: 2104
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, m = na()

zs = []
for i in range(n):
    zs.append(na())

ans = 0
if m == 0:
    print(0)
else:
    for u in (-1, 1):
        for v in (-1, 1):
            for w in (-1, 1):
                vs = []
                for z in zs:
                    vs.append(z[0]*u+z[1]*v+z[2]*w)
                vs.sort()
                ans = max(ans, sum(vs[-m:]))

    print(ans)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
        ll llimit=-1000,ulimit=1000;
        ll x; cin>>x;
        unordered_map<ll,ll> a;
        auto compute=[&](ll y) { return y*y*y*y*y; };
        for(int i=llimit;i<=ulimit;i++){
                a[i]=compute(i);
        }
        for(int i=llimit+1;i<=ulimit;i++){
                for(int j=llimit;j<i;j++){
                        if(a[i]-a[j]==x){ cout<<i<<" "<<j<<endl; return 0; }
                }
        }
}


Measured memory_bytes: 3708
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/algorithm_ext.hpp>
#include <boost/math/common_factor_rt.hpp>
using namespace std;
using namespace boost::range;
using boost::irange;
using boost::math::gcd;
using boost::math::lcm;

using ll = int64_t;
constexpr char LN = '\n';
template<class T> bool chmax(T& a, const T& b) {if(a<b){a=b;return true;}else{return false;}}
template<class T> bool chmin(T& a, const T& b) {if(b<a){a=b;return true;}else{return false;}}

#ifdef LOCAL
template<class H> void dump_(const char* s, H h) {cout<<s<<"="<<h<<LN; }
template<class H, class... T> void dump_(const char* s, H h, T... t) {for(;*s!=',';++s){cout<<*s;}cout<<"="<<h<<",";dump_(++s,t...);}
#define dump(...) dump_(#__VA_ARGS__, __VA_ARGS__)
#else
#define dump(...)
#endif

struct init_ {init_(){cin.tie(nullptr);ios::sync_with_stdio(false);}} init_;

template<class C> C scan(size_t n) {C c(n);for(auto& v:c){cin>>v;}return c;}
template<class C> C scan(size_t n, size_t m) {C vss(n);for(auto& vs:vss){vs.resize(m);for(auto& v:vs){cin>>v;}}return vss;}

template<class R> struct Joined { const R& r; const char* s; };
template<class R> Joined<R> joined(const R& r, const char* s = " ") {return{r,s};}
template<class R> ostream& operator<<(ostream& out, Joined<R> j) {bool f=true;for(const auto& v:j.r){if(f){f=false;}else{out<<j.s;}out<<v;}return out;}

template<class T> using matrix = vector<vector<T>>;
template<class T> matrix<T> make_matrix(size_t n, size_t m, const T& init = T()) {matrix<T> vss(n);for(auto& vs:vss){vs.resize(m,init);}return vss;}
template<class T> ostream& operator<<(ostream& out, Joined<matrix<T>> j) {bool a=true;for(const auto& vs:j.r){if(a){a=false;}else{out<<LN;}bool f=true;for(const auto& v:vs){if(f){f=false;}else{out<<j.s;}out << v;}}return out;}

template<class T> void show_(const T& t) {cout<<t;}
template<class T> void show_(const vector<T>& v) {cout<<joined(v);}
void show_(bool b) {cout<<(b?"Yes":"No");}
void show_(double d) {cout<<fixed<<setprecision(12)<<d;}
template<class T, class... TS> void show_(const T& t, TS... ts) {show_(t);cout<<' ';show_(ts...);}
template<class T> void show(const T& t) {show_(t);cout<<LN;}
template<class T, class... TS> void show(const T& t, TS... ts) {show_(t, ts...);cout<<LN;}

int main() {
    ll K, N;
    cin >> K >> N;
    auto A = scan<vector<ll>>(N);
    ll maxdiff = 0;
    for (auto i : irange(0l, N-1)) {
        chmax(maxdiff, A[i+1]- A[i]);
    }
    chmax(maxdiff, K - A[N-1] + A[0]);
    show(K - maxdiff);
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    int Z;           //入力待ち
    int i, j, k;     //for文用
    string to = ","; //デバッグ用
    int e_count = 0; //演算回数を数える
    int count = 0;   //よくあるカウント
    //-----------

    long long L, R; //最大2x10^9//ギリintはいるが，演算した結果に影響するので大きく取る
    cin >> L >> R;

    int min = 2019;
    int mod = 2019;
    for (; L < R; L++)
    {
        if (R - L >= 2019)
            min = 0;

        for (i = 0; i < R - L; i++)
        {
            //cout << L << to << (L + i + 1) << endl;
            //cout << "e=" << e_count++ << endl;
            //cout << (1000000000LL * (1000000000LL + 1)) % 2019LL << endl;
            //cout << 1000000001000000000 << endl;
            //cout << 1000000001000000000 % 2019 << endl;

            if (min == 0)
            {
                break;
            }
            mod = (L * (L + i + 1)) % 2019;
            //cout << L << to << i << to << (L + i + 1) << to << L * (L + i + 1) % 2019LL << endl;
            //cout << "割ったあまりは" << mod << endl;
            min = min > mod ? mod : min;
            //cout << min << to << mod << endl;
        }
        //cout << to << endl;
        if (min == 0)
            break;
    }

    cout << min << endl;

    //-----------
    cin >>
        Z;
    return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(input().split())
if n==1:
  print(a[0])
  exit()
bl=[a[-1]]
br=[a[-2]]
for i in range(2,n):
  if i%2==0:
    bl.append(a[-1-i])
  else:
    br.append(a[-1-i])
m=len(br)
br=[br[-i-1] for i in range(m)]
bl[len(bl):len(bl)]=br
print(' '.join(bl))


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

using namespace std;

#define int long long

#ifndef bhupixb
    #define var(...)
    #define stl(...)
#endif

#define single_test


constexpr int mod = 998244353;

struct M {
    unsigned v;
    M(long long a = 0) : v((a %= mod) < 0 ? a + mod : a) {}
    M& operator+=(M r) { if ((v += r.v) >= mod) v -= mod; return *this; }
    M& operator-=(M r) { if ((v += mod - r.v) >= mod) v -= mod; return *this; }
    M& operator*=(M r) { v = (uint64_t)v * r.v % mod; return *this; }
};

uint32_t add(M a, M b) { return (a += b).v; }
uint32_t mul(M a, M b) { return (a *= b).v; }
uint32_t sub(M a, M b) { return (a -= b).v; }

const int N = 4e5 + 3;

M lazy[N << 2];
M tree[N << 2];

struct segtree { // with lazy propagation
  M combine(M a, M b) {
    return add(a, b);
  }
  void prop(int l, int r, int x) {
    if(lazy[x].v) {
      tree[x] += lazy[x];
      if(l ^ r) {
        int lc = x + x, rc = lc + 1;
        lazy[lc] += lazy[x];
        lazy[rc] += lazy[x];
      }
      lazy[x] = 0;
    }
  }
  void update(int l, int r, int ql, int qr, M val, int x) {
    prop(l, r, x);
    if(qr < l || r < ql) {
      return;
    }
    if(ql <= l && r <= qr) {
      lazy[x] = val;
      prop(l, r, x);
      return;
    }
    int mid = l + r >> 1, lc = x + x, rc = lc + 1;

    update(l, mid, ql, qr, val, lc);
    update(mid + 1, r, ql, qr, val, rc);

    tree[x] = combine(tree[lc], tree[rc]);
  }
  M query(int l, int r, int ql, int qr, int x) {
    prop(l, r, x);
    if(qr < l || r < ql) {
      return 0;
    }
    if(ql <= l and r <= qr) {
      prop(l, r, x);
      return tree[x];
    }
    int mid = l + r >> 1, lc = x + x, rc = lc + 1;

    return combine(query(l, mid, ql, qr, lc), query(mid + 1, r, ql, qr, rc));
  }
};


void solve() {
    int n, k;

    cin >> n >> k;
    vector<pair<int,int>> q(k);
    for (auto &[x, y] : q) {
        cin >> x >> y;
    }
    segtree ins;
    const int N = ::N - 1;
    ins.update(1, N, 1, 1, 1, 1);
    for (int i = 1; i < n; ++i) {
        M cur = ins.query(1, N, i, i, 1);
        for (auto [l, r]: q) {
            l += i;
            r += i;
            ins.update(1, N, l, r, cur, 1);
        }
    }
    cout << ins.query(1, N, n, n, 1).v << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    #ifndef single_test
        cin >> t;
    #endif
    for (int i = 1; i <= t; ++i) {
        // cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

Measured memory_bytes: 16160
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.next());
        HashMap<Integer, Integer> map = new HashMap<>();
        int a;
        for(int i = 0; i < n; i++){
            a = Integer.parseInt(sc.next());
            map.put(a, map.getOrDefault(a, 0)+1);
        }
        
        String ans = "No";
        if(map.size() == 1 && map.containsKey(0)){
            ans = "Yes";
        }else if(n%3 == 0){
            if(map.size() == 2 && map.getOrDefault(0, -1) == n/3){
                ans = "Yes";
            }else if(map.size() == 3){
                List<Integer> list = new ArrayList<>(map.keySet());
                if(map.get(list.get(0)) == n/3 && map.get(list.get(1)) == n/3 && map.get(list.get(2)) == n/3){
                    int x = list.get(0) ^ list.get(1) ^ list.get(2);
                    if(x == 0){
                        ans = "Yes";
                    }
                }
            }
        }
        
        System.out.println(ans);
    }
}

Measured memory_bytes: 48140
p =list(map(int, input().split()))
a = p[0]
b = p[1]
c = p[2]
d = p[3]
while True:
    c = c - b
    if c <= 0:
        print("Yes")
        exit()
    a = a - d
    if a <=0:
        print("No")
        exit()

Measured memory_bytes: 9184
#include <iostream>
#include <math.h>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cstdlib>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <limits.h>
#include <utility>
#include <stack>

using namespace std;

#define fs first
#define sc second

typedef long long ll;
typedef pair<ll, ll> P;

int main(){
    ll N, K, a[101000], b[101000];
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> a[i] >> b[i];
    }

    ll res = 0;
    for(int i = 29; i >= 0; i--){
        if((K >> i) % 2 == 0){
            continue;
        }
        ll K2 = ((K >> (i+1)) << 1);   // 上位桁
        ll resTmp = 0;
        for(int j = 0; j < N; j++){
            if((K2 | (a[j] >> i)) == K2){
                resTmp += b[j];
            }
        }
        res = max(res, resTmp);
    }
    ll resTmp = 0;
    for(int j = 0; j < N; j++){
        if((K | a[j]) == K){
            resTmp += b[j];
        }
    }
    res = max(res, resTmp);
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
typedef long long ll;
const ll MOD=1000000007;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }

int main(void){
    // Your code here!
    int n,k; cin >> n >> k;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    sort(p.begin(),p.end());
    ll ans = 0;
    rep(i,k) ans+= p[i];
    cout << ans << endl;
}


Measured memory_bytes: 3632
#ifndef DEBUG
#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i <= i##_len; ++i)
#define rep3(i, l, r) for (int i = l, i##_len = (r); i < i##_len; ++i)
#define REP3(i, l, r) for (int i = l, i##_len = (r); i <= i##_len; ++i)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const Ld pi = M_PI;
const Int MOD = 1000000007;
const Int INF = 1LL << 62;

class UnionFind {
private:
    vector<Int> _par, _siz;

public:
    UnionFind(Int sz) : _par(sz), _siz(sz, 1LL) {
        for (Int i = 0; i < sz; i++) {
            _par[i] = i;
        }
    }

    Int root(Int x) {
        while (_par[x] != x) {
            x = _par[x] = _par[_par[x]];
        }
        return x;
    }

    bool merge(Int x, Int y) {
        x = root(x);
        y = root(y);
        if (x == y) {
            return false;
        }

        if (_siz[x] < _siz[y]) {
            swap(x, y);
        }
        _siz[x] += _siz[y];
        _par[y] = x;

        return true;
    }

    bool issame(Int x, Int y) {
        return root(x) == root(y);
    }

    Int size(Int x) {
        return _siz[root(x)];
    }

    ~UnionFind(){};
};

Int Floor(Int a, Int b) {
    return (a - (a % b)) / b;
}

template <class T>
inline bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

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

    Int n, m;
    cin >> n >> m;

    UnionFind UF(n);

    for (Int i = 0; i < m; i++) {
        Int a, b;
        cin >> a >> b;
        a--;
        b--;

        UF.merge(a, b);
    }

    Int ans = 0;
    for (Int i = 0; i < n; i++) {
        chmax(ans, UF.size(i));
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6364