akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;

const int mod = 1e9 + 7;

const int nax = 2e5 + 5;
int fac[nax], inv_fac[nax];

int mul(int a, int b) {
    return (ll) a * b % mod;
}
int my_pow(int a, int b) {
    int r = 1;
    while(b) {
        if(b % 2) {
            r = mul(r, a);
        }
        a = mul(a, a);
        b /= 2;
    }
    return r;
}
int my_inv(int a) {
    return my_pow(a, mod - 2);
}

int binomial(int a, int b) {
    if(a < 0 || b < 0 || b > a) {
        return 0;
    }
    return mul(fac[a], mul(inv_fac[b], inv_fac[a-b]));
}

int f(int a, int b) {
    int tmp = binomial(a + b, b);
    //~ debug() << imie(a) imie(b) imie(tmp);
    return tmp;
}

int sub(int a, int b) {
    return (a - b + mod) % mod;
}

int main() {
    fac[0] = inv_fac[0] = 1;
    for(int i = 1; i < nax; ++i) {
        fac[i] = mul(fac[i-1], i);
        inv_fac[i] = my_inv(fac[i]);
    }
    int h, w, n;
    scanf("%d%d%d", &h, &w, &n);
    vector<pair<int,int>> in(n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &in[i].first, &in[i].second);
    }
    sort(in.begin(), in.end(), [&](pair<int,int> a, pair<int,int> b) {
        return a.first + a.second < b.first + b.second;
    });
    // dp[i] - the number of paths to vertex in[i] such that it's the first
    // forbidden vertex
    
    in.emplace_back(h, w);
    
    vector<int> dp(n + 1);
    for(int i = 0; i <= n; ++i) {
        int tmp = f(in[i].first - 1, in[i].second - 1);
        debug() << imie(tmp);
        for(int j = 0; j < i; ++j) {
            if(in[j].first <= in[i].first && in[j].second <= in[i].second) {
                tmp = sub(tmp, mul(dp[j], f(in[i].first - in[j].first, in[i].second-in[j].second)));
            }
        }
        dp[i] = tmp;
    }
    debug() << imie(dp);
    printf("%d\n", dp[n]);
}


Measured memory_bytes: 5312
#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 M 998244353
#define ll long long
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define REPI(i,a,b) for(ll i=b-1;i>=a;i--)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define G(a,b) get<a>(b)
#define VI vector<int>
#define VLL vector<long long>
 
#define o_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define o_setll tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
 
ll modI(ll a, ll m);
ll gcd(ll a, ll b);
ll powM(ll x, unsigned ll y, unsigned ll m);
void pairsort(int a[], int b[], int n);
void pairsortll(ll a[],ll b[],ll n);
ll logint(ll x,ll y);
 
 
ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}
 
ll powM(ll x,ll y,ll m)
{
    if(y==0) return 1;
    ll p=powM(x,y/2,m)%m;
    p=(p*p)%m;
    return (y%2==0)?p:(x*p)%m;
}
 
ll modI(ll a, ll m)
{
    ll m0=m,y=0,x=1;
    if(m==1) return 0;
    while(a>1)
    {
        ll q=a/m;
        ll t=m;
        m=a%m;
        a=t;
        t=y;
        y=x-q*y;
        x=t;
    }
    if(x<0) x+=m0;
    return x;
}
 
void pairsort(int a[],int b[],int n)
{
    pair<int,int> v[n];
    REP(i,0,n)
    {
        v[i].F=a[i];
        v[i].S=b[i];
    }
    sort(v,v+n);
    REP(i,0,n)
    {
        a[i]=v[i].F;
        b[i]=v[i].S;
    }
}
 
void pairsortll(ll a[],ll b[],ll n)
{
    pair<ll,ll> v[n];
    REP(i,0,n)
    {
        v[i].F=a[i];
        v[i].S=b[i];
    }
    sort(v,v+n);
    REP(i,0,n)
    {
        a[i]=v[i].F;
        b[i]=v[i].S;
    }
}
 
ll logint(ll x,ll y)
{
    ll ans=0;
    ll a=1;
    for(ll i=0;i<=x;i++)
    {
        if(x<a)
        {
            return ans;
        }
        ans++;
        a*=y;
    }
    return -1;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    /*
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    */
 
    ll q=1;
    //cin>>q;
    while(q--)
    {
        ll n;
        cin>>n;
        ll fct[n+5];
        fct[0]=1;
        REP(i,1,n+5)
        {
            fct[i]=fct[i-1]*2;
            fct[i]%=M;
        }
        pair<ll,ll> x1[n];
        ll x2[n];
        REP(i,0,n)
        {
            ll t1,t2;
            cin>>t1>>t2;
            x1[i]=MP(t1,t2);
            x2[i]=t2;
        }
        sort(x1,x1+n);
        sort(x2,x2+n);
        ll ans=0;
        o_setll v;
        REP(i,0,n)
        {
            v.insert(x1[i].S);
            ll a=v.order_of_key(x1[i].S);
            ll b=lower_bound(x2,x2+n,x1[i].S)-x2-a;
            ll d=i-a;
            ll c=n-a-b-d-1;
            ans+=fct[n]-fct[a+b]-fct[b+c]-fct[c+d]-fct[d+a]+fct[a]+fct[b]+fct[c]+fct[d];
            ans%=M;
            if(ans<0) ans+=M;
        }
        cout<<ans-n;
    }
 
    return 0;
}

