akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int n, a[22][22];
ll dp[22][1<<22];

int main() {
    cin >> n;
    rep(i, n) rep(j, n) cin >> a[i][j];

    dp[0][0] = 1;
    rep(i, n) {
        for (int bits = 0; bits < (1 << n); bits++) {
            if (i == __builtin_popcount(bits)) {
                rep(j, n) {
                    if (!(bits & (1 << j)) && a[i][j]) {
                        dp[i+1][bits | (1 << j)] += dp[i][bits];
                        dp[i+1][bits | (1 << j)] %= MOD;
                    }
                }
            }
        }
    }
    cout << dp[n][(1 << n) - 1] << endl;
}


Measured memory_bytes: 321792
N=int(input())
count=0
max_=0
for i in range(N):
    D1,D2=map(int,input().split())
    if D1==D2:
        count+=1
        max_=max(max_,count)
    else:
        count=0
if max_>=3:
    print("Yes")
else:
    print("No")

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

int main(){
  vector<int>A(5);
  for(int i=0;i<5;i++){
    cin>>A[i];
  }
  for(int i=0;i<5;i++){
    if(A[i]==0){
      cout<<i+1<<endl;
      
    }
  
  }
}





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

using namespace std;

void solve(){
    long long count, n;
    cin>>n;
    while(true){
        count = 0;
        for(long i = 2; i < n; i++){
            if(n % i == 0){
                count++;
                break;
            }
        }
        if(count == 0){
            cout<<n;
            break;
        }
        n++;
    }
    
}

int main(){
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>

using namespace std;

const int maxn = 200000 + 10;

int main(void)
{
	set<int> st;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		st.insert(x);
	}
	
	if (st.size() != n) cout << "NO\n";
	else cout << "YES\n";
	return 0;
}

Measured memory_bytes: 9600
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

string S,T;

