akhauriyash/Code-Regression huggingface dataset:
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
void swap(int A[], int i, int j) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
int partition(int A[], int p, int r) {
    int x = A[r];
    int i = p - 1;
    for(int j = p; j < r; j++) {
        if(A[j] <= x) {
            i++;
            swap(A, i, j);
        }
    }
    i++;
    swap(A, i, r);
    return i;
}
int main() {
    int n;
    cin >> n;
    int A[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    int r = partition(A, 0, n - 1);
    for(int i = 0; i < n; i++) {
        if(i >= 1)
            printf(" ");
        if(r != i) {
            printf("%d", A[i]);
        }else{
            printf("[%d]",A[i]);
        }
    }
    cout << endl;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

int N,M;
int A[5555],B[5555];

int latte(int s){
        UnionFindTree uf(N);
        rep(i,M){
            if(i==s)continue;
            uf.unite(A[i],B[i]);
        }

        return uf.size(0)!=N;
}

signed main(){
    cin>>N>>M;
    rep(i,M)cin>>A[i]>>B[i],A[i]--,B[i]--;

    int cnt=0;
    rep(i,M)cnt+=latte(i);
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
using namespace std;

#define ll long long
#define INF (1 << 30)
#define INFLL (1LL << 60)

#define FOR(i,a,b) for(ll i = (a);i<(b);i++)
#define REP(i,a) FOR(i,0,(a))
#define MP make_pair

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

	bool flag = false;
	int c1, c2, c3;
	for(int i = 0;i <= 100;i++){
		c1 = c[0][0] - i;
		c2 = c[0][1] - i;
		c3 = c[0][2] - i;
		if(c1 < 0 || c2 < 0 || c3 < 0) continue;

		for(int j = 0;j <= 100;j++){
			if(c[1][0] - j != c1) continue;
			if(c[1][1] - j != c2) continue;
			if(c[1][2] - j != c3) continue;
			for(int k = 0;k <= 100;k++){
				if(c[2][0] - k != c1) continue;
				if(c[2][1] - k != c2) continue;
				if(c[2][2] - k != c3) continue;
				flag = true;
			}
		}
	}

	if(flag) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct _OMAZINAI_ { _OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } __omazinai_instance__;
#define INF ((1LL<<61) + (1<<29))
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
ll my_gcd(ll a, ll b) { return b ? my_gcd(b, a%b) : a; };
void _INPUT_IMPL_() {};
template <class T, class... Args> void _INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; _INPUT_IMPL_(args...); }
void _OUTPUT_IMPL_() {};
template <class T, class... Args> void _OUTPUT_IMPL_(T dest, Args... args) { cout << dest << (sizeof...(Args) ? " " : ""); _OUTPUT_IMPL_(args...); }
#define in(type, ...) type __VA_ARGS__; _INPUT_IMPL_(__VA_ARGS__)
#define in_v(type, name, cnt) vector<type> name(cnt); loop(i, cnt) cin >> name[i];
#define sort_v(v) std::sort(v.begin(), v.end())
#define unique_v(v) v.erase(std::unique(v.begin(), v.end()), v.end()) //必ずソート後に実行
#define out(...) (_OUTPUT_IMPL_(__VA_ARGS__), std::cout<<std::endl)
#define set_fix(x) ((std::cerr<<std::fixed<<std::setprecision(x)),(std::cout<<std::fixed<<std::setprecision(x)))
//小さい方に寄る
#define space_op(x, y, a, b, c) ([](auto x_, auto y_, auto a_, auto b_, auto c_){if(x_<y_)return a_;if(x_>y_)return c_;return b_;}(x,y,a,b,c))
#define space_out(x, y, a, b, c) out(space_op(x, y, a, b, c))

// ^^^ Template ^^^ //


int main() {
	bool ans = true;
	in(ll, N);
	vector<ll> t(N+1, 0), x(N+1, 0), y(N+1, 0);
	loop(i, N)
		cin >> t[i+1] >> x[i+1] >> y[i+1];
	loop(i, N) {
		ll om = (t[i + 1] - t[i]) - (abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]));
		ans = ans && om >= 0 && !(om & 1);
	}
	YesNo(ans);
	return 0;
}


Measured memory_bytes: 2560
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length() + 1; i++) {
            sb.append("z");
        }
        String ans = sb.toString();
        for(int i = 0; i <= s.length() - t.length(); i++) {
            String subStr = s.substring(i, i+t.length());
            String candidate = (s.substring(0, i) + t + s.substring(i + t.length(), s.length())).replaceAll("\\?", "a");
            if (check(subStr, t) && isUpperDictOrder(ans, candidate)) {
                ans = candidate;
            }
        }
        if(ans.length() == s.length() + 1) {
            System.out.println("UNRESTORABLE");
        } else {
            System.out.println(ans);
        }
    }
    private static boolean check(String subStr, String t) {
        int index = 0;
        while (index < t.length()) {
            if (subStr.charAt(index) != '?' && subStr.charAt(index) != t.charAt(index)) return false;
            index++;
        }
        return true;
    }
    private static boolean isUpperDictOrder(String ans, String candidate) {
        int index = 0;
        while(index < ans.length()) {
            if(ans.charAt(index) > candidate.charAt(index)) return true;
            index++;
        }
        return false;
    }
}



Measured memory_bytes: 25172
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;

int main() {
    int N, K;
    cin >> N >> K;

    if (K == 1) {
        cout << 0 << endl;
    } else if (N > K) {
        cout << N - K << endl;
    } else if(N == K){
        cout << 0 << endl;
    }else {
        cout << 1 << endl;
    }
}


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