Measured memory_bytes: 19072
import java.util.Scanner;
 
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int a = sc.nextInt();
            int b = sc.nextInt();
             
            if (a==b){
                System.out.println("a == b");
            }
            else if( a < b){
                System.out.println("a < b");
            }
            else {
                System.out.println("a > b");
            }           
        }
    }
}

Measured memory_bytes: 17160
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <climits>
using namespace std;

const int maxn = 10002;
const int maxm = 20002;

typedef pair<int, int> P;
struct Edge {
    int to, d, c;
    Edge() {}
    Edge(int t, int d, int c) : to(t), d(d), c(c) {}
};

vector<Edge> g[maxn];
int dis[maxn];
int cf[maxn];

int main() {
    //freopen("aoj2249.txt", "r", stdin);
    while (1) {
        int n, m;
        scanf("%d%d", &n, &m);
        if (!n) break;

        for (int i = 1; i <= n+1; i++) {
            g[i].clear();
        }
        for (int i = 0; i < m; i++) {
            int f, t, d, c;
            scanf("%d%d%d%d", &f, &t, &d, &c);
            g[f].push_back(Edge(t, d, c));
            g[t].push_back(Edge(f, d, c));
        }

        fill(dis, dis+n+1, INT_MAX);
        fill(cf, cf+n+1, -1);
        dis[1] = 0;
        cf[1] = 0;

        priority_queue<P, vector<P>, greater<P>> q;
        q.push(P(0, 1));
        while (!q.empty()) {
            P p = q.top();
            q.pop();
            int d = p.first;
            int idx = p.second;
            if (d > dis[idx]) continue;
            for (int i = 0; i < (int) g[idx].size(); i++) {
                Edge& e = g[idx][i];
                if (dis[idx] != INT_MAX && dis[idx] + e.d < dis[e.to]) {
                    dis[e.to] = dis[idx] + e.d;
                    cf[e.to] = e.c;
                    q.push(P(dis[e.to], e.to));
                } else if (dis[idx] != INT_MAX && dis[idx] + e.d == dis[e.to]) {
                    if (e.c < cf[e.to])
                        cf[e.to] = e.c;
                    //q.push(P(dis[e.to], e.to));
                }
            }
        }

        int res = 0;
        for (int i = 2; i <= n; i++) {
            res += cf[i];
        }
        printf("%d\n", res);
    }
    return 0;
}

Measured memory_bytes: 3264
#include <bits/stdc++.h>
using namespace std;
string s1="Sunny", s2="Cloudy", s3="Rainy", s;
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> s;
if (s==s1) cout << s2;
if (s==s2) cout << s3;
if (s==s3) cout << s1;
return 0;
}


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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

//MOD
//--------------------------------------------
#define MUL(a,b) (((a) % MOD) * ((b) % MOD)) % MOD

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//main code

