akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <stack>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
int main(){
    vector<vector<char>>g(2,vector<char>(3));
    rep(i,2)rep(j,3)cin>>g[i][j];
    if(g[0][0]==g[1][2]&&g[0][1]==g[1][1]&&g[0][2]==g[1][0])return puts("YES")*0;
    else
        cout<<"NO"<<endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.Collections;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    sc.close();
    System.out.println(Math.max(0, A - B * 2));
  }
}


Measured memory_bytes: 23252
//{{{
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < int(n); ++i)
#define REPE(i, a, b) for (int i = (a); i <= int(b); ++i)
using LL = long long;
typedef long long LL;
//}}}
int main() {
  int n;
  vector<tuple<int, int>> a;
  scanf("%d", &n);
  REP(i, n) {
    int x;
    scanf("%d", &x);
    a.emplace_back(x, 0);
  }
  REP(i, n) {
    int x;
    scanf("%d", &x);
    a.emplace_back(x, 1);
  }
  sort(a.begin(), a.end());
  int c[2] = {};
  int ans = 1;
  const int mod = 1e9 + 7;
  for (auto &it : a) {
    int x = get<1>(it);
    if (c[x^1]) ans = 1LL * ans * (c[x^1]--) % mod;
    else c[x]++;
  }
  printf("%d\n", ans);
  return 0;
}



Measured memory_bytes: 2420
import java.util.Scanner;

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

        //Nはお札の枚数
        int N = stdIn.nextInt();
       
        int Y = stdIn.nextInt();

        for (int i=0; i<=N; i++) {
            for (int j=0; j<=N-i; j++) {
                int k = N - i - j;
                int totil = i * 10000 + j * 5000 + k * 1000;
                if (totil == Y) {
                    System.out.println(i + " " + j + " " + k);
                    return;
                }
            }
        }

        System.out.println("-1 -1 -1");
    }
}

Measured memory_bytes: 21844
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		new aoj0084().doIt();
	}

	class aoj0084 {
		void doIt() {
			ArrayList<String> array = new ArrayList<String>();
			String str = sc.nextLine();
			String st= str.replace(',', ' ');
			st= st.replace('.', ' ');
			String[] ans = st.split(" ");
			for(int i = 0;i < ans.length;i++){
				if(ans[i].length() >= 3 && ans[i].length() <= 6){
					array.add(ans[i]);
				}
			}
			for(int i = 0;i < array.size()-1;i++){
				System.out.print(array.get(i)+" ");
			}
			System.out.println(array.get(array.size()-1));
		}
	}
}

Measured memory_bytes: 25972
#include<bits/stdc++.h>
using namespace std;
vector<int> sect[510];
int n,m,q;
int l,r;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
	{
		cin>>l>>r;
		sect[l].push_back(r);
	}
	for(int i=1;i<=n;i++)
		sort(sect[i].begin(),sect[i].end());
	for(int i=1;i<=q;i++){
		cin>>l>>r;
		int ans=0;
		for(int j=l;j<=r;j++){
			ans+=upper_bound(sect[j].begin(),sect[j].end(),r)\
			-sect[j].begin();
		}
		cout<<ans<<endl;
	}
	return 0;
}


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

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vi x(m);
  for (int i = 0; i < m; i++) {
    cin >> x[i];
  }
  if (m <= n) {
    cout << 0 << endl;
    return 0;
  }
  sort(x.begin(), x.end());

  vi d(m - 1);
  ll sum = 0;
  for (int i = 0; i < m - 1; i++) {
    d[i] = x[i + 1] - x[i];
    sum += d[i];
  }
  sort(d.begin(), d.end(), greater<int>());
  // for (auto& e : x) {
  //   printf("%d ", e);
  // }
  // printf("\n");
  // printf("sum=%d\n", sum);
  // for (auto& e : d) {
  //   printf("%d ", e);
  // }
  // printf("\n");

  for (int i = 0; i < n - 1; i++) {
    sum -= d[i];
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 1024
MOD = 10**9 + 7
def main():
  N, K = map(int , input().split())
  A = list(map(int, input().split()))
  
  if max(A) < 0 and K % 2 == 1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
      ans = ans*A[i]%MOD
    print(ans%MOD)
  elif K == N:
    ans = 1
    for i in A:
      ans = ans*i%MOD
    print(ans%MOD)
  else:
    A_p = []
    A_m = []
    for i in A:
      if i >= 0:A_p.append(i)
      else:A_m.append(abs(i))
    A_p.sort(reverse =  True)
    A_m.sort(reverse = True)
    num = 0
    ans = 1
    posi_p = 0
    posi_m = 0
    sign = 0
    while (num < K):
      if posi_m == len(A_m) and posi_p < len(A_p):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1
      elif posi_p == len(A_p) and posi_m < len(A_m):
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1        
      elif  A_p[posi_p] >= abs(A_m[posi_m]):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1        
      else:
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1
      if num == K and sign % 2 == 1:
        if K == 1:
          ans = A_p[0]
        elif posi_m == len(A_m):
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD) % MOD
          ans = ans*A_p[posi_p] % MOD
        elif posi_p == len(A_p):
          ans = ans*pow(A_p[posi_p-1],  MOD-2, MOD)
          ans =  ans*A_m[posi_m] % MOD
        elif A_p[posi_p]*A_p[posi_p-1] >= A_m[posi_m]*A_m[posi_m-1]:
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
          ans = ans*A_p[posi_p] % MOD
        else:
          if posi_p != 0:
            ans = ans*pow(A_p[posi_p-1], MOD-2, MOD)%MOD
            ans = ans*A_m[posi_m]%MOD
          else:
            ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
            ans = ans *A_p[posi_p]%MOD
            
    print(ans%MOD)
          
    