int main(){
    int a, b;
    cin >> a >> b;
    int p = a + b;
    int s = a - b;
    int m = a * b;
    int ans = max({p, s, m});
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int n, a, b, c;
vector<int> l;

int solve (int ind, int A, int B, int C) {
    if (ind == n) {
        if (min({A, B, C}) <= 0) return INF;
        else return abs(a-A)+abs(b-B)+abs(c-C);
    }
    vector<int> ret(4);
    ret[0] = solve(ind+1, A+l[ind],B, C)+(A==0 ? 0:10);
    ret[1] = solve(ind+1, A, B+l[ind], C)+(B==0 ? 0:10);
    ret[2] = solve(ind+1, A, B, C+l[ind])+(C==0 ? 0:10);
    ret[3] = solve(ind+1, A, B, C);
    return (*min_element(ret.begin(), ret.end()));
}

int main(int argc, char const *argv[]) {
    cin >> n >> a >> b >> c;
    l.resize(n);
    REP(i,n) {
        cin >> l[i];
    }
    int ans = solve(0, 0, 0, 0);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int result = (n-1) * (m-1);

        System.out.println(result);
    }
}


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

int main() {
  char x;
  cin >> x;
  if(x == 'A')cout << "T";
  if(x == 'T')cout << "A";
  if(x == 'G')cout << "C";
  if(x == 'C')cout << "G";
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define ll long long
#define ld long double
#define vi vector<long long>
#define mkp make_pair
#define sz(x) (int)x.size()
#define pi pair<long long, long long>
#define watch(x) cout << (#x) << " is " << (x) << endl; cout.flush()
#define endl '\n'
#define _ << ' '
#define min3(a, b, c) min(a, min(b, c))
#define min4(a, b, c, d) min(min(a, d), min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define max4(a, b, c, d) max(max(a, d), max(b, c))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> idxset;
//find_by_order(i) : iterator to the value at index i, order_of_key(x) : the index of value x
const ll mod = (ll)1e9+7;
const ll INF = (ll)1e18+1;



int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
   // freopen("A.txt", "r", stdin);
    #endif
    ll x, y, ans=1;
    cin >> x >> y;
    while(x*2<=y)
    {
        x*=2;
        ans++;
    }
    cout << ans;
}



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

int main(){
    int h,w,k;
    cin >> h >> w >> k;
    char c[h][w];
    for(ll i=0;i<h;i++){
        for(ll j=0;j<w;j++){
            cin >> c[i][j];
        }
    }
    int res=0;
    for(int bit1=0;bit1<(1<<h);bit1++){
        for(int bit2=0;bit2<(1<<w);bit2++){
            char d[h][w];
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    d[i][j]=c[i][j];
                }
            }
            for(int i=0;i<h;i++){
                if(bit1&(1<<i)){
                    for(int j=0;j<w;j++){
                        d[i][j]='.';
                    }
                }
            }
            for(int j=0;j<w;j++){
                if(bit2&(1<<j)){
                    for(int i=0;i<h;i++){
                        d[i][j]='.';
                    }
                }
            }
            int count=0;
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(d[i][j]=='#') count++;
                }
            }
            if(count==k) res++;
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3616
#include<iostream>

using namespace std;

int main(){
    int a,b,c,x;
    cin>>a>>b>>c>>x;

    int ans=0;
    for(int i=0;i<=a;++i){
        for(int j=0;j<=b;++j){
            for(int k=0;k<=c;++k){
                if(500*i+100*j+50*k==x) ++ans;
            }
        }
    }       
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		int happiness = 0;

		if (0 < (x / 500) ) {
			happiness += 1000 * (x / 500);
			x = x % 500;
		}
		if (0 < (x / 5)) {
			happiness += 5 * (x / 5);
			x = x % 5;
		}

		System.out.println(happiness);

		scan.close();
	}

}


Measured memory_bytes: 21716
main :: IO ()
main = do
    s <- getLine
    print $ solve s

solve :: String -> Int
solve cs = snd $ foldl f (0, 0) cs
  where
    f (d, x) 'S'             = (succ d, succ x)
    f (d, x) 'T' | d == 0    = (     d, succ x)
                 | otherwise = (pred d, pred x)


Measured memory_bytes: 15100
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
 
var myOut = main();
console.log(String(myOut));
 
function main(){
  var n = next();
  var ans = n * (n+1) * (n+2) / 6;
  for(var i = 1; i < n; i++){
    var u = next(), v = next();
    if(u > v){var temp = u; u = v; v = temp;}
    ans -= u * (n-v+1);
  }
  return ans;
}