int main(int argc, char const* argv[])
{
	int n;
	cin >> n;
	int yo = n;
	if (n&1) { // 奇数
		yo--;
	}
	set<PLL> edges;
	for (int i = 1; i <= n; i++) {
		for (int j = i+1; j <= n; j++) {
			edges.insert({i,j});
		}
	}
	for (int i = 1; yo > 0; i++) {
		edges.erase({i, yo});
		yo--;
	}
	cout << edges.size() << endl;
	for (auto&& var : edges) {
		cout << var.first << " " << var.second << endl;
	}
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <cmath>

using namespace std;

int main()
{
    int d, n;
    int dp[200][200]={0};
    int temp[200];
    int cloth[200][3];
    int m;
    list<int> suit;
    cin >> d >> n;
    for(int i=0;i<d;++i) cin >> temp[i];
    for(int i=0;i<n;++i) cin >> cloth[i][0] >> cloth[i][1] >> cloth[i][2];
    for(int i=0;i<n;++i)
    {
        if(!(cloth[i][0] <= temp[0] && temp[0] <= cloth[i][1])) dp[0][i] = -400000;
    }
    for(int i=1;i<d;++i)
    {
        for(int j=0;j<n;++j)
        {
            m=0;
            for(int k=0;k<n;++k)
            {
                if(cloth[j][0] <= temp[i] && temp[i] <= cloth[j][1])
                {
                    m = max(m, dp[i-1][k] + abs(cloth[k][2]-cloth[j][2]));
                }
            }
            dp[i][j] = m;
        }
    }
    m=0;
    for(int i=0;i<n;++i) m = max(m,dp[d-1][i]);
    cout << m << endl;
}

Measured memory_bytes: 1328
# ABC_088_B_Card_Game_for_two.py
N=int(input())
a=list(map(int, input().split()))
a.sort( reverse= True)

ScoreAlice=0
ScoreBob=0
for i in range (0,N):
	if i%2==0: #Alice
		ScoreAlice+=a[i]
	else: #Bob
		ScoreBob+=a[i]
print(ScoreAlice-ScoreBob)


Measured memory_bytes: 61892
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

class Program{
  public static void Main(){

    int n = int.Parse(Console.ReadLine());
    var input = Console.ReadLine().Split();
    var a = new int[n];
    long total = 0;
    for(int i=0;i<n;i++){
      a[i] = int.Parse(input[i]);
      total += a[i];
    }
    
    long x=0,y=total;
    long min = Math.Abs(total - a[0]*2);
    for(int i=0; i<n-1; i++){
      x += a[i];
      y -= a[i];
      min = Math.Min(Math.Abs(x-y),min);
    }
    Console.WriteLine(min);
  }
}


Measured memory_bytes: 29672
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<string>
//#include<string>
//#include<sstream>
using namespace std;
int main()
{
	int k,s;
	scanf("%d%d",&k,&s);
	int i,j,b,sum=0;
	for(i=0;i<=k;i++){
		for(j=0;j<=k&&j<=s-i;j++){
			if(s-i-j<=k) sum++;
		}
	}
	printf("%d\n",sum);
}

Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int W[N] = {}, R[N] = {};
int n;
char arr[N] = {};
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    for (int i = 1; i <= n; i++) {
        W[i] = W[i - 1] + (arr[i] == 'W');
        R[n + 1 - i] = R[n + 2 - i] + (arr[n + 1 - i] == 'R');
    }
    int ans = n;
    for (int i = 0; i <= n; i++)
        ans = min(ans, max(W[i], R[i + 1]));
    cout << ans << '\n';
    return 0;
}

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<bool> VB;



//REPEAT
//------------------------------------------
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define RFOR(i, m, n) for(int i = m;i > n;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,m)  RFOR(i,m,0)

//container util
//------------------------------------------
#define pb(a) push_back(a)
#define SORT(V) sort((V).begin(),(V).end())
#define REV(V) reverse((V).begin(),(V).end())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//def function
//------------------------------------------

int dp[101][4][4][4]; //AGCT -> 0123
//main
//------------------------------------------

signed main(){
  int N;
  cin >> N;
  //333Sと考える
  dp[0][3][3][3]=1;

  REP(len, N){
    REP(i, 4){
      REP(j, 4){
        REP(k, 4){
          if(dp[len][i][j][k]==0) continue;
          REP(l, 4){
            //ダメなのは，012，102，021，0*12，01*2
            if(j==0 && k==1 && l==2) continue;
            if(j==1 && k==0 && l==2) continue;
            if(j==0 && k==2 && l==1) continue;
            if(i==0 && k==1 && l==2) continue;
            if(i==0 && j==1 && l==2) continue;

            dp[len+1][j][k][l]+=dp[len][i][j][k];
            dp[len+1][j][k][l]%=MOD;
          }
        }
      }
    }
  }
  int ans=0;
  REP(i, 4){
    REP(j, 4){
      REP(k, 4){
        ans+=dp[N][i][j][k];
      }
    }
  }
  ans%=MOD;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	/*/TODO:!!!!!!!テスト用!!!!!!!!!
	sc = bufio.NewScanner(strings.NewReader(`

				`))
	//TODO:!!!!!!!テスト用!!!!!!!!!*/

	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush() // !!!!caution!!!! you must use Fprint(out, ) not Print()
	/* --- code --- */
	//fmt.Fprintln(out, "[DEBUG]", time.Now())

	n := nextInt()
	a := nextInt()
	b := nextInt()

	ans := (b-a)*(n-2) + 1
	if ans < 0 {
		ans = 0
	}

	//	fmt.Fprintln(out, "[DEBUG]]", a)
	fmt.Fprintln(out, ans)
}

//------------------------------------------------------------------------------

// -*-*-*-*-*-*-*-*-
// * I/O utilities *
// -*-*-*-*-*-*-*-*-

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

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

func chars(s string) []string {
	ret := make([]string, len([]rune(s)))
	for i, v := range []rune(s) {
		ret[i] = string(v)
	}
	return ret
}

func absInt(x int) int {
	return int(math.Abs(float64(x)))
}


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

int main() {
  int n,m; cin>>n>>m;
  cout<<(1900*m+100*(n-m))*pow(2,m);
  
}

Measured memory_bytes: 256
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

n=int(input())

for i in range(n,1000001):
    if is_prime(i):
        print(i)
        break

Measured memory_bytes: 3060
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCorder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            // 解答はココに書く
            var X = cin.ReadIntArray(3);
            WriteLine(X.Sum() - X.Max());
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}


