akhauriyash/Code-Regression huggingface dataset:
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	log.SetFlags(log.Lshortfile)
	a := nextInt()
	b := nextInt()
	if a >= 1 && a <= 9 && b >= 1 && b <= 9 {
		fmt.Println(a * b)
	} else {
		fmt.Println("-1")
	}
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}
var MAX = math.MaxInt32

func pow(a, b int) int {
	return int(math.Pow(float64(a), float64(b)))
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type pair struct {
	a, b int
}

type pairs []pair

func (p pairs) Len() int {
	return len(p)
}
func (p pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p pairs) Less(i, j int) bool {
	if p[i].a == p[j].a {
		return p[i].b < p[j].b
	}
	return p[i].a < p[j].a
}


Measured memory_bytes: 640
def solve():
    N = int(input())
    S = input()
    l,r = 0,0
    state = 'r'
    for i in range(N):
        if i == 0 and S[i] == ')': state = 'l'
        # if S[i] == '(': state = 'r'
        if i > 0  and S[i-1] == ')' and S[i] == '(':
            state = 'r' 
            
        if S[i] == '(':
            if state == 'l':
                if l > 0:
                    l -= 1
                else:
                    r += 1
            elif state == 'r':
                r += 1
        elif S[i] == ')':
            if state == 'r':
                if r > 0:
                    r -= 1
                else:
                    l += 1
            elif state == 'l':
                l += 1
                
        # print(state,l,r)
            
    print('('*l+S+')'*r)
    
solve()

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

//単一始点最短経路（負の重みをもつ辺を含む）
//https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B
#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, char, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

const ll mod = 1000000007;

const ll INF = 1e15;

struct warshall_floyd {
	static bool solve(vector<vector<ll>>& d) {
		int n = d.size();
		rep(k, n) {
			rep(i, n) {
				rep(j, n) {
					if (d[i][k] != INF && d[k][j] != INF) {
						auto u = d[i][k] + d[k][j];
						if (d[i][j] > u) {
							d[i][j] = u;
						}
					}
				}
			}
		}
		rep(k, n) {
			rep(i, n) {
				rep(j, n) {
					if (d[i][k] != INF && d[k][j] != INF) {
						auto u = d[i][k] + d[k][j];
						if (d[i][j] > u) {
							return false;
						}
					}
				}
			}
		}
		return true;
	}
}; 

int main(void)
{
	int v, e;
	cin >> v >> e;
	vector<vector<ll>> g(v, vector<ll>(v, INF));
	rep(i, v) {
		g[i][i] = 0;
	}
	rep(i, e) {
		ll s, t, d; 
		cin >> s >> t >> d;
		g[s][t] = d;
	}
	bool ok = warshall_floyd::solve(g);
	if (!ok) {
		cout << "NEGATIVE CYCLE" << endl;
		return 0;
	}
	rep(i, v) {
		rep(j, v) {
			if (g[i][j] == INF) {
				cout << "INF";
			}
			else {
				cout << g[i][j];
			}			
			if (j != v - 1) cout << " ";
			else cout << endl;
		}
	}
	return 0;
}



Measured memory_bytes: 3240
#include <stdio.h>

int main(void) {
  int H,W,i,j,ans = 1;
  char S[51][51];
  scanf("%d %d",&H,&W);
  for (i = 0;i < H;i++) {
    scanf("%s",&S[i][0]);
  }
  for (i = 0;i < H;i++) {
    for (j = 0;j < W;j++) {
      if (S[i][j] == '#' && S[i - 1][j] != '#' && S[i][j - 1] != '#' && S[i][j + 1] != '#' && S[i + 1][j] != '#') ans = 0;
    }
  }
  if (ans == 1) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 128
import math
import copy
import sys

inputa = input().split()
# inputb = input().split()
# inputc = input().split()

a = int(inputa[0])
# b = int(inputa[1])
# c = int(inputa[2])

# x = int(inputb[0])
# y = int(inputb[1])

# inputb = input().split()
# inputbList = [int(n) for n in inputb]
#
inputList = []
inputNumList = []
for i in range(a):
    inputNum = input().split()
    inputNumList = list(inputNum[0])
    inputList.append(inputNumList)

# inputList = [int(n) for n in inputList]

# b = [int(n) for n in inputb]
# c = [int(n) for n in inputc]

flg = True
for i in range(a):
    if i == 0:
        continue
    else:
        if inputList[i][0] != inputList[i-1][-1]:
            flg = False
            break

        for j in range(i):
            if "".join(inputList[i]) == "".join(inputList[j]):
                flg = False
                break

if flg:
    print("Yes")
else:
    print("No")


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

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }


struct Doubling { // ダブリング
  vector<vector<int>> to; // to[i][j] = jから2^i回操作した値
  int mx;
  Doubling(int n, int d, const vector<int> &a):to(d, vector<int>(n)) {
    mx = d;
    to[0] = a;
    for(int i = 1; i < mx; i++) for(int j = 0; j < n; j++) {
      to[i][j] = to[i-1][to[i-1][j]];
    }
  }
  int operator()(int s, long long k) { // sからk回操作後の値を返す
    int res = s;
    for(int i = mx-1; i >= 0; i--) {
      long long l = 1LL<<i;
      if(l <= k) {
        res = to[i][res];
        k -= l;
      }
    }
    return res;
  }
};

const int MX = 60;

int main(){
    
    int n;
    ll k;
    cin >> n >> k;
    V<int> a(n);
    rep(i,n) {
        cin >> a[i];
        a[i]--;
    }
    Doubling d(n,MX,a);
    int ans = d(0,k)+1;
    cout << ans << endl;
}

Measured memory_bytes: 51756
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<cmath>
#define ll long long
#define Pr pair<ll,ll>
#define mp make_pair
using namespace std;
const int N=1e5+10;
map<ll,int> cnt;
int p[N];
int vis[N];
ll p2[N],lis[N];
Pr rec[N];
int n,m,cntp,cntpair,ans;
void prework(int n){
	cntp=0;	
	vis[1]=1;
	for (int i=2;i<=n;++i){
		if (!vis[i])
			p[++cntp]=i,p2[cntp]=1LL*i*i;
		for (int j=1;j<=cntp&&i*p[j]<=n;++j){
			vis[i*p[j]]=1;
			if (i%p[j]==0) break;
		}
	}
}
void print(Pr x){
	printf("(%lld,%lld)\n",x.first,x.second);
}
void work(ll val){
	int tmp=0;
	//if (val==1) return;
	ll nwval=1,need=1;
	for (int i=1;p2[i]*p[i]<=val;++i){
		if (val%p[i]) continue;
		tmp=0;
		while (val%p[i]==0) tmp=(tmp+1)%3,val/=p[i];
		if (tmp==0) continue;
		else if (tmp==1) need*=p2[i],nwval*=p[i];
		else need*=p[i],nwval*=p2[i];
	}
	nwval*=val;
	//if (nwval==1) return;
	if (val>1){
		ll ttmp=sqrt(val);
		if (ttmp*ttmp==val)
			need*=ttmp;
		else
			need*=val*val;
	}
	++cnt[nwval];
	//print(mp(nwval,need));
	if (nwval>need) rec[++cntpair]=mp(need,nwval);
	else rec[++cntpair]=mp(nwval,need);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
#endif
	ll val,val1;
	scanf("%d",&n);
	prework(1e5);
	cnt.clear();
	lis[0]=0; cntpair=0;
	for (int i=1;i<=n;++i){
		scanf("%lld",&val);
		work(val);
	}
	sort(rec+1,rec+1+cntpair);
	cntpair=unique(rec+1,rec+1+cntpair)-rec-1;
	ans=0;
	for (int i=1;i<=cntpair;++i)
		if (rec[i].first==1&&rec[i].second==1)
			ans+=1;
		else 
			ans+=max(cnt[rec[i].first],cnt[rec[i].second]);
	printf("%d\n",ans);
}

Measured memory_bytes: 18380
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

char rev(char c){
	if(c == '('){ return ')'; }
	if(c == ')'){ return '('; }
	if(c == '{'){ return '}'; }
	if(c == '}'){ return '{'; }
	if(c == '['){ return ']'; }
	if(c == ']'){ return '['; }
	return c;
}

int main(){
	string s;
	cin >> s;
	int answer = 0;
	for(int i = 0; i < (1 << s.size()); ++i){
		string t;
		for(int j = 0; j < s.size(); ++j){
			if(i & (1 << j)){ t += s[j]; }
		}
		if(t.size() < 3 || t.size() % 2 != 1){ continue; }
		bool valid = true;
		for(int j = 0; j < t.size(); ++j){
			if(t[j] != rev(t[t.size() - j - 1])){ valid = false; }
		}
		int center = t.size() / 2;
		if(t[center - 1] != 'i' || t[center] != 'w' || t[center + 1] != 'i'){
			valid = false;
		}
		if(count(t.begin(), t.end(), 'i') != 2){ valid = false; }
		if(count(t.begin(), t.end(), 'w') != 1){ valid = false; }
		if(valid){ answer = max(answer, (int)t.size()); }
	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
const ll MOD = 1e9 + 7;
const ll INF = 1e9;

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}

int main(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  // ll n;
  // cin >> n;
  ll d, g;
  cin >> d >> g;
  // ll n, m, k;
  // cin >> n >> m >> k;
  int num[d], bonus[d];
  int ans = INF;
  fi(0, d){
    cin>>num[i];
    cin>>bonus[i];
  }
  // bitmap of d bits
  fi(0, 1 << d) {
    int cnt = 0;
    int score = 0;
    fj(0, d) {
      // add all scores and bonus if the bit is 1
      if((i >> j) & 1) {
        cnt += num[j];
        score += num[j] * (j + 1) * 100;
        score += bonus[j];
      }
    }
    // for the shortage, add from the largest one which the bit is 0
    for(int j = d - 1; j >= 0; --j) {
      if(!((i >> j) & 1)) {
        for(int k = 0; k < num[j] && score < g; ++k) {
          score += (j + 1) * 100;
          ++cnt;
        }
      }
    }
    if(score >= g) {
      ans = min(ans, cnt);
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int
signed main()
 {
	//code
  	int n;
  	cin>>n;
  	int prev;
  	cin>>prev;
  int ans=0;
  	for(int i=1;i<n;i++){
    	int curr; 	
    	cin>>curr;
      	if(curr<prev){ 
          ans+=(prev-curr);
        }else{
          prev=curr;
        }
      
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3640
use std::io::{BufRead, Write};
use std::io;
use std::cmp::Ordering;

fn solve<R: BufRead, W: Write>(mut input: R, mut output: W) {
    let mut s = String::new();
    input.read_line(&mut s).unwrap();
    let mut split = s.split_whitespace();
    let _ = split.next().unwrap().parse::<usize>().unwrap();
    let mut s = String::new();
    input.read_line(&mut s).unwrap();
    let a = s.split_whitespace()
        .map(|s| s.parse::<u32>().unwrap())
        .collect::<Vec<_>>();
    let mut result = 1usize;
    if a.len() >= 2 {
        let mut flag = a[1].cmp(&a[0]);
        for i in 1..a.len() {
            match (a[i].cmp(&a[i - 1]), flag) {
                (x, y) if x == y => {}
                (Ordering::Equal, _) => {}
                (x, Ordering::Equal) => {
                    flag = x;
                }
                _ => {
                    result += 1;
                    if i != a.len() - 1 {
                        flag = a[i + 1].cmp(&a[i]);
                    }
                }
            }
        }
    }
    writeln!(output, "{}", result).unwrap();
}

fn main() {
    let stdin = io::stdin();
    let stdout = io::stdout();
    solve(stdin.lock(), stdout.lock());
}

#[cfg(test)]
mod tests {
    fn test(input: &str, output: &str) {
        let mut v = Vec::<u8>::new();
        ::solve(input.as_bytes(), &mut v);
        assert_eq!(String::from_utf8(v).unwrap(), output);
    }
    #[test]
    fn case1() {
        test("6
1 2 3 2 2 1\n",
             "2\n");
    }
    #[test]
    fn case2() {
        test("9
1 2 1 2 1 2 1 2 1\n",
             "5\n");
    }
    #[test]
    fn case3() {
        test("7
1 2 3 2 1 999999999 1000000000\n",
             "3\n");
    }
}


Measured memory_bytes: 4352
fun main(args: Array<String>) {
    a74(readLineList())
}

fun readLineList(): Array<String> {
    val lineList = mutableListOf<String>()
    while (true) {
        val line = readLine()
        if (line.isNullOrBlank()) {
            break
        } else {
            lineList.add(line!!)
        }
    }
    return lineList.toTypedArray()
}

fun a74(args: Array<String>) {
    if (args.size != 1) {
        throw IllegalArgumentException()
    }
    val str = args[0]
    println(if (str.contains("9")) "Yes" else "No")
}


Measured memory_bytes: 33908
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<iomanip>

using namespace std;

int main(void) {
	string s;
	cin >> s;
	int count = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '1') {
			count++;
		}
	}
	cout << count;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

int main(void)
{
	int N, X, Y, Z;
	map<int, int>mp;
	cin >> N;
	cin >> X;
	for (int i = 0; i < X; ++i) {
		int a;
		cin >> a;
		mp[a] += 1;
	}
	cin >> Y;
	for (int i = 0; i < Y; ++i) {
		int b;
		cin >> b;
		mp[b] += 2;
	}
	cin >> Z;
	for (int i = 0; i < Z; ++i) {
		int c;
		cin >> c;
		mp[c] += 4;
	}
	int ans = 0;
	for (auto p : mp) {
		if (p.second == 7 || p.second == 6 || p.second == 4) {
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}




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

using namespace std;


#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0)
     
#define ll long long int
#define ld long double


#define fr first
#define se second



#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) (int)v.size()
#define sunq(v) sort(all(v));v.resize(distance(v.begin(),unique(all(v))))


#define pb push_back
#define mp make_pair

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define emla(a, val) memset(a, val, sizeof(a))

#define easm(a, b) (a + b - 1)/b 


#define PI 3.141592653589793238
#define E  2.718281828459045235


ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a*b/gcd(a,b);}


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

const int N = 1e5 + 10;

ll dp[N][4];

int n, a[N][4];

ll solve(int i, int j){
  if(i == n)return 0;
  ll &re = dp[i][j];
  if(re != -1)return re;
  ll mx = 0;
  for(int k = 0; k < 3; k++)
    if(k != j)
      mx = max(mx, a[i][k] + solve(i + 1, k));
  return re = mx;
}


int main(){
  IOS;
  //freopen("input.in", "r", stdin);
  //freopen("output.txt", "w", stdout);
  clock_t z = clock();
  emla(dp, -1);
  cin >> n;
  for(int i = 0; i < n; i++)
    for(int j = 0 ; j < 3; j++)
      cin >> a[i][j];
  cout << solve(0, 3) << endl;
  debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);
  /*
  *try tricky test cases:
    -bounds
    -integer overflow
    -small input (0, 1)
    -big input
    -random tests
  */
  return 0;
}

Measured memory_bytes: 12800
#include<bits/stdc++.h>
#define SORT(v) sort(v.rbegin() , v.rend())
#define si(n) scanf( "%d" , &n)
#define sii(n , m) scanf( "%d %d" , &n , &m)
#define sl(n) scanf( "%lld" , &n)
#define sll(n , m) scanf( "%lld %lld" , &n, &m)
#define ss(cad) scanf( "%s" , cad)
#define sz(x) (int)x.size()
#define PB push_back
#define fst first
#define scn second
#define DBG(x) cerr << #x << " = " << (x) << endl
#define M 1000000007
#define N_MAX 1000010
#define EPS 1e-9

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<pi> vp;

void mostrar(set<pi> ls){
	for(auto x: ls)
		printf("(%d, %d) ", x.fst, x.scn);
}

int main(){
	int h, w;
	sii(h, w);
	set<pi> lista;
	multiset<int> num;
	for(int i = 1; i <= w; i++){
		lista.insert({i, 1});
		num.insert(1);
	}
	int cnt = 0;
	while(h--){
		int a, b;
		sii(a, b);
		bool sw = 0;
		auto pt = lista.lower_bound(pi(a, -1));
		auto pt2 = pt;
		pi mitad = {-1, -1};
		pi inicio;
		if(pt != lista.begin()){
			sw = 1;
			pt--;
			mitad = *pt;
			inicio = *pt;
			pt++;
		}
		while(pt != lista.end() && pt->fst <= b){
			pt2 = pt;
			mitad = *pt;
			num.erase(num.lower_bound(mitad.scn));
			pt++;
			lista.erase(pt2);
		}
		pt2 = lista.lower_bound(pi(b+1, -1));
		if(mitad.fst != -1 && b != w){
			if(pt2 != lista.end() && pt2->fst != b+1){
				int val = mitad.scn + b-mitad.fst+1;
				//update(val, 1);
				num.insert(val);
				lista.insert({b+1, val});
			}
			else if(pt2 == lista.end()){
				int val = mitad.scn + b-mitad.fst+1;
				//update(val, 1);
				num.insert(val);
				lista.insert({b+1, val});
			}
		}
		if(sw){
			int val = inicio.scn + a-inicio.fst;
			//update(val, 1);
			num.insert(val);
			lista.insert({a, val});
		}
		if(num.empty())
			printf("-1\n");
		else
			printf("%d\n", *num.begin()+cnt);
		//mostrar(lista);
		//cout << endl;
		cnt++;
	}
    return 0;
}

Measured memory_bytes: 22496
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()

vector<ll> xd[4][200010], yd[4][200010], pl[4][400020], mi[4][400020];

void chmin(ll& A, ll B) {
	A = min(A, B);
}

int dirnum(char dir) {
	if (dir == 'U')return 0;
	if (dir == 'D')return 1;
	if (dir == 'L')return 2;
	/*if (dir == 'R')*/return 3;
}

int main() {
	int N, X, Y, d;
	char U;
	cin >> N;
	for (int i = 0;i < N;i++) {
		cin >> X >> Y >> U;
		d = dirnum(U);
		xd[d][X].push_back(Y);
		yd[d][Y].push_back(X);
		pl[d][X + Y].push_back(X - Y + 200005);
		mi[d][X - Y + 200005].push_back(X + Y);
	}
	for (int k = 0;k < 4;k++) {
		for (int i = 0;i < 200010;i++) {
			sort(all(xd[k][i]));
			sort(all(yd[k][i]));
			sort(all(pl[k][i]));
			sort(all(mi[k][i]));
		}
		for (int i = 200010;i < 400020;i++) {
			sort(all(pl[k][i]));
			sort(all(mi[k][i]));
		}
	}
	//上下で衝突
	ll S = INT64_MAX;
	for (int i = 0;i < 200005;i++) {
		auto it = xd[1][i].begin();
		for (ll j : xd[0][i]) {
			it = lower_bound(all(xd[1][i]), j);
			if (it == xd[1][i].end())break;
			chmin(S, (*it - j) * 5LL);
		}
	}
	//左右で衝突
	for (int i = 0;i < 200005;i++) {
		auto it = yd[2][i].begin();
		for (ll j : yd[3][i]) {
			it = lower_bound(all(yd[2][i]), j);
			if (it == yd[2][i].end())break;
			chmin(S, (*it - j) * 5LL);
		}
	}
	//上と左で衝突
	for (int i = 0;i < 400015;i++) {
		auto it = mi[2][i].begin();
		for (ll j : mi[0][i]) {
			it = lower_bound(all(mi[2][i]), j);
			if (it == mi[2][i].end())break;
			chmin(S, (*it - j) * 5LL);
		}
	}
	//右と下で衝突
	for (int i = 0;i < 400015;i++) {
		auto it = mi[1][i].begin();
		for (ll j : mi[3][i]) {
			it = lower_bound(all(mi[1][i]), j);
			if (it == mi[1][i].end())break;
			chmin(S, (*it - j) * 5LL);
		}
	}

	//右と上で衝突
	for (int i = 0;i < 400015;i++) {
		auto it = pl[0][i].begin();
		for (ll j : pl[3][i]) {
			it = lower_bound(all(pl[0][i]), j);
			if (it == pl[0][i].end())break;
			chmin(S, (*it - j) * 5LL);
		}
	}
	//下と左で衝突
	for (int i = 0;i < 400015;i++) {
		auto it = pl[2][i].begin();
		for (ll j : pl[1][i]) {
			it = lower_bound(all(pl[2][i]), j);
			if (it == pl[2][i].end())break;
			chmin(S, (*it - j) * 5LL);
		}
	}
	if (S == INT64_MAX) 
		cout << "SAFE" << endl;
	else
		cout << S << endl;
}

Measured memory_bytes: 138708
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef long long ll;
namespace mp = boost::multiprecision;
using Mint = mp::cpp_int;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = int(a); i < int(b); i++)
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define sort_g(v) sort(all(v), greater<int>())
#define dump(x) cerr << #x << ' ' << '=' << ' ' << x << endl

int main() {
    Mint A, B;
    cin >> A >> B;
    if(A > B) cout << "GREATER" << endl;
    else if(A < B) cout << "LESS" << endl;
    else cout << "EQUAL" << endl;
}

Measured memory_bytes: 256
def p_c():
    from itertools import permutations
    N = int(input())
    st_list = "".join(map(str, range(1, N+1)))
    *P, = map(int, input().split())
    *Q, = map(int, input().split())
    *per, = permutations(range(1, N + 1))
    per.sort()
    li = []
    for p in per:
        li.append("".join(map(str, p)))
    p = "".join(map(str, P))
    q = "".join(map(str, Q))
    print(abs(li.index(q) - li.index(p)))
    
p_c()

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

using namespace std;

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

    vector<int> v(5);

    for(int &i : v) cin >> i;

    for(int i=0; i<5; i++){
        if(v[i]==0){
            cout << i+1 << endl;
            return 0;
        }
    }
    
    return 0;
}

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

typedef long long ll;

int main(){
	int a,b,x;
	cin >> a >> b >> x;
	if((x-a)<=b && (x-a)>=0)cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}

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

int main(){
    int a, b;
    cin >> a >> b;
    a--; b--;
    vector<bool> x(3, false);
    x[a] = true; x[b] = true;
    for (int i = 0; i < 3; i++){
        if (!x[i]) {
            cout << i + 1 << endl;
            return 0;
        }
    }
}

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

I n,dp[1024][100001],v[323456],w[323456],c1,c2;

void dfs(I i){
    I j=i/2;
    if(i>1){
        for(I k=c2;k+1;k--){
            if(dp[j-1][k]or!k){
                I ne=k+w[i-1];
                if(ne<=c2)dp[i-1][ne]=max(dp[j-1][k]+v[i-1],dp[i-1][ne]);
            }
            dp[i-1][k]=dp[j-1][k];
        }
    }
    if(i*2<=min(c1,n))dfs(i*2);
    if(i*2+1<=min(c1,n))dfs(i*2+1);
}

signed main(){
    cin>>n;
    REP(i,n){I x,y;cin>>v[i]>>w[i];}
    c1=1024;c2=100000;
    dp[0][w[0]]=v[0];
    dfs(1);
    REP(i,c1)REP(j,c2)dp[i][j+1]=max(dp[i][j],dp[i][j+1]);
    I q;cin>>q;
    REP(i,q){
        I u,l;cin>>u>>l;
        vector<I> cand;
        while(u>c1){
            cand.push_back(u);
            u=u/2;
        }
        I r=cand.size();
        I ans=0;
        REP(j,1<<r){
            I v_sub=0;I w_sub=0;
            REP(k,r){
                if(j>>k&1){
                    v_sub+=v[cand[k]-1];
                    w_sub+=w[cand[k]-1];
                }
            }
            if(w_sub<=l)ans=max(ans,dp[u-1][l-w_sub]+v_sub);
        }
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 405648
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <vector>

using namespace std;

void c_colorful_leaderboard(void) {
	int n;
	int rate[9] = { 0 };
	int rate_val = 0;

	int color_min = 0;
	int color_max = 0;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> rate_val;
		if (rate_val > 3199) rate[8]++;
		else if (rate_val > 2799) rate[7]++;
		else if (rate_val > 2399) rate[6]++;
		else if (rate_val > 1999) rate[5]++;
		else if (rate_val > 1599) rate[4]++;
		else if (rate_val > 1199) rate[3]++;
		else if (rate_val > 799)  rate[2]++; // green
		else if (rate_val > 399)  rate[1]++;
		else                      rate[0]++;
	}

	for (int i = 0; i < 8; i++) {
		if (rate[i] > 0) color_min++;
	}

	color_max = color_min;

	if (color_min == 0 && rate[8] > 0) color_min++;

	color_max += rate[8];

	cout << color_min << " " << color_max << endl;
}

int main()
{
    c_colorful_leaderboard();

    return 0;
}

Measured memory_bytes: 3532
#include <bits/stdc++.h>
// D - Knapsack 1

using namespace std;

long long dp[100005];

int main() {
    int N,W,w,v,i,j;
    long long ans;

    scanf("%d%d",&N,&W);

    for (i = 1;i <= N;i++) {
        scanf("%d%d",&w,&v);
        for (j = W;j >= w;j--)
            dp[j] = max(dp[j],dp[j - w] + v);
    }

    ans = 0;
    for (i = 0;i <= W;i++)
        ans = max(ans,dp[i]);

    printf("%lld\n",ans);

    return 0;
}


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

int main() {
  int H, N;
  cin >> H >> N;
  int A[N];
  int total = 0;
  for(int i=0; i<N; i++) {
      cin >> A[i];
      total += A[i];
  }
  cout << ((total >= H)? "Yes" : "No" )<< endl;
  
}

Measured memory_bytes: 640
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    string s; cin>>s;
    ll ans=0;
    ll cntr;
    ll cntl;
    bool ok;
    rep(i,s.size()){
        cntr=0;
        cntl=0;
        ok=false;
        while(s[i]=='<'){
            i++;
            cntr++;
            ans+=cntr;
        }
        while(s[i]=='>'){
            i++;
            cntl++;
            ans+=cntl;
            ok=true;
        }
        ans-=min(cntr,cntl);
        if(ok){
            i--;
        }
        
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 900
from collections import defaultdict


def main():
    H, W = map(int, input().split())
    ans = ["#" * (W + 2)]
    for _ in range(H):
        ans += ["#" + input().strip() + "#"]
    ans += ["#" * (W + 2)]
    print("\n".join(ans))


if __name__ == '__main__':
    main()


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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
using ll = long long;

using namespace std;

ll gcd(ll x, ll y) {
    if(y == 0) return x;
    return gcd(y, x % y);
}

int main() {
    ll a, b;
    cin >> a >> b;
    if(a < b) swap(a, b);
    ll g = gcd(a, b);
    a /= g; b /= g;
    ll lcm = g * a * b;
    cout << lcm << endl;

    return 0;
}


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

int main()
{
    int n,m;
    cin >> n >> m;
    int day[m];
    for(int i=0;i<m;i++){
        cin >> day[i];
    }

    for(int i=0;i<m;i++){
        n-=day[i];
    }
    if(n<0) cout << "-1" << endl;
    else cout << n << endl;
    return 0;
}


Measured memory_bytes: 3612
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const long long mod = 1e9+7;

vector<int> Z_algorithm(string S){
  int c = 0, n = S.length();
  vector<int> Z(n,0);
  for(int i = 1; i < n; ++i){
    int l = i - c;
    if(i + Z[l] < c + Z[c]){
      Z[i] = Z[l];
    }else{
      int j = max(0, c + Z[c] - i);
      while(i + j < n && S[j] == S[i+j]) ++j;
      Z[i] = j;
      c = i;
    }
  }
  Z[0] = n;
  return Z;
}

int main(){
  string w;
  cin >> w;
  vector<int> Z = Z_algorithm(w);
  reverse(w.begin(), w.end());
  vector<int> Z_rev = Z_algorithm(w);
  int l = w.length(), t = 0;
  vector<bool> V(l,true);
  for(int i = 1; i < l; ++i){
    int x = i;
    while(x <= Z[i]) x += i, V[x] = false;
    //if(Z[i] >= i) V[2*i] = false;
    if(Z[i] < l-i) continue;
    if(not t) t = i;
  }
  //for(int i = 0; i < l; ++i) cerr << V[i] << " ";cerr << endl;
  for(int i = 1; i < l; ++i){
    int x = i;
    while(x <= Z_rev[i]) x += i, V[l-x] = false;
    //if(Z_rev[i] >= i) V[l-2*i] = false;
  }
  //for(int i = 0; i < l; ++i) cerr << V[i] << " ";cerr << endl;
  //cerr << "t = " << t << endl;
  if(not t or l%t){
    cout << 1 << endl << 1 << endl;
    return 0;
  }
  if(t == 1){
    cout << l << endl << 1 << endl;
    return 0;
  }
  cout << 2 << endl;
  long long ans = 0;
  for(int i = 1; i < l; ++i){
    ans += V[i];
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 5148
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, s, N) for(ll i{s}; i < (N); i++)
#define rem(i, N, s) for(ll i{N}; i > (s); i--)
using namespace std;using ll = long long;using ld = long double;using P = pair<ll,ll>;const int MOD = (int)1e9+7;const string rt = "\n", sp = " ";/* IO高速化 */void fastio(){ios::sync_with_stdio(false);cin.tie(NULL);}

/* ここからコード開始 */

int main(){
  fastio;
  ll N;
  cin >> N;
  if(N%2) N*=2;
  cout << N << rt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long int power(int a,int b)
{
    if(b==0)
        return 1;
    long long int k=power(a,b/2);
    if(b%2==0)
        return ((k%M)*(k%M))%M;
    else
        return ((k%M)*(k%M)*(a%M))%M;
}
long long int fact(long long int n)
{
    if(n==1 || n==0)
        return 1;
    else
        return ((n%M)*(fact(n-1)%M))%M;

}
int div(int n)
{  int c=0;
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
          if(n/i==i)
            c++;
          else
            c+=2;
        }

    }

    
    return  c;
}
int func(int n)
{
    return (n*(n+1))/2;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifndef ONLINE_JUDGE
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
   #endif
   
   string str;
   cin>>str;
   set<char> s;
   for(int i=0;i<str.length();i++)
   {
      s.insert(str[i]);
   }
   if(s.size()==26)
    cout<<"None";
  else
  { int i=0;

    for(auto it=s.begin();it!=s.end();it++,i++)
    {

        if(*it!=(97+i))
        {
            
            cout<<(char)(97+i);
            return 0;
        }
    }
    if(s.size()<26)
    {
        cout<<char(97+s.size());
    }
  }


 return 0;
}








Measured memory_bytes: 3796
#include <stdio.h>

int main() {
    int N;
    char S[100000] = {};
    int count = 0;
    int p,i;

    scanf("%d",&N);
    scanf("%s", S);

    p = 0; i = 1;

    while (p < N) {
        i = 1;
        while (S[p] == S[p+i]) {
            count++;
            i++;
        }
        p = p + i;
    }
    printf("%d\n", N - count);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include <map>
using namespace std;
typedef long long int ll;
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define all(u) u.begin(),u.end()
#define pl pair<ll,ll>
#define fi first
#define se second
#define inf 1000000007

string S;


int main() {
    cin >> S;
    ll ans = 0;
    rep(i,S.size()){
        if ((S[i] == 'A' || S[i] == 'C')|| (S[i] == 'G'|| S[i] == 'T')){
            ll temp = i;
            ll k = 1;
            while((S[temp+1] == 'A' || S[temp+1] == 'C')||( S[temp+1] == 'G'|| S[temp+1] == 'T')){
                temp++;
                k++;
                if (temp+1 >=S.size()) break;
            }
            ans = max(ans,k);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<functional>
using namespace std;
typedef long long LL;
inline LL read()
{
	LL kk=0,f=1;
	char cc=getchar();
	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}
	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}
	return kk*f;
}
int main()
{
	LL a,b,c;
	a=read();b=read();c=read();
	swap(a,b);swap(a,c);
	printf("%lld %lld %lld\n",a,b,c);
}

Measured memory_bytes: 256
module.exports=function(t){var e={};function r(n){if(e[n])return e[n].exports;var i=e[n]={i:n,l:!1,exports:{}};return t[n].call(i.exports,i,i.exports,r),i.l=!0,i.exports}return r.m=t,r.c=e,r.d=function(t,e,n){r.o(t,e)||Object.defineProperty(t,e,{enumerable:!0,get:n})},r.r=function(t){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(t,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(t,"__esModule",{value:!0})},r.t=function(t,e){if(1&e&&(t=r(t)),8&e)return t;if(4&e&&"object"==typeof t&&t&&t.__esModule)return t;var n=Object.create(null);if(r.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:t}),2&e&&"string"!=typeof t)for(var i in t)r.d(n,i,function(e){return t[e]}.bind(null,i));return n},r.n=function(t){var e=t&&t.__esModule?function(){return t.default}:function(){return t};return r.d(e,"a",e),e},r.o=function(t,e){return Object.prototype.hasOwnProperty.call(t,e)},r.p="",r(r.s=0)}([function(t,e,r){"use strict";var n=r(1);r(2)(n.readFileSync("/dev/stdin","utf8"))},function(t,e){t.exports=require("fs")},function(t,e,r){"use strict";var n=r(3),i=r(5);t.exports=function(t){var e=new n(t);i(e)}},function(t,e,r){"use strict";var n=r(4);t.exports=class{constructor(t){var e=t.trim().split(/\s+/g);this.inp=new n(e)}inr(){return this.inp.deq()}in(){return parseInt(this.inp.deq(),10)}fin(){this.inp.clear()}}},function(t,e,r){"use strict";t.exports=class{constructor(){var t=arguments.length>0&&void 0!==arguments[0]?arguments[0]:[];this.size=t.length,this.items=t,this.ind=0}enq(t){this.size+=1,this.items.push(t)}deq(){var t=this.items[this.ind];return this.size-=1,this.ind+=1,t}clear(){this.items=[],this.size=0,this.ind=0}}},function(t,e,r){"use strict";t.exports=function(t){for(var e=t.in(),r=0,n=0;n<e;n++){var i=Number(t.inr());r+="JPY"==t.inr()?i:38e4*i}console.log(r)}}]);


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

int main() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        int n, q;
        cin >> n >> q;
        dsu uf(n);
        rep(i, q) {
                int t, u, v;
                cin >> t >> u >> v;
                if (t) {
                        cout << uf.same(u, v) << '\n';
                } else {
                        uf.merge(u, v);
                }
        }
        return 0;
}


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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    string S;
    cin >> S;

    ll ans = INF;
    REP(i, S.length()-2){
        ll a, b, c;
        a = (S[i] - '0')*100;
        b = (S[i+1] - '0')*10;
        c = S[i+2] - '0';
        ll temp = a+b+c;
        ans = min(ans, abs(753-temp));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

int main(){
  ll x,y,z,k;
  cin>>x>>y>>z>>k;
  vector<ll> a(x),b(y),c(z),v;
  for(int i=0;i<x;i++)cin>>a[i];
  for(int i=0;i<y;i++)cin>>b[i];
  for(int i=0;i<z;i++)cin>>c[i];

  for(int i=0;i<x;i++){
    for(int j=0;j<y;j++){
	 v.pb(a[i]+b[j]);
    }
  }
  sort(all(v));

  priority_queue<ll> q;
  for(int i=0;i<z;i++){
    for(int j=0;j<v.size();j++){
	 if(j>k)break;
	 q.push(c[i]+v[v.size()-1-j]);
    }
  }

  ll ans=0;
  for(int i=0;i<k;i++){
    cout<<q.top()<<endl;
    q.pop();
  } 
  return 0;
}


Measured memory_bytes: 42856
#include<cstdio>
using namespace std;
#define MAX 10000
#define NIL -1

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

Node T[MAX];
int n, D[MAX], H[MAX];

void Depth(int u, int d) {
    if (u == NIL) return;
    D[u] = d;
    Depth(T[u].left, d + 1);
    Depth(T[u].right, d + 1);
}

int Height(int u) {
    int h1 = 0, h2 = 0;
    if (T[u].left != NIL)
        h1 = Height(T[u].left) + 1;
    if (T[u].right != NIL)
        h2 = Height(T[u].right) + 1;
    
    return H[u] = ( h1 > h2 ? h1:h2);

}

int Sibling(int u) {
    if (T[u].parent == NIL) return NIL;
    if (T[T[u].parent].left != u && T[T[u].parent].left != NIL)
        return T[T[u].parent].left;
    if (T[T[u].parent].right != u && T[T[u].parent].right != NIL)
        return T[T[u].parent].right;
    return NIL;
}

void print(int u) {
    int dep = 0;
    printf("node %d: ", u);
    printf("parent = %d, ", T[u].parent);
    printf("sibling = %d, ", Sibling(u));
    if (T[u].left != NIL) dep++;
    if (T[u].right != NIL) dep++;
    printf("degree = %d, ", dep);
    printf("depth = %d, ", D[u]);
    printf("height = %d, ", H[u]);
    if (T[u].parent == NIL)
        printf("root\n");
    else if (T[u].left == NIL && T[u].right == NIL)
        printf("leaf\n");
    else 
        printf("internal node\n");
}

int main() {
    int v, l, r, root = 0;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) T[i].parent = NIL;

    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &v, &l, &r);
        T[v].left = l;
        T[v].right = r;
        if (l != NIL) T[l].parent = v;
        if (r != NIL) T[r].parent = v;
    }

    for (int i = 0; i < n; i++) {
        if (T[i].parent == NIL)
            root = i;
    }

    Depth(root, 0);
    Height(root);
    
    for (int i = 0; i < n; i++)
        print(i);
    
    return 0;
}





Measured memory_bytes: 2748
#![allow(unused_imports, unused_variables, dead_code)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

trait InputValue {
    fn parse(s: &str) -> Self;
}

fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

const MOD: i64 = 1e9 as i64 + 7;

fn powmod(a: i64, p: usize, m: i64) -> i64 {
    let mut ret = 1i64;
    let mut aa = a;
    let mut pp = p;
    while pp >= 1 {
        if pp & 1 == 1 {
            ret *= aa;
            ret %= m;
        }
        aa = aa * aa % m;
        pp >>= 1;
    }
    ret
}

fn inv(a: i64, m: usize) -> i64 {
    powmod(a, m-2, m as i64)
}

fn main() {
    let (n, k): (usize, i64) = read();

    let ans = 0;

    let mut divisors = vec![];
    for d in 1..n+1 {
        let d2 = d * d;
        if d2 == n {
            divisors.push(d);
            break;
        } else if d2 > n {
            break;
        }
        if n % d == 0 {
            divisors.push(d);
            divisors.push(n / d);
        }
    }
    divisors.sort();

    let dn = divisors.len();

    let mut dp = vec![0; dn];
    for i in 0..dn {
        let d = divisors[i];
        let mut sum = powmod(k, (d + 1) / 2, MOD);
        for j in 0..i {
            if d % divisors[j] == 0 {
                sum += MOD - dp[j]
            }
        }
        sum %= MOD;
        dp[i] = sum;
    }

    let mut ans = 0;
    for i in 0..dn {
        let d = divisors[i] as i64;
        if d % 2 == 0 {
            ans += dp[i] * (d / 2) % MOD;
        } else {
            ans += dp[i] * d % MOD;
        }
        ans %= MOD;
    }
    println!("{}", ans);
}



Measured memory_bytes: 4476
N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp = map(int, raw_input().split())
    if 1 == temp[0]:
        a.append(temp[1])
    elif N == temp[1]:
        b.append(temp[0])

if any(list(set(a) & set(b))):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

#ifdef _DEBUG
#define ASSERT(x) assert(x)
#define DLOG(x) cout << __LINE__ << ": " << x << endl;
#else
#define ASSERT(x)
#define DLOG(x)
#endif
#define DLOG_V(x) DLOG(#x << ": " << x)

using namespace std;

vector<int> read(int n) {
  vector<int> res;
  for (int i = 0; i < n; ++i) {
    int t;
    cin >> t;
    res.push_back(t - 1);
  }
  return res;
}

template <typename It> class Node {
public:
  Node(It begin, It end) : begin_{begin}, end_{end} {
    DLOG_V(*begin);
    DLOG_V(*(end - 1));
  }

  template <typename IndexMap> void setRoot(It root, IndexMap& m) {
    ASSERT(root != end_);
    root_ = *root;
    if (begin_ != root) {
      left_ = make_unique<Node>(begin_, root);
      for (auto c = begin_; c != root; ++c) {
        m[*c] = left();
      }
    }
    if (root + 1 != end_) {
      right_ = make_unique<Node>(root + 1, end_);
      for (auto c = root + 1; c != end_; ++c) {
        m[*c] = right();
      }
    }
  }

  int root() const { return root_; }

  auto left() const { return left_.get(); }
  auto right() const { return right_.get(); }

private:
  It begin_;
  It end_;
  int root_{-1};
  unique_ptr<Node> left_;
  unique_ptr<Node> right_;
};

template <typename Container>
static Node<typename Container::const_iterator> makeNode(Container& container) {
  return {container.begin(), container.end()};
}

template <typename T, typename C>
auto postOrder(T& result, const Node<C>* node) {
  if (!node)
    return;
  postOrder(result, node->left());
  postOrder(result, node->right());
  result.push_back(node->root());
}

int main() {
  int n;
  cin >> n;
  auto pre = read(n);
  auto in = read(n);
  auto root = makeNode(in);
  vector<decltype(root)*> nodes(n, &root);
  for (auto&& i : pre) {
    auto it = std::find(in.begin(), in.end(), i);
    ASSERT(it != in.end());
    auto& node = *nodes[*it];
    node.setRoot(it, nodes);
  }
  vector<int> result;
  postOrder(result, &root);

  bool first{true};
  for (auto&& r : result) {
    if (first) {
      first = false;
    } else {
      cout << " ";
    }
    cout << (r + 1);
  }
  cout << endl;
}



Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[200010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	if(b>a)return 0;
	if(a==b)return 1;
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
int n,a[200010],b[200010],ans=0;
signed main(){
	cin>>n;
	rep(i,n)cin>>a[i];
	rep(i,n)cin>>b[i];
	while(1){
		bool can=false;
		bool flag=true;
		rep(i,n){
			if(b[i]!=a[i])flag=false;
			if(i==0){
				int B=b[i+1]+b[n-1];
				if(b[i]-B<a[i])continue;
				ans+=(b[i]-a[i])/B;
				b[i]=(b[i]-a[i])%B+a[i];
				can=true;
			}
			else if(i==n-1){
				int B=b[i-1]+b[0];
				if(b[i]-B<a[i])continue;
				ans+=(b[i]-a[i])/B;
				b[i]=(b[i]-a[i])%B+a[i];
				can=true;
			}
			else{
				int B=b[i-1]+b[i+1];
				if(b[i]-B<a[i])continue;
				ans+=(b[i]-a[i])/B;
				b[i]=(b[i]-a[i])%B+a[i];
				can=true;
			}
		}
		if(flag)break;
		if(!can){
			puts("-1");
			return 0;
		}
		
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
#pragma GCC optimize ("Ofast")
#define ll long long
#define pll pair<long long,long long>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define forn(i, n) for(int i=0; i<int(n); i++)
#define Forn(i, n) for(int i=1; i<=int(n); i++)

using namespace std;

/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
typedef tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;*/

int n;
int a[200010];

int main()
{
    cin.tie(0); ios_base::sync_with_stdio(false);
    //freopen("connect_the_dots.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin >> n;
    forn(i, n)
    {
        int x;
        cin >> x;
        a[i] = x;
    }
    int maxid = max_element(a, a+n) - a;
    int maxval = a[maxid];
    int secmax = -1;
    forn(i, n)
    {
        if(i!=maxid) secmax = max(secmax, a[i]);
    }
    forn(i, n)
    {
        if(i!=maxid) cout << maxval << endl;
        else cout << secmax << endl;
    }
}



Measured memory_bytes: 2432