Measured memory_bytes: 61516
#include<bits/stdc++.h>
using namespace std;
char s[15];
int cnt;
int main()
{
    cin>>s;
    for(int i=0;i<strlen(s);i++)
    {
        if(s[i]=='x')
        {
            cnt++;        
        }
    }
    if(cnt>7)
    {
        cout<<"NO";
        return 0;
    }
    cout<<"YES";
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define _ 0
#define int long long
#define INF 0x7fffffff
#define re register
#define drep(i ,l ,r) for(re int i = (r) ; i >= (l) ; -- i)
#define rep(i ,l ,r) for(re int i = l ; i <= r ; ++ i)
#define Next(u ,i) for(re int i = head[u] ; i ; i = e[i].next)
int n;
int read() {
    char cc = getchar() ; int cn = 0 ,flus = 1;
    while(cc < '0' || cc > '9') {if(cc == '-') flus = - flus ; cc = getchar();}
    while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0' ,cc = getchar();
    return flus * cn;
}
int a, b, c, d;
signed main() {
    a = read() ,b = read() ,c = read() ,d = read();
    if(c * b <= 0 && c * a <= 0 && b * d <= 0 && a * d <= 0) {
		if(!(a * b * c * d)) puts("0");
		else if(a > 0) printf("%lld" ,a * d);
		else printf("%lld" ,b * c);
    }
    else printf("%lld" ,std :: max(std :: max(a * c, a * d), std :: max(b * c, b * d)));
    return ~~(0^_^0);
}

Measured memory_bytes: 1596
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef int ll;

int main(){
    ll N, Q,a,b,point, x;
    cin >>N>>Q;
    vector<vector<ll>> G(N);
    vector<ll> cost(N);
    REP(i,N-1){
        cin >> a >> b; G[a-1].push_back(b-1); G[b-1].push_back(a-1);
    }
    REP(i,Q){
        cin >> point >> x; cost[point-1] += x; 
    }
    stack<ll> s;
    vector<bool> closed;
  	closed.assign(N, false);
    s.push(0);
    ll vertex;
    while(s.empty() != 1){
        vertex = s.top();
        s.pop();
        closed[vertex] = true;
        for(auto v: G[vertex]){
            if (closed[v]) continue;
            s.push(v);
            cost[v] += cost[vertex];
        }     
    }
    for(auto i : cost) cout << i << " ";
    return 0;
 }




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

#define infi            2e9
#define infl            5e18
#define MX              100005
#define pi              2*acos(0.0)
#define ll              long long int
#define rr              read()
#define ff              first
#define ss              second
#define pb              push_back
#define pii             pair<int,int>
#define ms(a,b)         memset(a, b, sizeof(a))
#define loop(i,n)       for(register int i=0;i<n;i++)
#define pool(i,n)       for(register int i=n-1;i>=0;i--)
#define loop1(i,n)      for(register int i=1;i<=n;i++)
#define pool1(i,n)      for(register int i=n;i>0;i--)

using namespace std;

inline ll read(){char c=getchar();ll num,sign=1;for(;c<'0'||c>'9';c=getchar())if(c=='-')sign=-1;for(num=0;c>='0'&&c<='9';){c-='0';num=num*10+c;c=getchar();}return num*sign;}
// inline ll pw(ll b, ll p){ll ans=1;while(p>0){if(p&1)ans*=b;p>>=1;b*=b;}return ans;}
// inline bool isPrime(ll n){if(n==1)return false;if(n==2)return true;if(!(n%2))return false;for(ll i=3;i<=sqrt(n);i+=2)if(!(n%i))return false;return true;}
// inline ll gcd(ll a, ll b){if(a==0)return b;return gcd(b%a,a);}

// //*************************************  Bitmask Opereations  **********************************//
// int Set(int N,int pos){return N=N | (1<<pos);}
// int reset(int N,int pos){return N= N & ~(1<<pos);}
// bool check(int N,int pos){return (bool)(N & (1<<pos));}
// //********************************************************************************************//


int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    //#ifdef rid.dle
    //freopen("in.txt", "r", stdin);
    //#endif
    
    ll n=rr,d=rr;

    d=(d*2LL)+1LL;

    ll ans=n/d + (n%d==0?0:1);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import sys
n = int(input())
s1 = input()
s2 = input()
MOD = 10**9 + 7

if n == 1:
    print(3)
    sys.exit()

dp = [0] * n
dp[0] = 3 if s1[0] == s2[0] else 6

for i in range(1, n):
    # 横に並んでいる場合は増えない
    if s1[i - 1] == s1[i]:
        dp[i] = dp[i - 1]
        continue
    # 前回縦に並んでいたなら2色から選べる
    if s1[i - 1] == s2[i - 1]:
        dp[i] = dp[i - 1] * 2 % MOD
    # 前回が縦でなく、RGの組み合わせÎならG-B, G-R, B-Rの3通りが選べる
    elif s1[i] != s2[i]:
        dp[i] = dp[i - 1] * 3 % MOD
    else:
        dp[i] = dp[i - 1]

print(dp[-1])

Measured memory_bytes: 9180
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

type pair struct {
	fi int
	se int
}

func convination(n int, k int) int {
	if k < 0 || n < k {
		return 0
	}
	var ret = 1
	for i := 1; i <= k; i++ {
		ret *= n
		ret /= i
		n--
	}
	return ret
}
func modconvination(n int, k int) int {
	if k < 0 || n < k {
		return 0
	}
	var ret = 1
	for i := 1; i <= k; i++ {
		ret *= n
		ret %= mod
		ret = inverseDiv(ret, i)
		n--
	}
	return ret
}
func inverseDiv(a int, b int) int {
	return a * modinv(b, mod) % mod
}

func modinv(a int, m int) int {
	b := m
	u := 1
	v := 0
	for {
		if b == 0 {
			break
		}
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= m
	if u < 0 {
		u += m
	}
	return u
}

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	//予備
	x := iScan()
	y := iScan()
	if (x+y)%3 != 0 || x > 2*y || y > 2*x {
		fmt.Println(0)
		return
	}
	n := (x + y) / 3
	r := x - n
	fmt.Println(modconvination(n, r))
}


Measured memory_bytes: 1792
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <iostream>
#include <locale>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

string solve(int n) {
    // string ans;
    vector<vector<int>> treasurePosition(n, vector<int>(2));
    int move;

    for (int i = 0; i < n; i++) {
        cin >> treasurePosition[i][0] >> treasurePosition[i][1];
    }
    cin >> move;
    int cast[move];
    vector<string> movedirection(move);
    for (int i = 0; i < move; i++) {
        cin >> movedirection[i];
        cin >> cast[i];
        //cout << cast[i] << " " << endl;
    }
    int xPosition = 10;
    int yPosition = 10;
    int count     = 0;
    for (int i = 0; i < move; i++) {
        for (int k = 0; k < cast[i]; k++) {
            // int cast = (int)movedirection[i][1];
            if (movedirection[i][0] == 'N') {
                yPosition++;
            } else if (movedirection[i][0] == 'E') {
                xPosition++;
            } else if (movedirection[i][0] == 'S') {
                yPosition--;
            } else if (movedirection[i][0] == 'W') {
                xPosition--;
            }
            for (int j = 0; j < n; j++) {
                if (xPosition == treasurePosition[j][0] && yPosition == treasurePosition[j][1]) {
                    count++;
                    treasurePosition[j][0] = -1;
                    treasurePosition[j][1] = -1;
                }
                // cout << xPosition << " " << yPosition << endl;
            }
        }
    }
    if (count == n)
        return "Yes";
    else
        return "No";
}

int main(int argc, char const *argv[]) {
    int n;
    vector<string> ans;
    while (1) {
        cin >> n;
        if (n == 0) {
            break;
        }
        ans.push_back(solve(n));
    }
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << endl;
    }
    return 0;
}



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