Measured memory_bytes: 13396
n=int(input())
s=[]
p=[]
for i in range(n):
    S,P=input().split()
    s.append([S,int(P),int(i)+1])
    p.append(int(P))
A=s[::]
A.sort(key=lambda A:(A[1],A[0]),reverse=True)
A.sort(key=lambda A:(A[0]))
for i in range(n):
    print(A[i][2])

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int t,n,i,j;
    string s,ss;
    cin>>s;
    if(s[0]>=97 and s[0]<=122)cout<<"a"<<endl;
    else cout<<"A"<<endl;
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3588
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
		string[] input = Console.ReadLine().Split(' ');//Splitで区切り文字を指定して複数個受け取る。
		long n = long.Parse(input[0]);
		long m = long.Parse(input[1]);
		long answer = 0;

    if(n >= 2 && m >= 2) answer = (n-2)*(m-2);
    else if(n == 1 && m >= 2) answer = m-2;
    else if(n >= 2 && m == 1) answer = n-2;
    else if(n == 1 && m == 1) answer = 1;

		Console.WriteLine(answer);//WriteLineをWriteとすると、改行なしで出力。
	}
}

Measured memory_bytes: 11092
n = gets.to_i
c = Hash.new(0)
0.upto(n) do |i|
  s = i.to_s
  c["#{s[0]}#{s[-1]}"] += 1
end
ans = 0
1.upto(9) do |i|
  1.upto(9) do |j|
    ans += c["#{i}#{j}"] * c["#{j}#{i}"]
  end
end
p ans


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
int main()
{
    ll n,k;
    cin>>n>>k;
    ll a[n+1];
    ll i,j;
    a[0]=1;
    for(i=1;i<=n;i++)
        cin>>a[i];
    map<ll,ll> mp;
    bool f = true;
    vector<ll> v;
    v.pb(1);
    mp[1]=1;
    ll prev = a[1];
    while(f)
    {
        if(mp.find(prev)!=mp.end())
            break;
        mp[prev]=1;
        v.pb(prev);
        prev = a[prev];
    }
    // for(i=0;i<v.size();i++)
    //     cout<<v[i]<<" ";
    // cout<<"\n"<<prev<<"\n";
    i = 0;
    while(v[i]!=prev)
    {
        i++;
        k--;
        // cout<<i<<" ";
        if(k==0)
        {
            cout<<v[i];
            return 0;
        }
    }
    // k++;
    // cout<<"\n";
    // cout<<i<<"\n";
    // ll t = k%(v.size()-(i-1));
    ll t;
    if(i==0){
        t = k%v.size();
        cout<<v[t];
    }
    else{
        t = k%(v.size()-i);
        cout<<v[t+i];
    }
}

Measured memory_bytes: 18612
{-# LANGUAGE BangPatterns #-}
import Data.List
import qualified Data.ByteString.Char8 as BS

main = do
  n <- readLn :: IO Int
  [a,b] <- map (read . BS.unpack) . BS.words <$> BS.getLine
  ps <- map (read . BS.unpack) . BS.words <$> BS.getLine
  let solve :: Int -> Int -> Int -> [Int] -> Int
      solve !na !nb !nc [] = min na (min nb nc)
      solve !na !nb !nc (x:xs)
        | x <= a = solve (na + 1) nb nc xs
        | x <= b = solve na (nb + 1) nc xs
        | otherwise = solve na nb (nc + 1) xs
  print $ solve 0 0 0 ps


Measured memory_bytes: 1020
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define NMAX 2000
#define MOD 1000000007
#define INF 2000000000

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

using namespace std;

int n, m;
int mat[NMAX][NMAX];
int workMat[NMAX][NMAX];
int sumMat[NMAX][NMAX];

void ReloadMat()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			workMat[i][j] = mat[i][j];
		}
}

int main()
{
	cin >> n >> m;
	cin.get();
	for (int i = 0; i < n; i++)
	{
		char line[NMAX];
		cin.getline(line, NMAX + 1);
		for (int j = 0; j < m; j++)
		{
			if (line[j] == '#')
				mat[i][j] = -1;
		}
	}

	// left to right
	ReloadMat();
	for(int i = 0; i < n; i++)
		for (int j = 1; j < m; j++)
		{
			if (workMat[i][j] != -1)
				workMat[i][j] = workMat[i][j - 1] + 1;
			sumMat[i][j] += workMat[i][j];
		}

	// right to left
	ReloadMat();
	for (int i = 0; i < n; i++)
		for (int j = m - 2; j >= 0; j--)
		{
			if (workMat[i][j] != -1)
				workMat[i][j] = workMat[i][j + 1] + 1;
			sumMat[i][j] += workMat[i][j];
		}

	// top to bottom
	ReloadMat();
	for (int i = 1; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (workMat[i][j] != -1)
				workMat[i][j] = workMat[i - 1][j] + 1;
			sumMat[i][j] += workMat[i][j];
		}

	// bottom to top
	ReloadMat();
	for (int i = n - 2; i >= 0; i--)
		for (int j = 0; j < m; j++)
		{
			if (workMat[i][j] != -1)
				workMat[i][j] = workMat[i + 1][j] + 1;
			sumMat[i][j] += workMat[i][j];
		}

	int lampMax = -1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			lampMax = MAX(lampMax, sumMat[i][j] + 1);
	}
	cout << lampMax << '\n';
	return 0;
}