if __name__ == "__main__":
  main()

Measured memory_bytes: 31696
import java.util.Scanner;

public class Main{
	public static int solve(double[] p, double[] q){
		double dist = Math.sqrt((q[0]-p[0])*(q[0]-p[0])+(q[1]-p[1])*(q[1]-p[1]));
		if( dist <= p[2]+q[2] ){
			if( p[2]-dist > q[2] ){
				return 2;
			} else if( q[2]-dist > p[2] ){
				return -2;
			} else {
				return 1;
			}
		} else {
			return 0;
		}
	}
	
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		int N = stdIn.nextInt();
		int[] result = new int[N];
		
		for(int i = 0; i < N; i++){
			double[][] p = new double[2][3];
			for(int j = 0; j < 2; j++){
				for(int k = 0; k < 3; k++){
					p[j][k] = stdIn.nextDouble();
				}
			}
			result[i] = solve(p[0],p[1]);
		}
		for(int i = 0; i < N; i++){
			System.out.println(result[i]);
		}
	}
}

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

 using namespace std;
 int main() {
   int i, hit;
   string S, T;
   cin >> S >> T;
   hit = 0;
   for (i = 0; i < 3; i++) {
     if (S.at(i) == T.at(i)) hit++;
   }
   cout << hit << endl;
 }


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAX 100005
#define INF 2e9
#define ll long long int
#define fastRead ios::sync_with_stdio(0);cin.tie(0);

using namespace std;
int n;
ll v[200] , w[200] ,dp[200][MAX] , W;

int main()
{
	fastRead;
	cin>>n>>W;

	ll tot = 0;
	for(int i =1 ; i<= n ; i++ ) cin>>w[i]>>v[i] , tot +=v[i];


	ll ans = 0;
    for(int i = 1 ; i<= tot ; i++ ) {

        dp[0][i] = INF;

        for(int j = 1 ; j <= n ; j++ )  {

            if( v[j] <= i ) {
				dp[j][i] = min(dp[j-1][i] , dp[j-1][i-v[j]]  + w[j]);
            }
            else dp[j][i] = dp[j-1][i];
        }
        if(	dp[n][i] <= W) ans = max(1LL*i  , ans);
    }

    cout<<ans<<endl;
    return 0;

}



Measured memory_bytes: 80128
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000001
using namespace std;

int main(){

	double minimum = 1000.0,T,D,t_a,t_b,d_a,d_b,tmp,calc;
	int limit_a,limit_b;

	scanf("%lf %lf",&T,&D);
	scanf("%lf %lf",&t_a,&t_b);
	scanf("%lf %lf",&d_a,&d_b);

	for(double i = 1; i <= D; i += 1.0){
		limit_a = (int)floor(i/d_a);
		for(int k = 0; k <= limit_a; k++){
			limit_b = (int)floor((i - d_a*(double)k)/d_b);
			for(int p = 0; p <= limit_b; p++){
				tmp = (t_a*(d_a*(double)k)+t_b*(d_b*(double)p))/(d_a*(double)k+d_b*(double)p);
				if(minimum < EPS)break;
				calc = fabs(T-tmp);
				minimum = min(minimum,calc);
			}
		}
	}

	printf("%.6lf\n",minimum);

	return 0;
}

Measured memory_bytes: 2732
#include <iostream>
#include <cstring>
#include <set>
#include <tuple>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll x, y, z, k, a[1008], b[1008], c[1008];
set<tuple<ll, ll, ll>> s;

int main(){
	cin >> x >> y >> z >> k;
	for(ll i = 0; i < x; i++){cin >> a[i];}
	for(ll i = 0; i < y; i++){cin >> b[i];}
	for(ll i = 0; i < z; i++){cin >> c[i];}
	sort(a, a+x);
	sort(b, b+y);
	sort(c, c+z);
	
	ll ans = a[x-1]+b[y-1]+c[z-1];
	s.insert(make_tuple(x-1, y-1, z-1));
	priority_queue<pair<ll, tuple<ll, ll, ll>>> q;
	q.push(make_pair(ans, make_tuple(x-1, y-1, z-1)));
	
	for(ll time = 0; time < k; time++){
		auto buf = q.top(); q.pop();
		auto index = buf.second;
		ll xi = get<0>(index);
		ll yi = get<1>(index);
		ll zi = get<2>(index);
		cout << buf.first << endl;
		if(xi > 0 && s.find(make_tuple(xi-1, yi, zi)) == s.end()){
			q.push(make_pair(a[xi-1]+b[yi]+c[zi], make_tuple(xi-1, yi, zi)));
			s.insert(make_tuple(xi-1, yi, zi));
		}
		if(yi > 0 && s.find(make_tuple(xi, yi-1, zi)) == s.end()){
			q.push(make_pair(a[xi]+b[yi-1]+c[zi], make_tuple(xi, yi-1, zi)));
			s.insert(make_tuple(xi, yi-1, zi));
		}
		if(zi > 0 && s.find(make_tuple(xi, yi, zi-1)) == s.end()){
			q.push(make_pair(a[xi]+b[yi]+c[zi-1], make_tuple(xi, yi, zi-1)));
			s.insert(make_tuple(xi, yi, zi-1));
		}
	}
	return 0;
}