int n;
priority_queue<int> pq;
vector<bool> seen;

void dfs(int cur, vector<int> v)
{
    if(cur == n)
    {
        int sum = 0;
        for(auto vi:v)
        {
            sum *= 10;
            sum += vi;
        }
        pq.push(sum);
        return;
    }

    rep(i,n)
    {
        if(seen[i]) continue;
        seen[i] = true;
        v.push_back(i+1);
        dfs(cur+1, v);
        v.pop_back();
        seen[i] = false;
    }
}

int main()
{    
    cin >> n;
    int p = 0;
    rep(i,n)
    {
        int p_;
        cin >> p_;
        p *= 10;
        p += p_;
    }
    int q = 0;
    rep(i,n)
    {
        int q_;
        cin >> q_;
        q *= 10;
        q += q_;
    }

    seen.assign(n, false);
    vector<int> v;
    dfs(0, v);

    int a = -1;
    int b = -1;
    for(int i=0,imax=(int)pq.size();i<imax;++i)
    {
        int pqi = pq.top();
        pq.pop();
        if(pqi == p) a = i;
        if(pqi == q) b = i;

        if(a >= 0 && b >= 0) break;
    }
    
    cout << abs(a-b) << endl;
    return 0;
}

Measured memory_bytes: 640
// B - ∵∴∵
#include <bits/stdc++.h>
using namespace std;

int main(){
	vector<string> s(2);
	cin>>s[0]>>s[1];
	for(int i=0; i<s[0].size()+s[1].size(); i++) cout<< s[i%2][i/2];
	cout<<"\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n,m,count=0;
	cin>> n >>m;
	vector<int>v;
	for(int i=0;i<m;i++){
		int h;
		cin>>h;
		v.push_back(h);
		count += v[i];
	}
	if(count > n)
	cout<<"-1"<<endl;
 
	else
	cout<<n-count<<endl;
	return 0;
}

Measured memory_bytes: 3728
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#define inf 0x3f3f3f3f
using namespace std;

int a,b,w;

int main()
{
    scanf("%d%d%d",&w,&a,&b);
    int aa=a+w;
    int bb=b+w;
    if(aa<b)
        cout << b-aa << endl;
    else if(bb<a)
        cout << a-bb << endl;
    else
        cout << "0" << endl;
}


Measured memory_bytes: 256
n = int(raw_input())
deck = [i for i in range(1,2*n+1)]
m = int(raw_input())
for i in range(m):
    k = int(raw_input())
    if k == 0:
        for j in range(n):
            deck += [deck[j]]+[deck[n+j]]
        deck = deck[2*n:]
    else:
        deck = deck[k:]+deck[:k]
for i in deck:
    print i

Measured memory_bytes: 4248
//INCLUDE
//------------------------------------------
#include <bits/stdc++.h>
//DEFINE
//------------------------------------------
#define ll long long
#define ld long double
#define ALLv(a)  (a).begin(),(a).end()
#define ALL(a,n)  (a),(a)+n
#define vi vector<long long>
#define vd vector<long double>
#define vs vector<string>
//CONST
//------------------------------------------
#define INF 1010000000000000017LL
#define MOD 1000000007LL
#define EPS 1e-12
#define PI 3.14159265358979323846
//REPEAT
//------------------------------------------
#define   FOR(i,m,n) for(ll (i)=(m);   (i)<(n);  (i)++)
#define   REP(i,n)   for(ll (i)=0;     (i)<(n);  (i)++)
#define  REPS(i,x)   for(ll (i)=1;     (i)<=(x); (i)++)
#define  RREP(i,x)   for(ll (i)=(x)-1; (i)>=0;   (i)--)
#define RREPS(i,x)   for(ll (i)=(x);   (i)> 0;   (i)--)
#define  WREP(i,in,j,jn) REP(i,in)REP(j,jn)
//-----------------------------------------
#define ifYN(x) cout<<(x?"Yes":"No")<<"\n" 
#define dcml(n) fixed<<setprecision(n)

 
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; } 
ll Factorial(ll n){ ll m=1;while(n>=1)m*=n--;return m; } 
ll modPow(ll x,ll n,ll mod=MOD){ 
    return (!n?1:!n%2?modPow(x*x,n/2,mod)%mod:x%mod*modPow(x,n-1,mod)%mod); 
} 
ll GetDigit(ll num){ 
    ll digit=0; 
    while(num!=0){num/=10;digit++;} 
    return digit; 
} 


using namespace std;
//-------------------------------------------
typedef pair<ll,ll> P;
struct Edge{
  ll to,dist;
};
ll N;
ll d[2000];
vector<Edge> G[2000];