Measured memory_bytes: 47104
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr = input.trim().split("\n");
var q=arr.shift()-0;
var str="";
var map = new Map();
for(var i=0;i<q;i++){
   var [a,b,c]=arr[i].split(" ");
   if(a=="0")map.set(b,c);
   else if(a=="1")str+=((map.has(b)) ? map.get(b) : "0") + "\n";
   else map.delete(b);
}
console.log(str.trim());


Measured memory_bytes: 88524
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
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)
typedef long long ll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

//aとbのうち大きい値をaとして採用する
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false;}

int main(){
    int N,W; cin>>N>>W;
    vector<int> w(N);
    vector<int> v(N);
    rep(i,N)cin>>w[i]>>v[i];

    vector<vector<ll>> dp(N+1,vector<ll> (W+1,0));

    //rep(i,N+1){rep(j,W+1)cout<<dp[i][j]<<' '; cout<<endl;}

    for(int i = 1; i<=N; i++){
        for(int j = 0; j<=W; j++){
            chmax(dp[i][j], dp[i-1][j]);
            if(w[i-1]<= j) chmax(dp[i][j], dp[i-1][j-w[i-1]]+v[i-1]);
        }
    }
    //cout<<"----------"<<endl;
    //rep(i,N+1){rep(j,W+1)cout<<dp[i][j]<<' '; cout<<endl;}
    cout<<dp[N][W]<<endl;return 0;
}


Measured memory_bytes: 80256
from fractions import gcd

def solve():
    n = int(input())
    a = list(map(int,input().split()))
    x = 1
    for ai in a:
        x = (x * ai) // gcd(x, ai)
    ans = sum([x // ai for ai in a])
    print(ans % 1000000007)

if __name__ == "__main__":
    solve()


Measured memory_bytes: 264672
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    string s;
    cin >> s;
    cout << s.substr(0, 3) << endl;
}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)

int main()
{
  int n;
  long long ans=0;
  cin >> n;
  rep(i,n-1)
    ans+=(n-1)/(i+1);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    r = int(input())
    print(3*(r**2))

Measured memory_bytes: 5712
#include <cstdio>
#include <cassert>
#include <algorithm>    
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <bitset>
#define pb push_back
#define mk make_pair
#define int long long
#define eb emplace_back
#define eps 1e-8
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()


using namespace std;
typedef long double ld;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef tuple<int, int, int> tiii;
typedef vector<int> vii;
typedef vector<long double> vd;
const int inf = 1e9;
const int INF = 1e18;
const int M = 1e9 + 7;

const int maxn = 2e5;
pii a[maxn];
set<int> s[maxn];
std::vector<int> v[maxn], vv[maxn];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<maxn> uf;

signed main()
{
#ifndef ONLINE_JUDGE
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	int n;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i].fi >> a[i].se;
	}
	sort(a, a + n);
	int cur = a[0].fi, i = 0, res = 0, dep = 0;
	while(i < n){
		++dep;
		while(i < n && a[i].fi == cur){
			v[a[i].se].pb(dep);
			s[dep].insert(a[i].se);
			++i;
		}
		cur = a[i].fi;
	}
	for(int i = 1; i <= 1e5; ++i){
		if((int)v[i].size() < 2) continue;
		for(int j = 1; j < (int)v[i].size(); ++j){
			uf(v[i][j], v[i][0]);
		}
	}
	for(int i = 1; i <= 1e5; ++i){
		vv[uf[i]].pb(i);
	}
	for(int i = 1; i <= 1e5; ++i){
		if((int)vv[i].size() > 1){
			set<int> t;
			int tot = 0;
			for(int j : vv[i]){
				for(int k : s[j]){
					t.insert(k);
					++tot;
				}
			}
			res += (int)vv[i].size() * (int)t.size() - tot;
		}
	}
	cout << res << endl;



    
	return 0;
}

Measured memory_bytes: 34672
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

vll divisor(ll n) {
    vll ans;
    for (ll i = 1; i*i <= n; ++i) {
        if (n%i == 0) {
            ans.push_back(i);
            //if (i*i != n) ans.push_back(n/i);
        }
    }
    sort(all(ans));
    return ans;
}