Measured memory_bytes: 896
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<string>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long 
using namespace std;
int main(){
  int N,M;
  cin >>N>>M;
  vector<int> vec(N);
  for(int i=0;i<N;i++){
    int a;
    cin >>a;
    vec[i]=a;
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  int sum=0;
  for(int i=0;i<N;i++){
    sum +=vec[i];
  }
  if(sum<=4*M*vec[M-1]){
    cout <<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    int n;
    cin>>n;
    vector<string>w(n);
    set<string>st;
    bool ans=true;
    rep(i,n){
        cin>>w[i];
    }
    rep(i,n-1){
        string s1=w[i];
        string s2=w[i+1];
        if(s1[s1.length()-1]!=s2[0]){
            ans=false;
        }
    }
    rep(i,n){
        rep(j,n){
            if(w[i]==w[j]&&i!=j){
                ans=false;
            }
        }
    }
    if(ans==true)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


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

using namespace std;

typedef long long ll;

void solve(ll a, ll b, ll v[], int m) {
    for (int i = 0; i < m; i++) {
        if ( a + b >= 0 && a - b >= 0 ) {
            cout << "R";
            a -= v[i];
        } else if ( a + b >= 0 && a - b < 0 ) {
            cout << "U";
            b -= v[i];
        } else if ( a + b < 0 && a - b >= 0 ) {
            cout << "D";
            b += v[i];
        } else {
            cout << "L";
            a += v[i];
        }
    }
    cout << endl;
    return;
}

int main() {
    int N, m = 34;
    ll X[1003], Y[1003];
    ll d[34];
    ll  t = 1;
    for (int i = 0; i < 33; i++) {
        d[32-i] = t;
        t *= 2;
    }

    cin >> N;

    int even = 0, odd = 0;
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
        if ( ( abs(X[i]) + abs(Y[i])) % 2 == 0) {
            even++;
        } else {
            odd++;
        }
    }
    if (even && odd) {
        cout << -1 << endl;
        return 0;
    }
    if (even) {
        for (int i = 0; i < 33; i++) {
            d[33-i] = d[32-i];
        }
        d[0] = 1;
    }
    if (odd) { m -= 1; }
    cout << m << endl;

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

    for (int i = 0; i < N; i++) {
        solve(X[i], Y[i], d, m);
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll INF = 1LL << 62;
const int inf = 1 << 30;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int x, a, b; cin >> x >> a >> b;
    string res = "dangerous";
    if(b <= a){
        res = "delicious";
    }
    else if(b <= a + x){
        res = "safe";
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int a[4],i,j,m,n;
	for(i=0;i<4;i++)
		scanf("%d",&a[i]);
	m=a[0]*a[1];
	n=a[2]*a[3];
	if(m>=n)
		printf("%d",m);
	else
		printf("%d",n);
	return 0;
}

Measured memory_bytes: 128
n,k= map(int,input().split())
s=input()
a=""

#print(s)
#print(s[0])
#print(s[2])
for i in range(k-1):
  a=a+s[i]
#print(a)
a=a+s[k-1].lower()
#print(a)
for i in range(n-k):
  a=a+s[i+k]
print(a)

Measured memory_bytes: 3060
# AOJ 0036: A Figure on Surface
# Python3 2018.6.27 bal4u

def judge(sr, sc, tbl):
	if 4 in sr: return 'C'
	if 4 in sc: return 'B'
	if 1 in sr: return 'F' if tbl[sr.index(1)][sc.index(2)] == 1 else 'D'
	if 1 in sc: return 'E' if tbl[sr.index(2)][sc.index(1)] == 1 else 'G'
	return 'A'

tbl = [[] for i in range(8)]
while True:
	for r in range(8): tbl[r] = list(map(int, input()))
	sr, sc = [0]*8, [0]*8
	for i in range(8): sr[i] = sum(tbl[i])
	for i in range(8): sc[i] = sum([tbl[r][i] for r in range(8)])
	print(judge(sr, sc, tbl))
	try: input()
	except: break


Measured memory_bytes: 5616
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
int n;
char f[1005][1005];
int imos[1005][1005];
int culc(int i,int j,int x)
{
	if(i-x<0||j-x<0)return 0;
	return imos[i][j]-imos[i][j-x]-imos[i-x][j]+imos[i-x][j-x];
}
int main()
{
	int cas=0;
	while(1)
	{
		cas++;
		int ans=0;
		cin >> n;
		if(n==0)break;
		memset(imos,0,sizeof(imos));
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				cin >> f[i][j];
				if(f[i][j]=='.')imos[i][j]++;
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=2;j<=n;j++)
			{
				imos[j][i]+=imos[j-1][i];
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=2;j<=n;j++)
			{
				imos[i][j]+=imos[i][j-1];
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				int l=ans,r=n+1;
				while(r-l>1)
				{
					int mid=(l+r)/2;
					if(culc(i,j,mid)==mid*mid)l=mid;
					else r=mid;
				}
				ans=max(ans,l);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 6100
#include <bits/stdc++.h>
#define F first 
#define S second 
#define endl "\n"
#define Endl "\n"
#define emdl "\n"
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
bool sortBy(const pair<int,int> &a,const pair<int,int> &b){
	if(a.F==b.F)
		return a.S<b.S;
	return a.F>b.F;
}

// #define MAXN 1001
// int pf[MAXN]; 
// void sieve(){
// 	long long int i,j; 
//     pf[1] = 1; 
//     for (i=2; i<MAXN; i++) 
//     pf[i] = i;   
//     for (i=2; i*i<MAXN; i++){ 
//         if (pf[i] == i){
//             for (j=i*i; j<MAXN; j+=i) 
//                 if (pf[j]==j) 
//                     pf[j] = i; 
//         } 
//     } 
// }
// vector<int> factors(int x){ 
//     vector<int> ret; 
//     while (x != 1){ 
// 		int fact=pf[x];
//         ret.push_back(pf[x]); 
// 		while(fac!=1&&x%fact==0)
//         x/=fact; 
//     } 
//     return ret; 
// } 
// set<long long int>poww;
// void init(){
// 	long long int temp=1;
// 	for(int i=1;i<43;i++){
// 		poww.insert(temp);
// 		temp*=2;
// 	}
// }  
// long long int power(long long int a,int n){
//     if(n==1)
//     return a;
//     if(n%2){
//         return power()
//     }
// }

int main() {		
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
	int qwe=1;
	//cin>>qwe;
	//init();
	// sieve();
	while(qwe--){
       int n;
       cin>>n;
       long long int a[n],ans=0,fin=0;

       for(int i=0;i<n;i++){
           cin>>a[i];
           fin+=a[i];
       }
       for(int i=0;i<n;i++){
           ans+=(((fin-a[i])%1000000007)*(a[i]%1000000007));
           fin-=a[i];
           ans%=1000000007;
       }
        cout<<ans;


	}

	return 0;
}


Measured memory_bytes: 5200
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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





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

	ll p[100];

	repn(i, N) cin >> p[i];

	sort(p + 1, p + N + 1);

	ll ans = p[N] / 2;

	repn(i, N - 1) ans += p[i];

	cout << ans;

	system("PAUSE");
}

Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n;
  string s;
  cin>>n>>s;
  int x=0;
  int ans=0;
  rep(i,s.size()){
    if(s[i]=='I'){
      x++;
      ans=max(ans,x);
    }
    else{
      x--;
      ans=max(ans,x);
    }
  }
  cout<<ans<<endl;
}

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

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

    vector<int> num(N+1,0);
    for(int i=0;i<M;i++){
        num[a[i]]++;
        num[b[i]]++;
    }

    for(int i=0;i<N;i++){
        cout<<num[i+1]<<endl;
    }
    

    return 0;
 
}


Measured memory_bytes: 256
<?php
  fscanf(STDIN,"%s",$a);
  $array = str_split($a);
  $ans = 0;

  for($i=0;$i<4;$i++)
  {
    if($array[$i] == "+")
    {
      $ans++;
    }
    else
    {
      $ans--;
    }
  }
  echo $ans;

Measured memory_bytes: 3576
#負の閉路検出
#n=頂点数 e=[[a,b,c],[]...](a~bの距離がc)
def find_negative_loop(n,e):
  d=n*[10**20];d[0]=0
  for h in range(n):
    for i,j,k in e:
      if d[j]>d[i]+k:
        d[j]=d[i]+k
        if h==n-1:return True
  return False

#DAG判定
#n=頂点数 e=隣接リスト
#flag=0...DAG判定　flag=1...トポロジカルソート
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in e[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in e[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t

#ベルマンフォード(d[i]=頂点sから頂点iの最短距離)
#単一始点最短経路(負の辺対応)
#s=始点 n=頂点数 e=[[a,b,c],[]...](a~bの距離がc)
def bellman_ford(s,n,e):
	inf=10**20;d=[inf]*n;d[s]=0
	while 1:
		f=True
		for i,j,k in e:
			if d[i]!=inf and d[j]>d[i]+k:d[j]=d[i]+k;f=False
		if f:break
	return d

#グラフ上でのBFS
#s=始点 n=頂点数 e=隣接リスト
def glaph_bfs(s,n,e):
  ans=[0]*n
  Q=[s]
  visited={s}
  while Q:
    P=[]
    for i in Q:
      ans[i]=1
      for j in e[i]:
        if j in visited:continue
        visited.add(j)
        P.append(j)
    Q=P
  return ans

n,m,p=map(int,input().split())
ef=[[]for _ in range(n)]
ee=[[]for _ in range(n)]
e=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  c-=p
  ef[a].append(b)
  ee[b].append(a)
  e.append([a,b,c])
eff=glaph_bfs(0,n,ef)
eef=glaph_bfs(n-1,n,ee)
edge=[]
for a,b,c in e:
  if eff[a]==1 and eef[a]==1 and eff[b]==1 and eef[b]==1:
    edge.append([a,b,-c])
if find_negative_loop(n,edge):print(-1);exit()
print(max(-bellman_ford(0,n,edge)[n-1],0))

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

int main() {
  ll n,m; cin >> n >> m;
  if(n < 1200){
    cout << "ABC";
  }
  else{
    cout << "ARC";
  }
}

Measured memory_bytes: 3572
#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <string>
#include <string.h>
#include <limits>
#include <utility>
#include <vector>
#include <algorithm>
#include <functional>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <chrono>

using namespace std;

namespace
{

}

#if 1
int main()
{
	int n;
	std::string a, b, c;
	cin >> n;
	cin >> a;
	cin >> b;
	cin >> c;

	int opeCount = 0;
	for (int i = 0; i < n; i++)
	{
		if (a[i] == b[i] && b[i] == c[i])
		{
			continue;
		}

		if (a[i] != b[i] && b[i] != c[i] && a[i] != c[i])
		{
			opeCount += 2;
			continue;
		}

		opeCount++;
	}

	cout << opeCount;

	return 0;
}
#endif


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

using namespace std;

#define fori(x) for (int i = 0; i < x; ++i)
#define forj(x) for (int j = 0; j < x; ++j)

typedef long long ll;

const int INF = 2e9 + 5;
const int alength=100100;

int main() {
	int n;
	cin>>n;
	map<string,bool> m;
	string r;
	cin>>r;
	m[r]=true;
	fori(n-1){
		string s;
		cin>>s;
		if(r.back()!=s.front()){
			cout<<"No";
			return 0;
		}
		auto itr=m.find(s);
		if(itr!=m.end()){
			cout<<"No";
			return 0;
		}
		m[s]=true;
		r=s;
	}
	cout<<"Yes";
}

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

int main() {
  int n;
  cin >> n;
  int a[n][2];
  REP(i, n) {
    cin >> a[i][0] >> a[i][1];
  }
  double sum = 0, ans = 0;
  int num = 0;
  vector<int> arr(n);
  iota(arr.begin(), arr.end(), 1);
  do {
      REP(i, arr.size()) {
        if (i == 0) continue;
        int index = arr[i]-1;
        int lastIndex = arr[i-1]-1;
        int diffx = a[index][0] - a[lastIndex][0];
        int diffy = a[index][1] - a[lastIndex][1];
        sum += sqrt((diffx * diffx) + (diffy * diffy));
      }
      num++;
  } while( next_permutation(arr.begin(), arr.end()) );
  ans = sum / num;
  cout << setprecision(10) << ans << endl;
}

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

using ll = long long;
using pll = pair<long, long>;
#define all(x) (x).begin(), (x).end()

int main() {

    ll sum = 0;
    ll n;
    cin >> n;

    ll s = sqrt(n) + 1000;
    for (int i = 1; i < s; ++i)
    {
        if ((n - i) % i == 0 && (n - i) / i > i)
        {
            sum += (n - i) / i;
        }
    }

    cout << sum;

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	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 stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXN=2005;
const int mod=1e9+7;
const int inv2=(mod+1)>>1;
int n,m,a[MAXN];
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int main()
{
	int ans=0;
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
//	for(int i=n+1;i<=n*m;i++)a[i]=a[i-n];
//	int ans1=0;
//	for(int i=1;i<=n*m;i++)for(int j=i+1;j<=n*m;j++)if(a[i]>a[j])ans1++;
//	pr2(ans1);
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(a[i]>a[j])
		ad(ans,1LL*m*(1+m)%mod*inv2%mod);
	for(int i=1;i<=n;i++)for(int j=1;j<i;j++)if(a[i]>a[j])
		ad(ans,1LL*(m-1)*m%mod*inv2%mod);
	pr2(ans);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const long long mod = 1000000007;
struct mint {
  long long x;
  mint(ll x = 0):x(x%mod) {}
  mint& operator+=(const mint a) {
    (x += a.x) %= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    (x += mod-a.x) %= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint ret(*this);
    return ret += a;
  }
  mint operator-(const mint a) const {
    mint ret(*this);
    return ret -= a;
  }
  mint operator*(const mint a) const {
    mint ret(*this);
    return ret *= a;
  }
  mint pow(ll t) const {
    if(t==0) return mint(1);
    mint a = pow(t>>1);
    a *= a;
    if(t&1) a *= *this;
    return a;
  }
  
  //for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint ret(*this);
    return ret /= a;
  }
};
ostream &operator<<(ostream& os, const mint& x) {
  os << x.x;
  return os;
}
class modutils {
  vector<mint> fact, invfact;
public:
  modutils(int n = 200005):fact(n+1),invfact(n+1) {
    fact[0] = 1;
    for(int i=1; i<=n; i++) fact[i] = fact[i-1] * i;
    invfact[n] = fact[n].inv();
    for(int i=n; i>=1; i--) invfact[i-1] = invfact[i] * i;
  }
  mint pow(mint x, ll n) {
    return x.pow(n);
  }
  mint comb(ll n, ll k) {
    if(n<0 || k<0 || n<k) return 0;
    return fact[n] * invfact[k] * invfact[n-k];
  }
  mint perm(ll n, ll k) {
    if(n<0 || k<0 || n<k) return 0;
    return fact[n] * invfact[n-k];
  }
  mint fac(ll n) {
    return fact[n];
  }
};
modutils mutil;

unordered_map<ll,mint> memo;

// 1～nまでN個使ってgcd(...)=1となる数
mint gcd1(ll n, ll N){
  if(n == 1) return mint(1);
  if(memo.count(n) == 1) return memo[n];
  
  mint ret = mutil.pow(n,N);
  REP(i,2,n+1){
    ll m = n/i;
    ret -= gcd1(m,N);
  }

  return memo[n] = ret;
}

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

  mint ret(0);
  mint cnt(0);
  REP(x,2,K+1){
    ll n = K/x;
    mint a = gcd1(n, N);
    cnt += a;
    ret += a * x;
  }
  ret += mutil.pow(K,N) - cnt;

  cout << ret << endl;
  
  return 0;
}



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

int main(){
    int n;
    int A[100];
    cin >> n;
    for (int i =0; i<n; i++){
        cin >> A[i];
    }
    for(int i =0; i<n; i++){
        int v;
        v =A[i];
        int j = i-1;
        while(1){
            if (j<0 || A[j] <=v) break;
            A[j+1] = A[j];
            j--;
        A[j+1]  =v;
        }
           cout << A[0] ;
            for (int i =1;i<n; i++){
                cout << " " << A[i] ;
            }cout << endl;
    }
    return 0;
    
}


Measured memory_bytes: 3092
import Data.List

play :: [Int] -> Int
play l = iter 0 0 (reverse (sort l)) where
    iter a b [] = a - b
    iter a b [x] = x + a - b
    iter a b (x:y:xs) = iter (a+x) (b+y) xs

readData :: IO [Int]
readData = do
    line1 <- getLine
    let xs = map (\x -> read x :: Int) (words line1)
    return xs

main :: IO() 
main = do
    n  <- readLn :: IO Int
    la <- readData
    let ans = play (take n la)
    print ans

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

#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;i++)
#define FOR(i,a,b) for(int i=(a),i##_cond=(b);i<i##_cond;i++)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumulate(all(a),0)
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second
#define mp make_pair

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<ll,ll> pii;


#define int ll

const int inf = 1ll<<62;
const int mod = 1e9+7;

main(){
  int n,c; cin >> n >> c;
  vi x(n),v(n); rep(i,n) cin >> x[i] >> v[i];
  
  vi a = v; // 時計回り
  reverse(all(v));
  vi b = v; // 逆時計
  // 累積和
  rep(i,n-1){
    a[i+1] += a[i];
    b[i+1] += b[i];
  }
  // 初期位置からの距離を引く
  rep(i,n){
    a[i] -= x[i];
    b[i] -= c - x[n-1-i];
  }

  vi maxa = a, maxb = b;
  // 累積max
  maxa[0] = max(maxa[0], 0ll);
  maxb[0] = max(maxb[0], 0ll);
  rep(i,n-1){
    maxa[i+1] = max(maxa[i+1], maxa[i]);
    maxb[i+1] = max(maxb[i+1], maxb[i]);
  }

  dump(a,b,maxa,maxb);
  
  int ans = max(maxa[n-1], maxb[n-1]);
  
  rep(i,n-1){
    int j = n - 2 - i;
    // 時計回りにi個行ってから戻って反時計
    ans = max(ans, a[i] - x[i] + maxb[j]);
    dump(ans);
    // 逆
    ans = max(ans, b[i] - (c - x[n - 1 - i]) + maxa[j]);
    dump(ans);
  }
  cout << ans << endl;
}

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

int main() {
	int x; cin >> x;
	if (400<=x && x<=599) {
		cout << 8 << endl;
		return 0;
	}
	if (600<=x && x<=799) {
		cout << 7 << endl;
		return 0;
	}
	if (800<=x && x<=999) {
		cout << 6 << endl;
		return 0;
	}
	if (1000<=x && x<=1199) {
		cout << 5 << endl;
		return 0;
	}
	if (1200<=x && x<=1399) {
		cout << 4 << endl;
		return 0;
	}
	if (1400<=x && x<=1599) {
		cout << 3 << endl;
		return 0;
	}
	if (1600<=x && x<=1799) {
		cout << 2 << endl;
		return 0;
	}
	if (1800<=x && x<=1999) {
		cout << 1 << endl;
		return 0;
	}
	
}

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

#define ll long long int
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define debug1(a) cout<<a<<"\n";
#define debug3(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n";
#define debug2(a,b) cout<<a<<" "<<b<<"\n";
#define debug4(a,b,c,d) cout<<a<<" "<< b <<" "<<c<<" "<<d<<"\n";

ll mod = 1000000007;

using namespace std;

int main()
{
	
	 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	 int n;
	 cin>>n;
	 bool mark = false;
	 for (int i = 0; i < n; ++i)
	 {
	 	int k;
	 	cin>>k;
	 	if(k%2 == 1)
	 	{
	 		mark = true;
	 	}
	 }

	 if(mark)
	 {
	 	cout<<"first\n";
	 }
	 else
	 {
	 	cout<<"second\n";
	 }
	return 0;
}

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

int main(){
  int a, b, c;
  cin >> a >> b >> c;
  int k;
  cin >> k;
  int d;
  d=max(max(a, b), max(a, c));
  int r = pow(2, k);
  cout << d*r+a+b+c-d << endl;
}

Measured memory_bytes: 256
macro_rules! scan_sub {
    ( $itr:ident, $t:ty ) => {
        let mut buf = String::new();
        let $itr = {
            while buf.trim().len() == 0 {
                buf = String::new();
                std::io::stdin().read_line(&mut buf).unwrap();
            }
            buf.split_whitespace().map(|n| n.parse::<$t>().unwrap())
        };
    };
}

macro_rules! scan {
    ( $x:ident; Vec<$t:ty> ) => {
        scan_sub!(itr, $t);
        let $x = itr.collect::<Vec<_>>();
    };
    ( $( $x:ident ),*; $t:ty ) => {
        scan_sub!(itr, $t);
        let mut itr = itr;
        $(
            let $x = itr.next().unwrap();
        )*
    };
}

fn main() {
    scan!(n, k; usize);
    scan!(brray; Vec<usize>);
    let array = brray.into_iter().map(|i| i - 1).collect::<Vec<_>>();

    let mut used = vec![None; n];
    let mut book = Vec::with_capacity(n);
    let mut entry = 0;
    let mut i = 0;
    for counter in 0..=n { // n+1 回までにはループしないとおかしい
        if !used[i].is_none() {
            entry = used[i].unwrap();
            break;
        }
        used[i] = Some(counter);
        book.push(array[i]);
        i = array[i];
    }

    let k = k - 1;
    println!("{}", if k < book.len() {
        book[k] + 1
    } else {
        let t = k - book.len();
        let loop_part = book.split_off(entry);
        loop_part[t % loop_part.len()] + 1
    });
}


Measured memory_bytes: 10068
#include <stdio.h>
#include <stdlib.h>
#define NIL NULL
 
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
 
Node root;
void Tree_insert(int);
void Tree_print(int);
 
 
int main(){
  int n,x,i;
  char c[10];
 
  scanf("%d",&n);
 
  for(i=0; i<n; i++){
    scanf("%s",c);
     
    if(c[0] == 'i'){
      scanf("%d",&x);
      Tree_insert(x);
    }
     
    if(c[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
   
  return 0;
}
 
void Tree_insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
   
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
 
   
  while(x!=NIL){
    y=x;
     
    if(z->key < x->key){
      x = x->left;
    }
     
    else{
      x = x->right;
    }
  }
    z->parent = y;
 
    if(y==NIL){
      root=z;
    }
     
    else if(z->key < y->key){
      y->left = z;
    }
     
    else {
      y->right = z;
    }
   
}
 
void inorder(Node u){
 
  if(u != NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
 
}
 
void preorder(Node u){
 
  if(u!=NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }  
}

Measured memory_bytes: 24040
N = int(input())
A = []
for _ in range(N):
    x, l = map(int, input().split())
    A.append((x+l, x-l+1))
A.sort()
now = A[0][0]
ans = 1
for r, l in A:
    if now<l:
        ans+=1
        now = r
print(ans)


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

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

  for(; N > 0; N--) {
    string s;
    cin >> s;
    if(s == "Y") break;
  }
  if(N) cout << "Four" << endl;
  else cout << "Three" << endl;
}

Measured memory_bytes: 3624
class Telepoter:
    def __init__(self, N, K, A):
        self.N = N
        self.K = K
        self.A = A
        self.path_start = 0
        self.loop_start = -1 # 未確定、get_path_and_loopで決める
        self.path_length = -1
        self.loop_length = -1

    def find_path_and_loop(self):
        visited = [False] * self.N
        visited[0] = True
        cur = self.A[0]

        while not visited[cur]:
            visited[cur] = True
            cur = self.A[cur]

        loop_start = cur
        self.loop_start = loop_start

        # get path length
        if loop_start == 0:
            path_length = 0
        else:
            path_length = 1
            cur = self.A[0]
            while cur != loop_start:
                path_length += 1
                cur = self.A[cur]
        self.path_length = path_length

        # get loop length
        loop_length = 1
        cur = self.A[loop_start]
        while cur != loop_start:
            loop_length += 1
            cur = self.A[cur]
        self.loop_length = loop_length

    def solve(self):
        self.find_path_and_loop()

        if self.K <= self.path_length:
            cur = 0
            for i in range(K):
                cur = self.A[cur]
            print(cur+1)
            return

        self.K -= self.path_length
        self.K %= self.loop_length
        cur = self.loop_start
        for i in range(self.K):
            cur = self.A[cur]
        print(cur+1)

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x-1, A))

t = Telepoter(N, K, A)
t.solve()


Measured memory_bytes: 104196
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
    
adj = [[INF]*N for _ in range(N)]
perm_list = []

def make_permutation(l,R):
    if R == 0:
        perm_list.append(l)
    else:
        for a in r:
            if a not in l:
                make_permutation(l+[a],R-1)

def main():
    for _ in range(M):
        A, B, C = map(int, input().split())
        adj[A-1][B-1] = C
        adj[B-1][A-1] = C
    
    # 方針: Warshall-Floydで各頂点間の最短距離を求めてからrの順列全探索
    for k in range(N):
        for i in range(N):
            for j in range(N):
                adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j])

    make_permutation([],R)
    ans = INF
    for ps in perm_list:
        tmp = 0
        for i in range(R-1):
            tmp += adj[ps[i]-1][ps[i+1]-1]
        ans = min(ans,tmp)
    print(ans)
    # print(perm_list)

if __name__ == "__main__":
    main()


Measured memory_bytes: 83584
function main(input){
    input = input.split(" ").map(Number);
    if(input[0] >= 10){
        console.log(input[1]);
    }else{
        console.log(input[1] + 100 * (10 - input[0]))
    }
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7500
def main():
    s = input()
    subprob = []
    substr = ''
    for i in range(len(s)):
        substr += s[i]
        # print(i, s[i])

        if i == len(s) - 1:
            subprob.append(substr)
            break

        if s[i] == 'L' and s[i + 1] == 'R':
            subprob.append(substr)
            substr = ''

    # print(subprob)

    answer = []
    for subp in subprob:
        r = subp.count('R')
        l = subp.count('L')

        border = 0
        for i in range(len(subp) - 1):
            if subp[i] == 'R' and subp[i + 1] == 'L':
                # R ... R | L ... L
                border = i

        quotient = len(subp) // 2
        reminder = len(subp) % 2
        if border % 2 == 0:
            answer += [0] * (r - 1)
            answer += [quotient + reminder] + [quotient]
            answer += [0] * (l - 1)
        else:
            answer += [0] * (r - 1)
            answer += [quotient] + [quotient + reminder]
            answer += [0] * (l - 1)

    print(' '.join(map(str, answer)))


main()

Measured memory_bytes: 13692
#include<bits/stdc++.h>
using namespace std;
#define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pi pair<int,int>
#define vi vector<int>
#define pL pair<ll,ll>
#define vL vector<ll>
#define vp vector<pi>
#define vpL vector<pL>

const int MX=2000000+5; // (R+C+1)
const ll inf=1e16;
const ll mod=1e9+7;

ll bigmod(ll b, ll p)
{
    ll ans = 1;
    for(; p; p>>=1)
    {
        if(p&1) ans = ans * b % mod;
        b = b * b % mod;
    }
    return ans;
}

ll F[MX], IF[MX];

ll nCr(ll n, ll r)
{
    return IF[r] * IF[n-r] % mod * F[n] % mod;
}

void FCT()
{
    F[0] = IF[0] = 1;
    for(int i = 1; i < MX; i++) F[i] = F[i-1] * i % mod;
    for(int i = 1; i < MX; i++) IF[i] = bigmod(F[i], mod-2);
}


ll tableSum(ll r1, ll c1, ll r2, ll c2)
{
    ll sm=0;
    for(int i = r1; i <= r2; i++)
    {
        sm =(sm + nCr(i + c2 + 1, c2))      % mod;
        sm=(sm - nCr(i + c1, c1 - 1) + mod) % mod;
    }
    return sm;
}

int main()
{
    FasterIO;

    FCT();

    ll r1, c1, r2, c2;

    cin >> r1 >> c1 >> r2 >> c2;

    ll sm = tableSum(r1, c1, r2, c2);

    cout << sm << endl;

    return 0;
}


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

using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> x(n), y(n);
    vector<ll> xv(n), yv(n);
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        xv[i] = x[i];
        yv[i] = y[i];
    }
    xv.erase(unique(xv.begin(), xv.end()), xv.end());
    yv.erase(unique(yv.begin(), yv.end()), yv.end());

    sort(xv.begin(), xv.end());
    sort(yv.begin(), yv.end());

    // 座標を照準で何番目かに圧縮
    int h = xv.size() + 1;
    int w = yv.size() + 1;
    vector<vector<int> > fld(h, vector<int>(w, 0));
    for(int i = 0; i < n; i++) {
        int idx_x = (int)(lower_bound(xv.begin(), xv.end(), x[i]) - xv.begin());
        int idx_y = (int)(lower_bound(yv.begin(), yv.end(), y[i]) - yv.begin());
        ++idx_x, ++idx_y;
        fld[idx_x][idx_y] = 1;;
    }

    // 累積和を計算
    for(int i = 1; i < h; i++) {
        for(int j = 1; j < w; j++) {
            fld[i][j] += fld[i-1][j] + fld[i][j-1] - fld[i-1][j-1];
        }
    }

    ll ans = __LONG_LONG_MAX__;
    for(int xi = 0; xi < h-1; xi++) {
        for(int xj = xi+1; xj < h-1; xj++) {
            for(int yi = 0; yi < w-1; yi++) {
                for(int yj = yi+1; yj < w-1; yj++) {
                    int num = fld[xi][yi] - fld[xj+1][yi] - fld[xi][yj+1] + fld[xj+1][yj+1];
                    if(num >= k) {
                        // cout << xj << " " << xi << ":: " << xv[xj]  << " " << xv[xi] << endl;
                        ans = min(ans, (xv[xj] - xv[xi]) * (yv[yj] - yv[yi]));
                    }
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
#n,k= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しに4 3sum変数使用はsum関数使用できないので注意
print(a[:4],a[4:])

Measured memory_bytes: 5076
#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int ara[n+1],i;
    long long sum=0;
    for(i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        sum+=x;
        ara[i]=x;
        //printf(" %d ",ara[i]);
    }
    //printf("= %lld\n\n",sum);
    int m;
    scanf("%d",&m);
    while(m--){
        int a,b;
        scanf("%d %d",&a,&b);
        int p=sum-ara[a];
        //printf(" 1= %d \n",p);
        p=p+b;
        printf("%d\n",p);
    }

    return 0;
}


Measured memory_bytes: 128
from collections import defaultdict
from itertools import accumulate

N=int(input())
A=[int(x) for x in input().split()]
cnt=list(accumulate(A))

ans=0
res=defaultdict(int)
for a in cnt:
  if a==0:
    res[a]+=1
    ans+=res[a]
  elif res[a] > 0:
    ans+=res[a]
    res[a]+=1
  else:
    res[a]=1

print(ans)

Measured memory_bytes: 41472
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cstring>
using namespace std;
long long int mod = 1e9 + 7;
template <class T>
void inputV(vector<T> &x, int n){
  for(int i=0; i<n; i++) cin >> x[i];
}

int main() {
  int n; cin >> n;
  vector<int> t(n+1, 0);
  vector<int> v(n);
  for(int i=1; i<=n; i++){
    cin >> t[i];
    t[i] += t[i-1];
  }
  for(int i=0; i<n; i++) cin >> v[i];
  vector<double> mv(40010, 0.0);
  for(int i=1; i<=n; i++){
    for(int j=t[i-1]*2+1; j<=t[i]*2; j++){
      mv[j] = min(mv[j-1]+0.5, v[i-1]*1.0);
    }
  }

  mv[t[n]*2] = 0.0;
  for(int i=n; i>=1; i--){
    for(int j=t[i]*2; j>=t[i-1]*2+1; j--){
      mv[j-1] = min({mv[j]+0.5, mv[j-1], v[i-1]*1.0});
    }
  }
  double ans = 0.0;
  for(int i=0; i<=t[n]*2; i++){
    ans += (mv[i]+mv[i+1])/4;
  }
  printf("%.4lf\n", ans);

  return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
int main(void) {
  int n, m, i, total = 0, mato;
  scanf("%d", &n);
  while(n != 0) {
    total = 0;
    m = n /4;
    for(i = 0; i < m; i++){
      scanf("%d", &mato);
      total = total + mato;
    }
    printf("%d\n", total);
    total = 0;
    scanf("%d", &n);
  }
  return 0;
}

Measured memory_bytes: 600
#include <stdio.h>

int gcd(int a, int b)
{
	if(b == 0){
		return a;
	} else {
		return gcd(b, a%b);
	}
}

int lcm(int a, int b){
	if ((a==0)||(b==0)){
		return 0;
	}
	return ((a / gcd(a, b)) * b);
}

int main(void){
	int a,b,x,y;
	while(scanf("%d %d",&a,&b)!=EOF){
		x=gcd(a,b);
		y=lcm(a,b);
		printf("%d %d\n",x,y);
	}
}

Measured memory_bytes: 1024