void dijkstra(ll u){
  REP(i,N)d[i]=INF;
  priority_queue<P,vector<P>,greater<P>> que;
  que.push({0,u});
  while(!que.empty()){
    auto r=que.top();que.pop();
    if(r.first>=d[r.second])continue;
    d[r.second]=r.first;
    
    for(Edge& e: G[r.second]){
      ll dist=d[r.second]+e.dist;
      if(dist>=d[e.to])continue;
      que.push({dist,e.to});
    }
  }
}

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N;cin>>N;
  ll ans=INF;
  REPS(i,sqrt(N)){
    if(N%i!=0)continue;
    ll m=N/i;
    ans=i+m-2;
  }
  cout<<ans;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <regex>
using namespace std;

#define FOR(i, a, b)   for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b)  for(int i = (a); i > (b); --i)

typedef long long ll;

int main()
{
    int X;
    cin>>X;
    if(X==7|X==5|X==3)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
using namespace std;
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[10000001];
//char str[1010][1010];
//vector<pair<int,int> > pc[100001];
//int ABS(int a){return max(a,-a);}
//long long num[100000];
int main(){
	string s;
	cin>>s;
	string k[s.length()];
	for(int i=0;i<s.length();i++){
		if(s[i]=='9') k[i]='1';
		else if(s[i]='1') k[i]='9';
	}
	for(int i=0;i<s.length();i++){
		cout<<k[i];
	}
	return 0;
}

Measured memory_bytes: 256
N = int(input())

c = [[0] * 10 for _ in range(10)]
for n in range(1, N + 1):
    s = int(str(n)[0])
    e = int(str(n)[-1])

    c[s][e] += 1

ans = 0
for x in range(10):
    for y in range(10):
        ans += c[x][y] * c[y][x]

print(ans)





Measured memory_bytes: 40556
#include<bits/stdc++.h>
using namespace std;
int main()
  {
  string s,s1;
  cin>>s>>s1;
  int flag=0;
  for(int i=0;i<s.size();i++){
    if(s[i]!=s1[i]){
      flag =1;
      break;
      }
    }
  if(flag)
    cout<<"No";
  else cout<<"Yes";
  }
    


Measured memory_bytes: 3596
#include <iostream>

using namespace std;

int main()
{
    string num;
    cin>>num;
    long long int sum=0;
    for(char ch: num)
        sum+=(ch-'0');
    //cout<<sum<<endl;
    if(sum%9==0)
        cout<<"Yes\n";
    else
        cout<<"No\n";
    return 0;
}


Measured memory_bytes: 3732
//#define NDEBUG
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
static constexpr double PI = 3.1415926535897932;

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;
using intl32 = std::int_least32_t;
using intl64 = std::int_least64_t;
using uintl32 = std::uint_least32_t;
using uintl64 = std::uint_least64_t;

void yes(bool c) { puts(c ? "yes" : "no"); }
void Yes(bool c) { puts(c ? "Yes" : "No"); }
void YES(bool c) { puts(c ? "YES" : "NO"); }
void pos(bool c) { puts(c ? "possible" : "impossible"); }
void Pos(bool c) { puts(c ? "Possible" : "Impossible"); }
void POS(bool c) { puts(c ? "POSSIBLE" : "IMPOSSIBLE"); }
template<class T>bool bmaxi(T&a, const T&b) { if (b<a)return 0;a = b;return 1; }
template<class T>bool bmini(T&a, const T&b) { if (a<b)return 0;a = b;return 1; }
template<class T>bool nmaxi(T&a, const T&b) { if (a<b) { a = b;return 1; }return 0; }
template<class T>bool nmini(T&a, const T&b) { if (b<a) { a = b;return 1; }return 0; }
template<typename T>auto scan(T&d)->typename std::enable_if<std::is_signed<T>::value>::type {
	d = 0;int c = fgetc(stdin);bool f = 0;while (c<'0' || '9'<c) { if (c == '-')f = 1;c = fgetc(stdin); }
	while ('0' <= c&&c <= '9') { d = d * 10 + c - '0';c = fgetc(stdin); }if (f)d = -d;
}
template<typename T>auto scan(T&d)->typename std::enable_if<!std::is_signed<T>::value>::type {
	d = 0;int c = fgetc(stdin);while (c<'0' || '9'<c)c = fgetc(stdin);
	while ('0' <= c&&c <= '9') { d = d * 10 + c - '0';c = fgetc(stdin); }
}
template<>void scan(double&d) { scanf("%lf", &d); }
template<>void scan(std::string&d) {
	d.clear();int c = fgetc(stdin);
	while (c <'a' || 'z'<c)c = fgetc(stdin);while ('a' <= c&&c <= 'z') { d.push_back(c);c = fgetc(stdin); }
}
template<typename F, typename...R>void scan(F&f, R&...r) { scan(f);scan(r...); }
template<typename T>T input() { T d;scan(d);return d; }

int main(void) {
	printf("%u\n", input<uint32>() / 3);

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (ll i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (LLONG_MAX)
#define MOD (1000000007)
#define MAX (100000)
#define pii pair<int, int>

/////////////////////////////////////////////////////////

class XY{
public:
  ll x, y;
  XY() {x = y = 0;}
  XY(ll u, ll v) {x = u; y = v;}
};

template<typename T1, typename T2>
void chmin(T1 &a, T2 b) {if(a > b) a = b;}
template<typename T1, typename T2>
void chmax(T1 &a, T2 b) {if(a < b) a = b;}

template<typename T1, typename T2>
ll mypow(T1 a, T2 n){
  if(n == 0) return 1;
  if(n == 1) return a;
  if(n % 2) return a * mypow(a, n - 1);
  ll tmp = mypow(a, n / 2);
  return tmp * tmp;
}

template<typename T>
int BS(vector<T> V, int left, int right, T key){
  int mid = (left + right) / 2;
  if(V[mid] <= key) left = mid;
  else right = mid;
  if(right - mid == 1) return left;
  else return BS(V, left, right, key);
}

/////////////////////////////////////////////////////////

ll comb(ll n, ll r){
	ll res = 1;
  rep(i, 0, r){
    res *= n - i;
    res /= i + 1;
  }
  return res;
}

void Main() {
  ll N, P; cin >> N >> P;
  ll cnt = 0;
  rep(i, 0, N){
    ll tmp; cin >> tmp;
    if(tmp % 2) cnt++;
  }
  ll res = 0;
  rep(i, 0, cnt + 1){
    if(i % 2 != P) continue;
    //from here
    res += comb(cnt, i);
  }
  res *= mypow(2, N - cnt);
  cout << res << endl;
}

/////////////////////////////////////////////////////////

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);

  Main();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
double pi = 3.141592653589793;
ll mod = 1000000007;
ll INF = 1000000001;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;



int main(){
	int a,b;
	cin>>a>>b;
	if (a>=13){
		cout<<b<<endl;

	}
	else if (a<=5){
		cout<<0<<endl;
	}
	else{
		cout<<b/2<<endl;
	}


    return 0;
}

Measured memory_bytes: 256
from collections import Counter


n = int(input())
arr = list(map(int, input().split()))

c = Counter(arr)
c_ = {k: v*(v-1)//2 for k, v in c.items()}
s = sum(c_.values())

for a in arr:
    tmp = c[a] - 1
    ans = s - c_[a] + tmp*(tmp-1)//2
    print(ans)


Measured memory_bytes: 32156
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dbl;
#define sqr(int) (int * int)
#define sqr3(int) (int * int * int)
#define pi M_PI
#define nl "\n"



  
  int main(){
	ios::sync_with_stdio(true);
	cin.tie(0);
    
    int a;
    cin >> a;
    cout << a + sqr(a) + sqr3(a);
}
	
	
	
	


	



Measured memory_bytes: 3624
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
# define int long long
const int inf = 2147400000 ;
using namespace std;
inline int read(){
    char c = getchar() ; int x = 0, w =1 ;
    while(c>'9'||c<'0'){ if(c=='-') w = -1; c = getchar() ;}
    while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar() ;}
    return x*w ;
}
int a,b,c,k ;
# undef int 
int main(){
# define int long long
    cin>>a>>b>>c>>k;
    if(k&1){
    	if(b-a>1e18)
    	  cout<<"Unfair\n";
    	else 
    	cout<<b-a<<endl;
	}
	else {
	    if(b-a>1e18)
    	  cout<<"Unfair\n";
		cout<<a-b ;
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
have = [1000, 0]
up = 0
for i in range(n - 1):
    if up:
        if a[i] > a[i + 1]:
            have[0] += have[1] * a[i]
            have[1] = 0
            up = 0
    else:
        if a[i] < a[i + 1]:
            have[1] = have[0] // a[i]
            have[0] = have[0] % a[i]
            up = 1
print(have[0] + have[1] * a[-1])

Measured memory_bytes: 61928
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int h,w,m,x,y,r[N],c[N];
vector<int>v1,v2;
map<pair<int,int>,int>mp;
int main(){
    cin>>h>>w>>m;
    while(m--){
        cin>>x>>y;
        r[x]++,c[y]++;
        mp[{x,y}]=1;
    }
    int mx1=0,mx2=0;
    for(int i=1;i<=h;i++) mx1=max(mx1,r[i]);
    for(int i=1;i<=h;i++) if(r[i]==mx1) v1.push_back(i);
    for(int i=1;i<=w;i++) mx2=max(mx2,c[i]);
    for(int i=1;i<=w;i++) if(c[i]==mx2) v2.push_back(i);
    for(auto i:v1) for(auto j:v2) if(!mp[{i,j}]) {cout<<mx1+mx2;exit(0);}
    cout<<mx1+mx2-1;
}


Measured memory_bytes: 28516
#include <bits/stdc++.h>
using namespace std;
int n,m,a[1000010],b[1000010],s;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)scanf("%d",a+i),s+=a[i]&1;
	if(s>2)return puts("Impossible"),0;
	sort(a+1,a+m+1,[](int x,int y)->bool{return (x&1)>(y&1);});
	if(m==1)if(a[1]==1)return puts("1\n1\n1"),0;else return printf("%d\n%d\n%d %d",a[1],2,a[1]-1,1),0;
	swap(a[2],a[m]);
	for(int i=1;i<=m;++i)printf("%d ",a[i]);
	printf("\n%d\n",a[m]==1?m-1:m);
	for(int i=1;i<=(a[m]==1?m-1:m);++i)printf("%d ",i==1?a[i]+1:i==m?a[i]-1:a[i]);
}

Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n; cin >> n;
  vector<int> v(n);
  vector<pair<int, int>> p(n);
  for(int i = 0; i < n; ++i){
    cin >> p[i].first;
    p[i].second = i;
  }
  sort(p.begin(), p.end());
  int mid = n / 2;
  vector<int> ans(n);
  for(int i = 0; i < n; ++i){
    if(mid <= i) ans[p[i].second] = p[mid - 1].first;
    else ans[p[i].second] = p[mid].first;
  }
  for(int i = 0; i < n; ++i){
    cout << ans[i] << endl;
  }
}

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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
 
#define FS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
#define ld long double
#define pb push_back
#define bp __builtin_popcount
#define sz size()
#define ff first
#define ss second
#define vll vector<ll>
#define vbool vector<bool>
#define vpll vector<pair<ll,ll>>
#define pll pair<ll,ll>
#define vllv vector<vector<ll>>
#define setpri(x) cout<<setprecision(x)<<fixed;
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define yesr {cout<<"YES"<<endl;return;}
#define nor {cout<<"NO"<<endl;return;}
// getline (std::cin,name);
ll MOD=1e9+7;
ll ceil1(ll n,ll x){if(n%x==0)return n/x; else return (n/x)+1;}
ll gcd(ll a,ll b){return __gcd(a,b);}
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}
ll pow1(ll n,ll k,ll mm){
    if(k==0)return 1;
    if(k%2==0)return (pow1((n%mm)*(n%mm),k/2,mm))%mm;
    	return ((n%mm)*(pow1((n%mm)*(n%mm),k/2,mm)%mm))%mm;
}
ll pow2(ll n,ll k){ll ans=1;
    while(k>0){
        if(k%2==1)ans=ans*n;n=n*n;k/=2;
    }return ans;
}
ll modinv(ll n,ll mod){
    return pow1(n,mod-2,mod);
}
bool func(pair<ll,ll> &a,pair<ll,ll> &b ){
    if(a.ff != b.ff)return a.ff < b.ff;
    return a.ss > b.ss;
}
const ll N=200000+11;
ll fact[N];
ll inv[N];
void pri(ll mod){
	fact[0]=fact[1]=1;
	for(int i=2;i<=2e5;i++){
		fact[i]=(i*fact[i-1])%mod;
	}
	inv[200000]=modinv(fact[200000],mod);
	for(int i=0;i<=2e5;i++){
		inv[i]=modinv(fact[i],mod);
	}
	
}
void solve(){
	
    ll i,j,k,l,n,m,x,y,z,r;
	 ll mod=998244353;
	 
	 pri(mod);
	 
	 cin>>n>>m>>k;
	 ll ans=0;
	 for(i=0;i<=k;i++){
	 	ll tt=pow1(m-1,n-1-i,mod);
	 	tt*=m;
	 	tt%=mod;
	 	// cout<<tt<<endl;
	 	tt*=fact[n-1];
	 	tt%=mod;
	 	
	 	tt*=inv[i];
	 	tt%=mod;
	 	
	 	tt*=inv[n-1-i];
	 	tt%=mod;
	 	
	 	// cout<<tt<<endl;
	 	ans+=tt;
	 	ans%=mod;
	 }
	 
	 cout<<ans<<endl;
 
	
}
int main(){
    FS;
    ll i,j,k,n,m,x,y,z,q;
    q=1;
    // cin>>q;
    while(q--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 6808
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
using namespace std;

struct Node{
	int key;
	Node *right, *left, *parent;
};

Node *root, *NIL;

Node * find(Node *u, int k){
	while(u != NIL && k != u->key){
		if(k < u->key )u = u->left;
		else u = u->right;
	}
	return u;
}
void insert(int k){
  Node *y = NIL;
  Node *x = root;
  Node *z;
  
  z = (Node *)malloc(sizeof(Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  
	
  while( x != NIL ){
    y = x;
    if( z->key < x->key ){
      x = x->left;
    } else {
      x = x->right;
    }
  }
  
  z->parent = y;
  if( y == NIL ){
    root = z;
  } else {
    if( z->key < y->key ){
      y->left = z;
    } else {
      y->right = z;
    }
  }
}

void inorder(Node *u) {
  if ( u == NIL ) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(Node *u) {
  if ( u == NIL ) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
	int n, i, x;
	string com;
	
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		cin >> com;
		if(com[0] == 'f'){
			scanf("%d", &x);
			Node *t = find(root, x);
			if(t != NIL)printf("yes\n");
			else printf("no\n");
		}else if (com == "insert"){
			scanf("%d", &x);
			insert(x);
		}else if(com == "print"){
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}
	}
	
	return 0;
}


	




Measured memory_bytes: 22028
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define lli long long int
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define ve vector<lli>
#define vep vector<pair<lli,lli> >
#define fr(i,n) for(lli i=0;i<(n);i++)
#define F first
#define S second
long long int gcd(long long int a,long long int b)
{
	if(a==0)return b;
	return gcd(b%a,a);
}
int bin(long int a[],long int low,long int high,long d,long day[])
{
	//cout<<low<<" "<<high<<" "<<d<<"\n";
	if(low>high)return -1;
	long mid=(low+high)/2;
	if(a[mid]>(a[low]+d)&&(a[mid-1]<=(a[low]+d)||day[mid-1])&&day[mid]==0)
		return mid;
	else if(a[mid]>(a[low]+d)&&day[mid]==0)
		return bin(a,low,mid-1,d,day);
	else
		return bin(a,mid+1,high,d-a[mid+1]+a[low],day);
}
long long power(long long a,long long b)
{
	//cout<<a<<" "<<b<<"\n";
	if(b==0)return 1;
	if(b%2==0)return (power((a*a)%mod,b/2))%mod;
	return ((a%mod)*(power((a*a)%mod,b/2))%mod)%mod;
}
/*int subtree(vector<int>v,int sub[],i,j)
{
	if(sub[i]>0)return sub[i];
	for(auto x:v[i])
	{
		if(x!=j)sub[i]+=subtree(v,sub,x,i);
	}
	return sub[i];
}*/
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)
	{
		int n,k;
		cin>>n>>k;
		int a[n],i,j;
		fr(i,n)cin>>a[i];
		int dp[k+1]={0};
		for(i=1;i<=k;i++)
		{
			for(j=0;j<n;j++)
			{
				if(i-a[j]>=0)
				{
					dp[i]|=(dp[i-a[j]]+1)%2;
				}
			}
		}
		if(dp[k])cout<<"First\n";
		else cout<<"Second\n";
	}
	return 0;
}

Measured memory_bytes: 640
use std::str::FromStr;
use std::io::*;
use utils::*;

pub fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}

fn run<R: BufRead, W: Write>(i: R, o: &mut W) {
    let mut i = AtRead::from(i);
    let n = i.read::<usize>();
    let a = i.read_vec::<i64>(n);

    writeln!(o, "{}", solve(&a)).unwrap();
}
fn solve(a: &[i64]) -> i64 {
    let cost = |x: i64| a.iter().map(|a| (a - x) * (a - x)).sum();
    (-100..100 + 1).map(cost).min().unwrap()
}

mod utils {
    use super::*;

    pub struct AtRead<R: BufRead> {
        r: R,
        s: String,
    }

    impl<R: BufRead> AtRead<R> {
        pub fn from(r: R) -> Self {
            AtRead {
                r: r,
                s: String::new(),
            }
        }
        pub fn read_line(&mut self) -> &str {
            self.s.clear();
            self.r.read_line(&mut self.s).unwrap();
            self.s.trim()
        }

        pub fn read<T: FromStr>(&mut self) -> T {
            self.read_line().parse().ok().unwrap()
        }

        pub fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            self.read_line()
                .split(' ')
                .take(n)
                .map(|x| x.parse().ok().unwrap())
                .collect()
        }
    }
}


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