int main() {
    ll n;
    cin >> n;

    vll g = divisor(n);
    ll ans = 0; 
    rep(i, g.size()) {
        if (g[i] * g[i] >= n) break;
        ll tmp = n / g[i] - 1;
        if (n % tmp != 0) ans += tmp;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	vector<set<int>> s(m);
	rep(i, m){
		int k;
		cin >> k;
		rep(j, k){
			int in;
			cin >> in;
			in--;
			s.at(i).insert(in);
		}
	}
	vector<int> p(m);
	rep(i, m){
		int in;
		cin >> in;
		p.at(i) = in;
	}

	int ans = 0;
	rep(bit, 1 << n){
		bool flag = true;
		vector<int> d(n);
		rep(i, n){
			if((bit & (1 << i)) == 0) d.at(i) = 0;
			else d.at(i) = 1;
		}
		
		// rep(i, n){
		// 	cerr << d.at(i) << " ";
		// }
		// cerr << endl;

		rep(i, m){
			int fl = p.at(i);
			int tt = 0;
			rep(j, n){
				if(s.at(i).count(j) == 0) continue;
				tt = (tt + d.at(j)) % 2;
			}
			if(tt != fl){
				// cerr << bit << " " << i << endl;
				flag = false;
			}
		}
		if(flag == true) ans++;
	}
	cout << ans << endl;
	return 0;
}

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

#define ll long long
#define FASTIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ii pair < ll , ll >
#define all(x) std::begin(x), std::end(x)

ll const MAX = 100005 ;
ll const INF = 1e9 ;
ll const mod = 1000000007 ;


ll dp[MAX][3] ;
ll a[MAX][3] ;
ll n ;
int k ;

ll cost ( int ndx , int ac )
{
    if ( ndx >= n )
        return 0 ;

    ll &ret = dp[ndx][ac] ;
    if ( ret != -1 )
        return ret ;

    return ret = max ( a[ndx][(ac+1)%3] + cost ( ndx + 1 , ( ac + 1 ) % 3 ) , a[ndx][(ac+2)%3] + cost ( ndx + 1 , ( ac + 2 ) % 3 ) ) ;
}


int main ()
{
    //freopen ( "portals.in" , "r" , stdin ) ;
    FASTIO ;

    cin >> n ;
    memset ( dp , -1 , sizeof dp ) ;
    for ( int i = 0 ; i < n ; i ++ )
        cin >> a[i][0] >> a[i][1] >> a[i][2] ;

    ll ans = 0 ;
    for ( int i = 0 ; i < 3 ; i ++ )
        ans = max ( ans , cost ( 0 , i ) ) ;
    cout << ans ;


}


Measured memory_bytes: 9600
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

signed main() {
	pair<double, int> a[3][8] = {};
	pair<double, int> b[18] = {};
	rep(i, 0, 3) {
		rep(j, 0, 8) { cin >> a[i][j].second >> a[i][j].first; }
		sort(a[i], a[i] + 8);
		rep(j, 2, 8) { b[i * 6 + (j - 2)] = a[i][j]; }
		rep(j, 0, 2)cout << a[i][j].second << " " << a[i][j].first << endl;
	}
	sort(b, b + 18);
	rep(i, 0, 2)cout << b[i].second << " " << b[i].first << endl;
	return 0;
}

Measured memory_bytes: 3176
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n, k = readmi()
ans = 0
l = int(math.ceil(math.log2(k)))
for i in range(1, n + 1):
    s = 1 / (n)
    p = i
    t = 1
    for j in range(l):
        if p >= k:
            break
        p = p * 2
        t /= 2
    ans += (s * t)
print(ans)

Measured memory_bytes: 6608
from heapq import heapify,heappop,heappush
que = []
heapify(que)
N = int(input())
S =[]
for i in range(0,N,1):
    S.append(input())
S.sort()
count=1
max_count =0
pre = S[0]
for i in range(1,N,1):
    if S[i]==pre:
        count+=1
    else:
        count=1
    if max_count < count:
        max_count = count
    pre = S[i]

count=1
pre = S[0]
for i in range(1,N,1):
    if S[i]==pre:
        count+=1
    else:
        if count ==max_count:
            print(pre)
        count=1
    pre = S[i]

if count ==max_count:
            print(pre)

Measured memory_bytes: 74584
#include <bits/stdc++.h>
 
typedef long long ll;
const int INFI = (1 << 29);
const ll INFL = (1LL << 62);
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) int(x.size())
#define FIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define forn(tourBina, n) for(ll tourBina = 0; tourBina < n; tourBina++)
#define fore(tourBina, l, r) for(ll tourBina = l; tourBina <= r; tourBina++)
#define DBG(x) cerr << #x << " = " << x << endl
#define pb(x) push_back(x)

using namespace std;

void solve()
{
    vector < vector < ll > > v(3, vector < ll >(3));
    
    forn(i, 3)
        forn(j, 3)
            cin >> v[i][j];
            
    ll n;
    
    cin >> n;
    
    while(n--)
    {
        ll val;
        
        cin >> val;
        
        forn(i, 3)
            forn(j, 3)
                if(v[i][j]==val)
                    v[i][j]=0;
    }
    
    forn(i, 3)
    {
        if((!v[i][0]&&!v[i][1]&&!v[i][2]) || (!v[0][i]&&!v[1][i]&&!v[2][i]))
        {
            cout << "Yes\n";
            
            return;
        }
    }
    
    if((!v[0][0]&&!v[1][1]&&!v[2][2]) || (!v[0][2]&&!v[1][1]&&!v[2][0]))
    {
        cout << "Yes\n";
            
        return;
    }
    
    cout << "No\n";
}