int main(){
  ll T,A,B,C,D;
  cin >> T;
  rep(i,T){
    cin >> A >> B >> C >> D;
    if(A<B){
      cNo;
    }
    else if(D%B==0){
      if(A%B>C){
        cNo;
      }
      else{
        cYes;
      }
    }
    else if(D<B){
      cNo;
    }
    else{
      ll P=gcd(B,D);
      if(C+P>=B){
        cYes;
      }
      else{
        cNo;
      }
    }
  }
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc160/tasks/abc160_d
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

int d[2001][2001];
int N, X, Y;
void warshall_floyd(int n) {
    vector<int> v;
    v.push_back(X);
    v.push_back(Y);
    for (auto k : v) {                    // 経由する頂点
        for (int i = 0; i < n; i++) {     // 始点
            for (int j = 0; j < n; j++) { // 終点
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> X >> Y;
    REP(i, N) REP(j, N) { d[i][j] = abs(i - j); }
    // 0-indexed
    X--, Y--;
    d[X][Y] = 1;
    d[Y][X] = 1;
    warshall_floyd(N);
    vector<int> ans(N);
    REP(i, N) FOR(j, i + 1, N) {
        int t = d[i][j];
        if (t < N)
            ans[t]++;
    }
    FOR(i, 1, N) { cout << ans[i] << "\n"; }

    return 0;
}


Measured memory_bytes: 31488
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041
"""
import sys
from itertools import permutations, product


def make_ten(digits):
    result = '0'
    for a, b, c, d in permutations(digits, 4):
        if result != '0':
            break
        for op1, op2, op3 in product(['+', '-', '*'], repeat=3):
            # 1, 2, 3
            exp = '((({} {} {}) {} {}) {} {})'.format(a, op1, b, op2, c, op3, d)
            if eval(exp) == 10:
                result = exp
                break
            # 1, 3, 2
            exp= '(({} {} {}) {} ({} {} {}))'.format(a, op1, b, op2, c, op3, d)
            if eval(exp) == 10:
                result = exp
                break
            # 2, 1, 3
            exp = '(({} {} ({} {} {})) {} {})'.format(a, op1, b, op2, c, op3, d)
            if eval(exp) == 10:
                result = exp
                break
            # 3, 1, 2
            exp = '({} {} (({} {} {}) {} {}))'.format(a, op1, b, op2, c, op3, d)
            if eval(exp) == 10:
                result = exp
                break
            # 3, 2, 1
            exp = '({} {} ({} {} ({} {} {})))'.format(a, op1, b, op2, c, op3, d)
            if eval(exp) == 10:
                result = exp
                break
            # 2, 3, 1
            exp =  '(({} {} {}) {} ({} {} {}))'.format(a, op1, b, op2, c, op3, d)
            if eval(exp) == 10:
                result = exp
                break
    return result


# ????????°????????????????????????10?????????????????????????????¢?????°????????§?????????????????????????????°??????????????¨???????????????????????¨??????????´????????????????
Memo = {}
def solve(digits):
    global Memo
    digits.sort(reverse=True)
    data = ''.join(map(str, digits))
    if data in Memo:
        pass
    else:
        Memo[data] = make_ten(digits)
    return Memo[data]


def main(args):
    while True:
        digits = [int(x) for x in input().strip().split(' ')]
        # digits = [int(x) for x in '{:04d}'.format(count)]
        if digits[0] == 0 and digits[1] == 0 and digits[2] == 0 and digits[3] == 0:
            break
        result = solve(digits)
        print(result)
        #print('count={}, {}'.format(count, result))


if __name__ == '__main__':
    main(sys.argv[1:])

Measured memory_bytes: 7804
import numpy as np
n = int(input())
m=1000000000000000000000
a = list(map(int,input().split()))
for i in range(n):
    num=0
    while True:
        if(a[i]%2==0):
            a[i]/=2
            num+=1
        else:
            break

    m = min(m,num)
print(m)

Measured memory_bytes: 12392
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();
		int X = sc.nextInt();

		if (500*K >= X) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

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

using namespace std;

const int N=110;

int sec[N],ans[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>sec[i];
    }
    for(int i=1;i<=n;i++)
    {
        bool fg=0;
        for(int j=n-i+1;j>=1;j--)
        {
            if(sec[j]==j)
            {
                ans[i]=j;
                fg=1;
                for(int k=j+1;k<=n-i+1;k++)
                {
                    sec[k-1]=sec[k];
                }
                break;
            }
        }
        if(!fg)
        {
            cout<<-1<<'\n';
            return 0;
        }
    }
    for(int i=n;i>=1;i--)
    {
        cout<<ans[i]<<'\n';
    }
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#define RG register
#define LL long long
using namespace std;
const LL mod=1e9+7;
int n,m;
LL dp[305][305][305];
inline int read(){
	char ch=getchar(); int x=0, f=1;
	while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();	}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar();	}
	return x*f;}
int main()
{
//	freopen("Road of the King.in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(); m=read();
	dp[0][1][1]=1;
	for(RG int i=0;i<m;i++)
	 for(RG int j=1;j<=n;j++)
	  for(RG int k=1;k<=j;k++)
	  {
			(dp[i+1][j+1][k]+=dp[i][j][k]*(n-j))%=mod;
			(dp[i+1][j][k]+=dp[i][j][k]*(j-k))%=mod;
			(dp[i+1][j][j]+=dp[i][j][k]*k)%=mod;
	  }
	printf("%lld\n",dp[m][n][n]);
	//fclose(stdin); fclose(stdout);
	return 0;
}

Measured memory_bytes: 218624
#include "bits/stdc++.h"
#include "math.h"
#include "string.h"
#include "algorithm"
 
using namespace std;
typedef int64_t ll;
typedef vector<int64_t> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SIZE(a) int((a).size())


int main(){
  int a,b;
  cin>>a>>b;
  double xa,ya,xb,yb;
  xa=a*12.5,ya=(a+1)*12.5,xb=b*10,yb=(b+1)*10;
  bool ans=true;
  FOR(i,a*10,(b+1)*10){
    if(i>=xa&&i<ya&&i>=xb){
      cout<<i<<endl;
      ans=false;
      break;
    }
  }
  if(ans){
    cout<<-1<<endl;
  }
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text.RegularExpressions;
using System.Diagnostics;
using static System.Math;

//var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
namespace AtCoderSolve
{

    class Solve
    {
        const int mod = 1000000007;
        const int INF = 2147483647;
        const long SINF = 9223372036854775807;

        static int N;
       

        public static void Input()
        {
            var cin = new Solve();
            N = int.Parse(Console.ReadLine());
        }

        static void Main(string[] args)
        {
            Input();
            //var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            //Console.SetOut(sw);
            Console.WriteLine(N % Dsum(N) == 0 ? "Yes" : "No");
            

            //Console.Out.Flush();
        }

        public int[] SplitReader()
        {
            int[] array = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return array;
        }
        public long[] SplitReaderL()
        {
            long[] array = Console.ReadLine().Split().Select(long.Parse).ToArray();
            return array;
        }

        public static int Dsum(int n)
        {
            int d = 0;
            while (n > 0)
            {
                d += n % 10;
                n /= 10;
            }
            return d;
        }
    }
}

    



Measured memory_bytes: 13140
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;

ll fiv(int a, int s) {
    return a*a*a*a*a + s*s*s*s*s;
}

int main() {
    int X;
    cin >> X;
    rep(i, 120){
        rep(j, i+1){
            if(i*i*i*i*i+j*j*j*j*j == X){
                cout << i << ' ' << -j << endl;
                return 0;
            } else if(i*i*i*i*i-j*j*j*j*j == X){
                cout << i << ' ' << j << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 3560
import java.util.Arrays;
import java.util.Scanner;
class Main{


	static char[][] map;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();
		int[] d = new int[n];
		for(int i = 0;i < n;i++){
			d[i] = sc.nextInt();
		}
		Arrays.sort(d);
		
		int ans = 0;
		if(n % 2 == 0 && d[n/2-1] != d[n/2]){
			ans = d[n/2] -d[n/2-1]; 
		}
		System.out.print(ans);

	}



	static int gcd(int a,int b){				//最大公約数を返す
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}
	static long gcd(long a,long b){
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}



	static long lcm (long a, long b) {
		long g = gcd(a,b);
		return a/g*b;
	}




}



class Pair implements Comparable{
	int from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return   end- otherpair.end;
	}







	static int find(int index,int current,int[] students,int ans,int[][] memo){
		if(current == index){
			return 1;
		}

		if(memo[current][index] != 0){
			return memo[current][index];
		}

		memo[current][index] = find(index, students[current]-1, students, ans+1, memo)+1;

		return memo[current][index];
	}



	static int gcd(int a,int b){				//最大公約数を返す
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}
	static long gcd(long a,long b){
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}



	static long lcm (long a, long b) {
		long g = gcd(a,b);
		return a/g*b;
	}




}






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

int main()
{
  int N,K;cin>>N>>K;
  long double sum=0;
  long double p=0.50000000000000000;
  for(int i=1;i<=N;i++)
  {
    int point=i;
    int count=0;
    while(point<=K-1)
    {
      point*=2;
      count++;
    }
    //cout<< i<<":"<< count<<endl;
    sum += pow(p,count);   
  }
  //cout << fixed << setprecision(15) << sum << endl;
  sum /= N;
  cout << fixed << setprecision(15) << sum << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
typedef long long ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define rrep(i,n,a) for(int i=n;i>=a;i--)
#define FOR(i,n) for(int i=0;i<n;i++)
#define all(s) s.begin(),s.end()
#define lla(s) s.rbegin(),s.rend()
#define pcnt(b) __builtin_popcount(b)
#define vi vector<int>
#define vvi vector<vector<int>>
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const ll INF = 1e18;


signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string n;
    cin>>n;
    rep(i,0,3){
        if(n[i]=='7'){
            cout<<"Yes"<<endl;return 0;
        }
    }
    cout<<"No"<<endl;return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
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;}
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b;cin>>a>>b;
    int k;cin>>k;
    rep(i, k){
        if(i%2==0){
            if(a%2!=0){
                a-=1;
            }
            a/=2;
            b+=a;
        } else {
            if(b%2!=0){
                b-=1;
            }
            b/=2;
            a+=b;
        }
    }
    cout<<a<<" "<<b<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main(){
	int n, k; cin>>n>>k;
	vector<int> a(n);
	for(int i=0;i<n;++i)cin>>a[i];

	int ans=INT_MAX,t;
	for(int i=0;i<n-k+1;++i){
		t=min(a[i+k-1]-a[i]+abs(a[i+k-1]), a[i+k-1]-a[i]+abs(a[i]));
		if(ans>t)ans=t;
	}
	cout<<ans;
}

Measured memory_bytes: 640
h, w = map(int, input().split())
a = [None for i in range(h + 2)]
a[0] = ['#' for i in range(w + 2)]
a[-1] = ['#' for i in range(w + 2)]
for i in range(1, h + 1):
    a[i] = ['#'] + list(input()) + ['#']

for i in range(h + 2):
    print(''.join(a[i]))


Measured memory_bytes: 3060
# coding: utf-8;

def main():
    s = input()
    unbalance = True

    if len(s) == 2 and s[0:1] == s[1:2]:
        unbalance = False
        print(1, 2)
    else:
        for i in range(len(s) - 2):
            if s[i:i+1] == s[i+1:i+2] or s[i:i+1] == s[i+2:i+3]:
                unbalance = False
                print(i+1, i+3)
                break

    if unbalance: print(-1, -1)

if __name__ == '__main__':
    main()


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

int main() {
	int n, k, d, a, i, j, cnt = 0;
	int sunuke[100] = { 0 };

	cin >> n >> k;
	for (i = 0; i < k; i++) {
		cin >> d;
		for (j = 0; j < d; j++) {
			cin >> a;
			sunuke[a - 1]++;
		}
	}
	for (i = 0; i < n; i++) {
		if (sunuke[i] == 0) {
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a,v,b,w,t;
	cin>>a>>v>>b>>w>>t;
	if(llabs(a-b)<=t*(v-w))
		cout<<"YES";
	else
		cout<<"NO";
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

int main()
{
    int n;
    cin >> n;
    int a[100002];
    for(int i = 0; i < n; i++) cin >> a[i];
    int s[3] {0};
    ll ans = 1;
    for(int i = 0; i < n; i++){
        int inc = -1;
        ll b = 0;
        for(int j = 0; j < 3; j++){
            if(a[i] == s[j]){
                inc = j;
                b++;
            }
        }
        s[inc]++;
        ans = ans * b % MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(){

int i, j, n;
int S[10000], q, T[500];
int c=0;

scanf("%d", &n);

for(i=0;i<n;i++){
scanf("%d", &S[i]);
}

scanf("%d", &q);

for(i=0;i<q;i++){
scanf("%d", &T[i]);
}

for(j=0;j<q;j++){

i=0;
S[n]=T[j];

while(S[i]!=T[j]){
i++;
}

if(i!=n) c++;

}

printf("%d\n", c);

return 0;

}

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


using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VP vector<pair<int,int>>
#define VPP vector<pair<int,pair<int,int>>>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 1000000007;



int main() {

	int n, m;
	cin >> n >> m;
	
	VI b(10, -1);
	if (n == 1 && m == 0) {
		cout << 0 << endl;
		return 0;
	}
	REP(i, m) {
		int c, d;
		cin >> c >> d;
		c--;

		if (c == 0 && d == 0 && n != 1) {
			cout << -1 << endl;
			return 0;
		}

		if (b[c] == -1) {
			b[c] = d;
		}
		else if (b[c] != d) {
			cout << -1 << endl;
			return 0;
		}
	}

	if (n == 1) {
		if (b[0] == -1) {
			cout << 0 << endl;
		}
		else cout << b[0] << endl;

		return 0;
	}

	REP(i, 10) {
		if (b[i] == -1)b[i] = 0;
	}
	if (b[0] == 0) {
		b[0] = 1;
	}
	REP(i, n)cout << b[i];
	
	cout << endl;


	



}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<cmath>
#include<ctime>

using namespace std;
using ll = long long;

struct UnionFind {
  vector<int> par;//parent
  vector<int>nodes;
  UnionFind(int N): par(N), nodes(N)
  {
    for(int i = 0; i < N; i++){
      par[i] = i;
      nodes[i] = 1;
    }
  }
  int root(int x) {//find the root and path compression
    if(par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  void unite(int x, int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry) return;
    nodes[ry] += nodes[rx];
    par[rx] = ry;
  }
  bool same(int x, int y){
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
};

struct node{
  double x, y, z, r;
};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  int n;
  while(cin>> n && n){
    double ans = 0;
    vector<node> V(n);
    for(int i = 0; i < n; i++){
      cin >> V[i].x >> V[i].y >> V[i].z >> V[i].r;
    }
    vector<pair<double, pair<int, int>>> edge;
    UnionFind U(n);
    for(int i = 0; i < n; i++){
      for(int j = i+1; j < n; j++){
        double cost = sqrt(pow(V[i].x - V[j].x,2.0)+pow(V[i].y - V[j].y,2.0)+pow(V[i].z - V[j].z,2.0)) - V[i].r - V[j].r;
        if(cost > 0) edge.push_back({cost, {i, j}});
        else if(!U.same(i, j)) U.unite(i, j);
      }
    }
    sort(edge.begin(), edge.end(), [](pair<double, pair<int, int>> a, pair<double, pair<int, int>> b){
      return a.first < b.first;
    });
    for(auto e : edge){
      if(!U.same(e.second.first, e.second.second)){
        U.unite(e.second.first, e.second.second);
        ans += e.first;
      }
    }
    cout << fixed << setprecision(3) << ans << endl;
  }
  // end-----------------------------------------------
  // cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}



Measured memory_bytes: 3408
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair< int, int> P;
struct edge{ll to, cost; };

static const double EPS = 1e-8;
static const double PI = 3.141592653589;
static ll INF = 999999999999;
int mod = 1000000007;

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define MIN(a,b)    (a) < (b) ? (a):(b)
#define MAX(a,b)    (a) > (b) ? (a):(b)
#define debug(x) cerr << #x << " = " << x << endl;
int dx[] = {1,-1,0,0,1,-1,1,-1};
int dy[] = {0,0,1,-1,-1,1,1,-1};

using namespace std;


int main() {
    string ans;
    cin >> ans;
    string hen = "";

    REP(i, ans.size()){
        if(ans[i] == '1'){
           hen = hen + '1';
        }else if(ans[i] == '0'){
            hen = hen + '0';
        }else{
            if(hen.size() != 0)
            hen.erase(hen.size()-1);
        }
    }

    cout << hen << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <vector>
#define mod 1000000007
using namespace std;
typedef long long ll;
const int MAXN = 305;
vector<pair<int , int> >vc[MAXN];
ll dp[MAXN][MAXN][MAXN];
bool check(int r , int g , int b) {
    int k = max(r , max(g , b));
    int len = vc[k].size();
    for(int i = 0 ; i < len ; i++) {
        int l = vc[k][i].first , x = vc[k][i].second;
        int cnt = 0;
        if(r >= l) cnt++;
        if(g >= l) cnt++;
        if(b >= l) cnt++;
        if(cnt != x) return false;
    }
    return true;
}
int main() {
    int n , m;
    cin >> n >> m;
    for(int i = 0 ; i < m ; i++) {
        int l , r , x;
        cin >> l >> r >> x;
        vc[r].push_back(make_pair(l , x));
    }
    memset(dp , 0 , sizeof(dp));
    dp[0][0][0] = 1;
    ll ans = 0;
    for(int r = 0 ; r <= n ; r++) {
        for(int g = 0 ; g <= n ; g++) {
            for(int b = 0 ; b <= n ; b++) {
                if(!dp[r][g][b]) continue;
                if(!check(r , g , b)) {
                    dp[r][g][b] = 0;
                    continue;
                }
                int k = max(r , max(g , b));
                if(k == n) ans = (ans + dp[r][g][b]) % mod;
                dp[k + 1][g][b] += dp[r][g][b] % mod;
                dp[r][k + 1][b] += dp[r][g][b] % mod;
                dp[r][g][k + 1] += dp[r][g][b] % mod;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 221952
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

template<typename T,T MOD,T B>
struct RollingHash{
  vector<T> hash,p;
  RollingHash(){}
  RollingHash(const string &s){
    ll n=s.size();
    hash.assign(n+1,0);
    p.assign(n+1,1);
    for(ll i=0;i<n;i++){
      hash[i+1]=(hash[i]*B+s[i])%MOD;
      p[i+1]=p[i]*B%MOD;
    }
  }
  //S[l, r)
  T find(ll l,ll r){
    T res=hash[r]+MOD-hash[l]*p[r-l]%MOD;
    return res>=MOD?res-MOD:res;
  }
};
 
int main() {
  ll n;
  string s;
  cin >> n >> s;
  RollingHash<ll,mod,31> rs(s);
  ll l=0,r=n/2+1;
  ll temp=(l+r)/2;
  while(l+1<r) {
    bool flag=false;
    for(ll i=0;i<max(n-temp+1,0LL);i++) {
      for(ll j=i+temp;j<max(n-temp+1,0LL);j++) {
        if(rs.find(i,i+temp)==rs.find(j,j+temp)) {
          flag=true;
          break;
        }
      }
      if(flag) break;
    }
    if(flag) {
      l=temp;
    }
    else {
      r=temp;
    }
    temp=(l+r)/2;
  }
  cout << l << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <random>
#include <chrono>
#include <algorithm>
#define rep(i, x) for(ll i = 0; i < x; i++)
using namespace std;
typedef long long ll;
const ll MOD = (ll)1e9+7;
const ll N = 5e5+5, inf = 1e18+5000;
ll add(ll x, ll y) { x += y; if (x >= MOD) return x - MOD; return x; }
ll sub(ll x, ll y) { x -= y; if (x < 0) return x + MOD; return x; }
ll mult(ll x, ll y) { return (x * y) % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n; cin >> n;
  vector<ll> x(n), y(n), p(n);
  rep (i, n) {
    cin >> x[i]; cin >> y[i]; cin >> p[i];
  }

  vector<vector<ll>> horizontals(n, vector<ll>(1<<n)), verticals(n, vector<ll>(1<<n));
  for (int mask = 0; mask < 1<<n; mask++) {
    for (int i = 0; i < n; i++) if (!(mask & (1<<i))) {
      ll best_x = abs(x[i]), best_y = abs(y[i]);
      for (int j = 0; j < n; j++) if (mask & (1<<j)) {
        best_x = min(best_x, abs(x[i] - x[j]));
        best_y = min(best_y, abs(y[i] - y[j]));
      }
      horizontals[i][mask] = best_y;
      verticals[i][mask] = best_x;
    }
  }

  vector<ll> ans(n+1, inf);
  for (int mask = 0; mask < 1<<n; mask++) {
    for (int subm = mask; ; subm = (subm-1)&mask) {
      ll score = 0;
      for (int i = 0; i < n; i++) if (!(mask & (1<<i)))
        score += min(horizontals[i][subm], verticals[i][mask ^ subm]) * p[i];
      ans[__builtin_popcount(mask)] = min(ans[__builtin_popcount(mask)], score);
      if (subm == 0)  break;
    }
  }

  for (int k = 0; k <= n; k++) cout << ans[k] << endl;

  return 0;
}

Measured memory_bytes: 11244
n, k = [int(i) for i in input().split()]
tel = [int(i) for i in input().split()]
been = [0 for _ in range(n)]
been[0] = 1

next = tel[0]
loop = [1]
for i in range(n):
	loop.append(next)
	if been[next-1] == 1:
		break
	been[next-1] = 1
	next = tel[next-1]

loop_begin = loop.index(tel[next-1])
loop_num = i - loop_begin + 2
if loop_begin >= k:
	ans = loop[k]
else:
	loop_remain = (k-loop_begin) % loop_num
	ans = loop[loop_begin+loop_remain]

print(ans)





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



signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    int n,m;
    cin>>n>>m;
    string ans="";
    for(int i=0;i<n;i++){
        ans += "-";
    }
    for(int i=0;i<m;i++){
        int s;
        char c;
        cin>>s>>c;
        s--;
        if(ans[s] != '-' && ans[s] != c){
            cout << "-1\n";
            return 0;
        }
        ans[s] = c;
    }    
    if(n!=1 && ans[0]=='0'){
        cout << -1 << endl;
        return 0;
    }
    if(n==1 && ans[0]=='-'){
        cout << 0 << endl;
        return 0;
    }
    if(ans[0]=='-')ans[0]='1';
    for(int i=1;i<n;i++){
        if(ans[i]=='-')ans[i]='0';
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  int a,b,w;
  cin >> w >> a >> b;
  if(max(a+w-b,b+w-a)<=2*w) cout << 0 << "\n";
  else cout << min(abs(a-b-w),abs(b-a-w)) << "\n";
  return 0;
}

Measured memory_bytes: 3640
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i, j,  N, Y;
    int x, y, z;
    int tmp, G, sum;
    int flag = 0;

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

    Y = Y / 1000;
    G = Y - N;

    tmp = Y / 10;

    for(i=tmp; i>=0; i--)
    {
        x = i;
        y = (G - 9*x) / 4;
        for(j=y; j>=0; j--)
        {
            y = j;
            z = N - x - y;
            if(z < 0)
            {
                continue;
            }
            sum = (10*x + 5*y + z);
            if(sum == Y)
            {
                flag = 1;
                break;
            }
        }
        if(flag == 1)
        {
            break;
        }
    }

    if(flag == 1)
    {
        printf("%d %d %d\n", x, y, z);
    }
    else
    {
        printf("-1 -1 -1\n");
    }
    return 0;

}

Measured memory_bytes: 128
#include <map>
#include <list>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
int n;
long long f[(long long)45];
int main()
{
    fast;
	cin>>n;
	f[0]=2;
	for (int i=1;i<=n;i++)
	   f[i]=f[i-1]*2+2;
	cout<<f[n]<<endl;
	return 0;
}

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

int main(){
  int n;
  cin >> n;
  int count = 0;
  for(int i = 0;i < n;++i){
    int l,r;
    cin >> l >> r;
    count += r - l + 1;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<stdlib.h>

int main(void){

  int i, n;
  int *a;

  scanf("%d", &n);
  a = (int *)malloc(sizeof(int) * n);

  for(i=n;i>0;i--){
    scanf("%d", &a[i-1]);
  }

  for(i=0;i<n;i++){
    printf("%d", a[i]);
    if(i != n-1){
      printf(" ");
    }else{
      printf("\n");
    }
  }

  return 0;

}



Measured memory_bytes: 2104
using System;
using System.Collections.Generic;

public class DateSet
{
    //0?????\????????§??°????????????????????????????????????
    static void Main(string[] args)
    {
        /*---??£?¨???¨---*/
        int i = 0;
        int k;
        List<int> list = new List<int>();
        /*---??£?¨???¨---*/

        //0?????\????????§????????????
        while (true){
            list.Add(int.Parse(Console.ReadLine()));
            if(list[i] == 0){
                break;
            }
            i++;
        }

        /*0?????§????????????????????????*/
        for(k = 0; k < i; k++){
            Console.WriteLine("Case {0}: {1}", k+1, list[k]);
        }
    }
}

Measured memory_bytes: 9392
#/*
    AUTHOR:shivam51
    IIESTS
*/
  #include<bits/stdc++.h>
  using namespace std;
  //
  #define add accumulate
  #define ll long long int
  #define ff first
  #define ss second
  #define pb push_back
  #define mp make_pair
  #define vll vector<ll>
  #define lb lower_bound
  #define ub upper_bound
  #define pll pair<ll,ll>
  #define vpll vector<pll>
  #define all(v) v.begin(), v.end()
  #define rep(i,k,n) for(int i=k;i<n;i++)
  #define hs ios_base::sync_with_stdio(false);cin.tie(NULL);
  const ll mod=1e9+7;
  const ll MAX=401;
  //
  //
  	ll solve(){
  		ll n;
  		cin>>n;
  		vll vec(n+1);
  		rep(i,0,n){
  			ll k;
  			cin>>k;
  			vec[k]=i+1;
  		}
  		bool flag=true;
  		rep(i,0,n){
  			if(vec[i+1]==i+1)
  				continue;
  			if(vec[i+1]!=i+1&&vec[vec[i+1]]==i+1){
  				if(!flag)
  					return cout<<"NO\n",0;
  				vec[vec[i+1]]=vec[i+1];
  				vec[i+1]=i+1;
  				flag=false;
  			}
  			else{
  				return cout<<"NO\n",0;
  			}
  		}
  		cout<<"YES\n";
  	}
	int main(){ 
		hs;
		ll t;
		// cin>>t;
		t=1;
		while(t--)
			solve();
    return 0; 
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int e,minx,x,y,z;
  while(cin >> e && e){
    if(e == 1)cout << 1 << endl;
    else{
      minx = 1000001;
      for(z=0;z*z*z<=e;z++){
	y = (int)sqrt(e-z*z*z);
	x = e-z*z*z-y*y;
	minx = min(minx,x+y+z);
      }
      cout << minx << endl;
    }
  }
}

Measured memory_bytes: 1156
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  ll N;
  cin >> N;
  vector<ll> H(N);
  rep(i,N) cin >> H[i];
  reverse(all(H));
  int ans = 0;
  int preans = 0;
  for(int i=1;i<N;i++){
    if(H[i] >= H[i-1]){
      preans++;
    }
    else{
      ans = max(ans,preans);
      preans = 0;
    }
  }
  ans = max(ans,preans);

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


Measured memory_bytes: 1152
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
using static System.Console;


namespace atcorder2
{
    class Program
    {
        public static long Read()
        {

            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {

            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }

       
         public static long GCM(long x,long y)
        {
            if (x < y)  GCM(y, x);


            while (y > 0)
            {
                var z = y;
                y = x % y;
                x = z;
            }
            
            return x;
        }

        



        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);


            var n = Read();
            var s = ReadLine();
            var t = ReadLine();
            long ans = 0;
            bool f=true;
            for (int i = 0; i < n; i++)
            {
                f = true;
                for (int j = i; j < n; j++)
                {
                    if (t[j - i] != s[j]) f = false;
                }
                if (f) { ans = i; break; }
            }
            WriteLine(f ? n+ans : 2*n );
            
            
           










            Console.Out.Flush();
        }
    }
}




Measured memory_bytes: 13140
N = int(input())
list = []
for i in range(N):
    s = input()
    list.append(s)

AC = str(list.count('AC'))
WA = str(list.count('WA'))
TLE = str(list.count('TLE'))
RE = str(list.count('RE'))

print('AC x '+ AC)
print('WA x '+ WA)
print('TLE x ' + TLE)
print('RE x '+ RE)


Measured memory_bytes: 16224
#include <bits/stdc++.h>
#include<math.h>
#include<algorithm> 
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
#define INF 1e18
#define mod 1000000007

ll modpow (ll a, ll n){
    if(n == 0) return 1 ;
    if(n == 1) return a % mod ;
    if(n % 2 == 1) return (a * modpow(a, n - 1)) % mod ;
    ll t = modpow(a, n / 2) ;
    return (t * t) % mod ;
}

int main () {
    ll n ;
    cin >> n ;
    ll ans = modpow(10, n) ;
    ll d1 = modpow(9, n) ;
    ll d2 = modpow(8, n) ;
    ll dd = (d1 + d1) % mod ;
    dd -= d2 ; 
    if(dd < 0){
        dd += mod ;
    }
    ans -= dd ;
    if(ans < 0){
        ans += mod ;
    }
    cout << ans << endl ;
}

Measured memory_bytes: 3636
/*
最短経路を求め，最短経路外のマスをすべて黒にすれば最も点数が得れる


*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define rep(i,n) for(int i = 0;i < (n);i++)

int d[51][51] = {};
int H,W;

void bfs(int y,int x,int c){
  queue<int> qx;
  queue<int> qy;
  queue<int> qc;
  qx.push(x);
  qy.push(y);
  qc.push(c);
  while(!qx.empty()){
    x = qx.front();
    y = qy.front();
    c = qc.front();
    qx.pop();qy.pop();qc.pop();
    if(d[y][x]!=0) continue;
    d[y][x] = c;
    rep(i,4){
      const int dir[5] = {0,1,0,-1,0};
      if(y+dir[i]<0 || y+dir[i]>=H || x+dir[i+1]<0 || x+dir[i+1]>=W) continue;
      qx.push(x+dir[i+1]);
      qy.push(y+dir[i]);
      qc.push(c+1);
    }
  }
}
int main(){
  cin >> H >> W;
  rep(i,H){
    string s;
    cin >> s;
    rep(j,W){
      d[i][j] = (s[j]=='.') ? 0 : -1;
    }
  }
  bfs(0,0,1);
  int c = 0;
  rep(y,H){
    rep(x,W){
      if(d[y][x]==-1) c++;
    }
  }
  // rep(y,H){
  //   rep(x,W){
  //     printf("%3d",d[y][x]);
  //   }
  //   cout << endl;
  // }
  if(d[H-1][W-1]==0) cout << -1 <<endl;
  else cout << H*W-c-d[H-1][W-1] << endl;
  return 0;
}


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

int main(void)
{
	long long n, sum, ans, x, y;
	cin >> n;
	vector<long long> v(n);

	sum = 0;
	rep(i, n)
	{
		cin >> v[i];
		sum += v[i];
	}
	ans = 100000000000;
	x = y = 0;
	rep(i, n - 1)
	{
		x = sum;
		y += v[i];
		x -= y;
		ans = min(ans, abs(x - y));
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<limits>

using namespace std;

#define int long long

vector<int> x(3);

/*
numer 0
( 1
) 2
+ 3
- 4
* 5
*/

char temp[] = {'n', '(', ')', '+', '-', '*'};

int solve(vector<pair<int,int>> t, int b, int e){
	vector<pair<int,int>> t2;
	
	for(int i = b, depth = 0, index = -1; i < e; i++){
		switch(t[i].first) {
			case 1: 
				if(depth == 0) {
					index = i;
				}
				depth++;
				break;
			case 2:
				depth--; 
				if(depth == 0) {
					t2.push_back({0, solve(t, index+1, i)});
				}
				break;
			default: if(!depth) t2.push_back(t[i]);
		}
	}
	for(int k = 0; k < 3; k++) {
	
		vector<pair<int,int>> st;
		
		for(int i = 0, depth = 0, index = -1; i < t2.size(); i++){
			st.push_back(t2[i]);
			pair<int,int> a, b, c;
			
			while(st.size() >= 3) {
				a = st.back(); st.pop_back();
				b = st.back(); st.pop_back();
				c = st.back(); st.pop_back();
				
				if(!b.first){
					st.push_back(c);
					st.push_back(b);
					st.push_back(a);
					break;
				}
				
				if(b.first == 3) {
					if(x[0] == k) {
						st.push_back({0,c.second + a.second});
					} else {
						st.push_back(c);
						st.push_back(b);
						st.push_back(a);
						break;
					}
				}
				
				if(b.first == 4) {
					if(x[1] == k) {
						st.push_back({0,c.second - a.second});
					} else {
						st.push_back(c);
						st.push_back(b);
						st.push_back(a);
						break;
					}
				}
				
				if(b.first == 5) {
					if(x[2] == k) {
						st.push_back({0,c.second * a.second});
					} else {
						st.push_back(c);
						st.push_back(b);
						st.push_back(a);
						break;
					}
				} 
			}
		}
		
		if(k == 2) {
			return st.back().second;
		} else {
			t2 = st;
		}
	}
	
	return 0;
}

void hoge(string &s, vector<pair<int,int>> &t){
	
	for(int i = 0, num = 0; i < s.size(); i++){
		switch(s[i]) {
			case '(': t.push_back({1,0}); break;
			case ')': t.push_back({2,0}); break;
			case '+': t.push_back({3,0}); break;
			case '-': t.push_back({4,0}); break;
			case '*': t.push_back({5,0}); break;
			default : 
				num = num * 10 + s[i] - '0';
				if(i + 1 == s.size() || '0' > s[i+1] && s[i+1]){
					t.push_back({0,num});
					num = 0;
				}
		}
	}
}

signed main(){
	
	vector<pair<int,int>> t;
	string s;
	
	int ans =  numeric_limits<long long>::min();
	
	cin>>s;
	
	hoge(s, t);
	
	
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 3; k++){
				x[0] = i;
				x[1] = j;
				x[2] = k;
				ans = max(solve(t, 0, t.size()), ans);
			}
		}
	}
	
	cout<<ans<<endl;
}


Measured memory_bytes: 3220
N, M, K = map(int, input().split())

if M==1:
    print(1 if K==N-1 else 0)
    exit()

mod = 998244353

f = [0]*N
f[0] = p = 1
for i in range(1,N):
    f[i] = p = p*i%mod

finv = [0]*N
finv[N-1] = p = pow(f[N-1],mod-2,mod)
for i in range(N-2, -1, -1):
    finv[i] = p = p*(i+1)%mod

ans = 0
for k in range(K+1):
    x = M * pow(M-1, N-k-1, mod) % mod
    y = (f[N-1]*finv[N-1-k]%mod)*finv[k]%mod
    ans = (ans + x*y%mod)%mod

print(ans)


Measured memory_bytes: 24576
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
using namespace std;

typedef pair<int, int> pii;
const int INF = 1 << 28;
struct UnionFind {
    int node[110];
    UnionFind() {
        memset(node, -1, sizeof(node));
    }
    void reset() {
        memset(node, -1, sizeof(node));
    }
    int find(int x) {
        return node[x] < 0 ? x : node[x] = find(node[x]);
    }
    int size(int x) {
        return -node[find(x)];
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return;
        if(size(x) > size(y)) swap(x, y);
        // x を y に統合
        node[y] += node[x];
        node[x] = y;
    }
};

UnionFind uf;
int main() {
    int N, M;
    while(scanf("%d%d", &N, &M)) {
        if(!(N|M)) break;
        vector<pii> edges[10010];
        for(int i=0; i<M; i++) {
            int a, b, w; scanf("%d%d%d", &a, &b, &w);
            a--; b--;
            edges[w].push_back(make_pair(a, b));
        }

        int ans = INF;
        for(int s=1; s<=10000; s++) {
            if(edges[s].size() == 0) continue;
            uf.reset();
            for(int i=s; i<=10000; i++) {
                for(auto e : edges[i]) {
                    int u = e.first, v = e.second;
                    uf.unite(u, v);
                    if(uf.size(0) == N) {
                        ans = min(ans, i-s);
                        goto outside;
                    }
                }
            }
            outside:;
        }
        if(ans == INF) printf("-1\n");
        else printf("%d\n", ans);
    }
    return 0;
}


Measured memory_bytes: 3064
#![allow(unused)]

use std::{cell, cmp, collections, convert, fmt, io, iter, ops, str};

use cell::{Cell, RefCell};
use cmp::Ordering::{Equal, Greater, Less};
use collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};
use io::{Read, Write};

#[cfg(feature = "debug")]
macro_rules! debug {
    ($($args: tt)*) => { eprint!($($args)*) };
}

#[cfg(feature = "debug")]
macro_rules! debugln {
    ($($args: tt)*) => { eprintln!($($args)*) };
}

#[cfg(not(feature = "debug"))]
macro_rules! debug {
    ($($args:tt)*) => {};
}

#[cfg(not(feature = "debug"))]
macro_rules! debugln {
    ($($args:tt)*) => {};
}

macro_rules! vmax {
    ($x: expr, $y: expr) => { cmp::max($x, $y) };
    ($x: expr, $($args: expr),*) => { cmp::max($x, vmax!($($args),*)) };
}

macro_rules! vmin {
    ($x: expr, $y: expr) => { cmp::min($x, $y) };
    ($x: expr, $($args: expr),*) => { cmp::min($x, vmin!($($args),*)) };
}

fn main() {
    let a = parse_word::<i32>();
    let b = parse_word::<i32>();

    if a <= 8 && b <= 8 {
        println!("Yay!");
    } else {
        println!(":(");
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        //
    }
}

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().to_owned()
}

fn read_word() -> String {
    const CAPACITY: usize = 16;

    let mut stdin = io::stdin();
    let mut byte: [u8; 1] = [0];

    loop {
        let mut buf = Vec::with_capacity(CAPACITY);

        loop {
            let res = stdin.read(&mut byte);

            if res.unwrap_or(0) == 0 || byte[0] <= b' ' {
                break;
            } else {
                buf.push(byte[0]);
            }
        }

        if !buf.is_empty() {
            return String::from_utf8(buf).unwrap();
        }
    }
}

fn parse_line<T: str::FromStr>() -> T {
    read_line().parse().ok().unwrap()
}

fn parse_word<T: str::FromStr>() -> T {
    read_word().parse().ok().unwrap()
}

fn parse_vec<T: str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn flush() {
    io::stdout().flush();
}

fn next_prime(x: i32) -> i32 {
    for i in (x + 1).. {
        if is_prime(i) {
            return i;
        }
    }

    panic!("attempt to add with overflow");
}

fn is_prime(x: i32) -> bool {
    let ceil = f64::from(x).sqrt().ceil() as i32;
    x == 2 || (2..(ceil + 1)).all(|i| x % i != 0)
}


Measured memory_bytes: 4352
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int D = sc.nextInt();
        int X = sc.nextInt();
        int A;
        int date = 0;
        int[] count = new int[N];
        for(int i=0; i<N; i++){
        	A = sc.nextInt();
        	count[i] = 1;
        	date = A + 1;
        	while(date <= D){
        		count[i]++;
        		date += A;
        	}
        }
        
        int c = 0;
        for(int i=0; i<N; i++){
        	c += count[i];
        }
        System.out.println(c+X);
	}

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n; cin>>n;
  int mod=1000000007;
  long long a[n];
  long long ans=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  long long sum=0;
  for(int i=0;i<n;i++){
    sum+=a[i];
  }
  for(int i=0;i<n-1;i++){
    sum-=a[i];
    sum%=mod;
    if(sum<0){
      sum+=mod;
    }
    ans+=sum*a[i]%mod;
    ans%=mod;
  }
  cout<<ans<<endl;
  return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = n % 1000;
        if (a != 0)
            a = 1000 - a;

        System.out.println(a);

    }
}

Measured memory_bytes: 35728
import java.io._
import java.util.StringTokenizer

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val N = in.next().toInt
  // (node, cost)
  val graph: Array[List[(Int, Int)]] = Array.fill(N+1)(Nil)
  for(_ <- 1 to N-1) {
    val a, b, cost = in.next().toInt
    graph(a) = (b, cost) :: graph(a)
    graph(b) = (a, cost) :: graph(b)
  }

  val Q, K = in.next().toInt

  // dfs
  val stack = new scala.collection.mutable.Stack[(Int, Long)] // (nowNode, cost)
  stack.push((K, 0))

  val dp = new Array[Long](N+1)
  dp(K) = 2

  while (!stack.isEmpty) {
    val (now, accCost) = stack.pop
    for((node, cost) <- graph(now)) {
      if(dp(node) == 0) {
        dp(node) = accCost + cost
        stack.push((node, accCost + cost))
      }
    }
  }

  for (_ <- 1 to Q) {
    val x, y = in.next().toInt
    val ans: Long = dp(x) + dp(y)
    pw.println(ans)
  }
  pw.flush()

}


class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 82056