typedef long long ll;

int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		s[i] = (s[i] - 'A' + n) % 26 + 'A';
	}
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    // Your code here!
    int H,W,K;
    char map[6][7] = {};
    int ans = 0;
    
    scanf("%d%d%d",&H,&W,&K);
    
    for(int i = 0; i < H; i++){
        scanf("%6s",map[i]);
        //printf("%s\n",map[i]);
    }
    
    for(int Hb = 0; Hb < (int)pow(2,H); Hb++ ){
        for(int Wb = 0; Wb < (int)pow(2,W); Wb++){
            int brack = 0;
            for(int i = 0; i < H; i++){
                for(int j = 0; j < W; j++){
                    if((Hb>>i & 1) == 0 && (Wb>>j & 1) == 0 && map[i][j] == '#'){
                        brack++;
                    }
                }
            }
            if(brack == K){
                ans++;
            }
        }
    }
    
    printf("%d\n",ans);
}


Measured memory_bytes: 2480
n = input()
negBase = -2

if (n == 0): 
    converted = "0"

else:
    converted = "01"
    while (n != 0):           
        remainder = n % (negBase) 
        n = int(n/negBase) 
  
        if (remainder < 0): 
            remainder += ((-1) * negBase) 
            n += 1
  
        converted = str(remainder) + converted 
          
    converted = converted[0:len(converted)-2]