int main()
{
	FIO;
	
	#ifdef tourBina
        //freopen("input.in", "r", stdin);
	#endif
    
    solve();
    
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <numeric>
#include <climits>
#define M 1000000007
#define ll long long
#define LIM 100000
using namespace std;
ll v[LIM];
int main() {
  string a, b, c;
  cin >> a >> b >> c;
  cout << a[0] << b[0] << c[0] << endl;
  return 0;
}


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

int main() {
    int n;
    cin >> n;
    long long int s[n];
    s[0] = 2;
    s[1] = 1;
    for (int i = 2; i <= n; i++) {
        s[i] = s[i - 2] + s[i - 1];
    }

    cout << s[n] << endl;
    return 0;
}

Measured memory_bytes: 256
n, d = map(int, input().split())
# xy = []
c = 0
for i in range(n):
    # xy.append([*map(int, input().split())])
    x, y = map(int, input().split())
    if x*x + y*y <= d*d:
        c += 1

print(c)
# print(n,d)
# print(*xy,sep='\n')


Measured memory_bytes: 9172
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

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

Measured memory_bytes: 256
n = input()
hon = ['2', '4', '5', '7', '9']
pon = ['0', '1', '6', '8']
bon = ['3']
out = ''

if n[-1] in hon:
  out = 'hon'
elif n[-1] in pon:
  out = 'pon'
else:
  out = 'bon'

print(out)

Measured memory_bytes: 9064
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <tuple>
#include <vector>
#include <bitset>
#include <stack>
typedef long long ll;
typedef unsigned long long ull;
#define mk make_pair

using namespace std;
const int N = 100000;
vector<vector<int>> fs, bs;
int ans[N], comp[N]; bool was[N], was2[N];
int cnt;

void dfs(int u, int c) {
    was[u] = true;
    comp[u] = c;
    cnt++;
    for (int v : fs[u])
        if (!was[v]) dfs(v, c);
}

void dfs_ans(int u) {
    was2[u] = true;
    ans[u] = cnt - fs[u].size() - 1;
    for (int v : bs[u])
        if (comp[v] == comp[u]) ans[u]--;
    for (int v : fs[u])
        if (!was2[v]) dfs_ans(v);
}

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        bs.push_back(vector<int>());
        fs.push_back(vector<int>());
    }

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        fs[a].push_back(b);
        fs[b].push_back(a);
    }

    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        bs[a].push_back(b);
        bs[b].push_back(a);
    }

    int c = 0;
    for (int i = 0; i < n; i++) {
        if (!was[i]) {
            c++;
            cnt = 0;
            dfs(i, c);
            dfs_ans(i);
        }
    }

    for (int i = 0; i < n; i++)
        cout << ans[i] << ' ';
}



Measured memory_bytes: 13476
import java.util.*;
import java.io.*;

/**
 * @author AnonymousP
 * @__WHEN YOU FEEL LIKE QUITTING, THINK ABOUT WHY YOU STARTED__@
 */
//COMBINATON = nCr = n*(n-1)/2
public class Main {

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        String s = sc.next();
        char a[] = s.toCharArray();
        int flag1 = 0;
        int flag2 = 0;
        for (int i = 1; i < a.length; i += 2) {
            if ((a[i] == 'L') || (a[i] == 'U') || (a[i] == 'D')) {

            } else {
                flag1 = -101;
                break;
            }
        }
        for (int i = 0; i < a.length; i += 2) {

            if ((a[i] == 'R') || (a[i] == 'U') || (a[i] == 'D')) {

            } else {
                flag1 = -101;
                break;
            }
        }
        if (flag1 == 0 && flag2 == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    //************************************************************************//
//CLASS_CLASS_CLASS_CLASS_CLASS_CLASS_CLASS_CLASS_CLASS_CLASS_CLASS_CLASS_//
//*******FAST IO*************FAST IO***************FAST IO****************//
    static class FastReader {

        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

   //*******FAST IO*************FAST IO***************FAST IO****************//
}


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


int main(void){
  int S,i;
  long long int count[2001];

  scanf("%d", &S);

count[1]=0;
count[2]=0;
count[3]=1;

if(S<=2) printf("0");
else if(S==3) printf("1");
else{
  for(i=4;i<=S;i++){
    count[i]=count[i-1]+count[i-3];
    count[i]%=1000000007;
  }
  printf("%lld\n", count[S]);
}

    return 0;

}


Measured memory_bytes: 1744
import java.util.Scanner;

class Main{


	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);			//文字の入力

		String S = sc.next();
		long mod = 1000000007L;
		String ABC = "ABC";
		long[][] dp = new long[S.length()][4];


		if(S.charAt(0) == '?'){					//初期値
			dp[0][0] = 3;
		}else{
			dp[0][0] = 1;
		}

		if(S.charAt(0) == 'A' || S.charAt(0) == '?'){
			dp[0][1] = 1;
		}


		for(int i = 1;i < S.length();i++){
			for(int j = 0;j < 4;j++){

				if(j == 0){
					if(S.charAt(i) == 'A' ||S.charAt(i) == 'B'||S.charAt(i) == 'C'){
						dp[i][0] = dp[i-1][0];
					}else{
						dp[i][0] = dp[i-1][0]*3L;
					}
					
					dp[i][j] %=mod;


				}else{

					long x = (S.charAt(i) == '?' ? 3L : 1L);				//?だったら３、他は１
					long y =( (S.charAt(i) == ABC.charAt(j-1)|| S.charAt(i) == '?') ? 1L :0L);

					dp[i][j] = (dp[i-1][j] * x) + (dp[i-1][j-1]*y); 
				dp[i][j] %=mod;
				}
			}


		}

		System.out.println(dp[S.length()-1][3] );
	}

}

Measured memory_bytes: 32236
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
#define inf 1e18+42
#define endl "\n"
#define pi 3.1415926535897932384626433832795028841971693993751058
#define maxn 100005

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define fori(it,A) for(auto it=A.begin();it!=A.end();it++)

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define pq priority_queue
#define all(x) (x).begin(),(x).end()
#define zero(x) memset(x,0,sizeof(x));
#define ceil(a,b) (a+b-1)/b
 
using namespace std;

int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

//START OF CODE ->->->->->->->

void solve()
{
    int n;
    cin>>n;
    int x = n/1000;
    cout<<((x+1)*1000 - n)%1000<<endl;
}

//END OF CODE ->->->->->->->->

signed main()
{
    fast;
    int t = 1;
    // cin>>t;

    while(t--)
    {
        solve();
    }
    return 0;
}



Measured memory_bytes: 3648
O = gets
E = gets
O.chomp!

ans = ""
while O.length > 0 || E.length > 0 do
	if O.length > 0
		ans += O[0]
		O.slice!(0)
	end
	if E.length > 0
		ans += E[0]
		E.slice!(0)
	end
end

print ans+"\n"


Measured memory_bytes: 1788
package main

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

func main(){
    
    sc := bufio.NewScanner(os.Stdin)
    
    var n, v, min, cmax int
    max := -1000000000
    
    sc.Scan()
    n, _ = strconv.Atoi(sc.Text())
    sc.Scan()
    min, _ = strconv.Atoi(sc.Text())

    for i := 1 ; i < n ; i++ {
        sc.Scan()
        v, _ = strconv.Atoi(sc.Text())
        cmax = v - min
        if max < cmax {
            max = cmax
        }
        if min > v {
            min = v
        }
    }
    fmt.Println(max)
}




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

int main() {

  string s;
  int k;
  cin>>s;
  cin>>k;
  int n = s.length();
  char ans[n];
  for (int i=0; i<n; i++) {
    char c = s[i];
    if (c == 'a') {
      ans[i] = 'a';
      continue;
    }
    int num = 26 - c + 'a';
    if (num <= k) {
      ans[i] = 'a';
      k = k - num;
    } else {
      ans[i] = c;
    }
  }
  k = k % 26;
  ans[n-1] = 'a' + (ans[n-1] - 'a' + k) % 26;
  cout<<string(ans, n)<<endl;
}

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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define MX              200005
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define pw(b,p)         pow(b,p) + 0.1

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // int t;
    // cin>>t;
    // while(t--){
        
    // }
    string s;cin>>s;
    int n=s.length();
    string ans="No";
    for(int i=0;i<n;i++){
        if(s[i]=='7')ans="Yes";
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3656
n = int(input())
a = [[int(i) for i in input().split()] for i in range(n-1)]
q,k = (int(i) for i in input().split())
question = [[int(i) for i in input().split()] for i in range(q)]
x,ans = [[] for i in range(n)],[False for i in range(n)]
for i in a:
	x[i[0]-1].append([i[1],i[2]])
	x[i[1]-1].append([i[0],i[2]])
visit = [False for i in range(n)]
visit[k-1],now = True,[k]
while now:
	p = now.pop()
	for i in x[p-1]:
		if not visit[i[0]-1]:
			visit[i[0]-1],ans[i[0]-1] = True,ans[p-1]+i[1]
			now.append(i[0])
for i in question:
	print(ans[i[0]-1]+ans[i[1]-1])

Measured memory_bytes: 80404
#include<stdio.h>
int main(){
  char s[5],c[5];
  int i,a=0;
  scanf("%s %s",s,c);
  for(i=0;i<3;i++){
    if(s[i]==c[i])a++;
  }
  printf("%d\n",a);
  return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
int main()
{
    long long n,j;
    while(~scanf("%lld",&n))
    {
        long long ans;
        for(j=1;j*j<=n;j++)
        {
            ans = j*j;
        }
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 128