print(converted)

Measured memory_bytes: 2568
T1,T2 = map(int,input().split())
A1,A2 = map(int,input().split())
B1,B2 = map(int,input().split())
ans = 0
if T1*A1+T2*A2 == T1*B1+T2*B2:
    print("infinity")
    exit()
if A1>B1:
    jtA = True
else:
    jtA = False
if jtA:
    if T1*A1+T2*A2 > T1*B1+T2*B2:
        print(0)
        exit()
    else:
        jA = False
        x = abs(T1*B1+T2*B2 - T1*A1-T2*A2)
else:
    if T1*A1+T2*A2 < T1*B1+T2*B2:
        print(0)
        exit()
    else:
        jA = True
        x = abs(T1*A1+T2*A2 - T1*B1-T2*B2)

if (abs(A1-B1)*T1)%x == 0:
    ans += ((abs(A1-B1)*T1)//x)*2
else:
    ans += ((abs(A1-B1)*T1)//x)*2+1
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,cnt=0;
    cin>>n;
    int arr[n];
    int check=1;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        if(arr[i]==check)
        {
            cnt++;
            check++;
        }
    }
    if(n==1&&cnt==1)
        printf("0\n");
    else if(cnt==0)
            printf("-1\n");
    else
        printf("%d\n",n-cnt);
    return 0;
}


Measured memory_bytes: 1024
from collections import defaultdict
N = int(input())
rates = [int(i) for i in input().split()]
# N = 4
# rates = [2100, 2500, 2700, 2700]

color_nums = defaultdict(int)

for rate in rates:
    if rate <= 399:
        color_nums['灰'] += 1
    elif rate <= 799:
        color_nums['茶'] += 1
    elif rate <= 1199:
        color_nums['緑'] += 1
    elif rate <= 1599:
        color_nums['水'] += 1
    elif rate <= 1999:
        color_nums['青'] += 1
    elif rate <= 2399:
        color_nums['黄'] += 1
    elif rate <= 2799:
        color_nums['橙'] += 1
    elif rate <= 3199:
        color_nums['赤'] += 1
    else:
        color_nums['自由'] += 1

free_num = color_nums['自由']
if free_num == 0:
    # 自由に変えられる人がいない場合
    # -1 は free_num = color_nums['自由']で増えてしまったので...
    print(len(color_nums)-1, len(color_nums)-1)
elif free_num == N:
    # 自由に変えられる人しかいない場合
    print(1, free_num)
elif free_num != N:
    # 自由な人と混在
    tmp = dict(color_nums)  # コピーを作る
    tmp.pop('自由')
    l_tmp = len(tmp)
    min_num = l_tmp
    max_num = l_tmp + free_num
    print(min_num, max_num)


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

const ll mod = 1e9 + 7;

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

/*-------------------------------------------*/

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

    ll n;
    cin >> n;
    ll a[n], k = 0;
    rep(i, n) cin >> a[i], k += a[i];
    if(k % (n * (n + 1) / 2)) {
        cout << "NO\n";
        return 0;
    }
    k /= n * (n + 1) / 2;
    rep(i, n) {
        ll x = a[(i + 1) % n] - a[i] - k;
        if(x > 0 || (-x) % n != 0) {
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
}

Measured memory_bytes: 1024