akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int K;
    string S;
    cin>>K>>S;
    if(S.size()<=K){
        cout<<S<<endl;
    }
    if(S.size()>K){
        for(int i=0;i<K;i++){
            cout<<S[i];
        }
         cout<<"..."<<endl;
    }
}


Measured memory_bytes: 3624
import sys, os

f = lambda:list(map(int,input().split()))
a = ["dream", "dreamer", "erase", "eraser"]
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

t = input().strip()
t = t[::-1]

def solve():
    s = ""
    for i in range(len(a)):
        a[i] = a[i][::-1]


    end = 0
    lent = len(t)
    while(len(s)<len(t)):
        ok = False
        for i in a:
            if len(s) + len(i) <= lent and i == t[len(s): len(s) + len(i)]:
                s += i
                ok = True

        if ok == False:
            print("NO")
            return
    
    print("YES")

solve()


Measured memory_bytes: 3316
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

int arr[55556]={};
void era(int n){
  arr[0]=0;
  arr[1]=0;
  for(int i=2;i<=n;i++){
    arr[i]=1;
  }
  for(int i=2;i<=sqrt(n);i++){
    if(arr[i]){
      for(int j=0;i*(j+2)<=n;j++){
        arr[i*(j+2)]=0;
      }
    }
  }
}

int main(){
  int n;
  cin>>n;
  if(n==5){
    cout<<"3 5 7 11 31"<<endl;
    return 0;
  }else if(n==6){
    cout<<"2 3 5 7 11 13"<<endl;
    return 0;
  }
  int N=55555;
  era(N);
  int ans[n+1]={};
  vector<int> x1,x2;
  for(int i=4;i<=N;i++){
    if(arr[i]){
      if(i%5==3){
        x1.push_back(i);
        //cout<<i<<endl;
      }
    }
  }
  for(int i=0;i<n-1;i++){
    cout<<x1[i]<<" ";
    if(i==n-2){
      cout<<x1[i+1]<<endl;
      return 0;
    }
  }
  return 0;
}


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

bool is_prime(int k)
{
	for(int j=2;j*j<=k;j++){
		if(k%j==0) {
			return false;
		}
	}
    return true;
}

int main()
{
    stringstream ss;
    // 入力
    int N;
    cin>>N;
    int ans=0;

    for(int i=1;i<=N;i+=2){
    	int divnum=0;
    	for(int j=1;j<=i;j++){
    		if(i%j==0) divnum++;
    	}
    	if(divnum==8){
    		ans++;
    	}
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 384
#define _CRT_SECURE_NO_WARNINGS
//#define _USE_MATH_DEFINES
#include<stdio.h>
//#include<stdlib.h>
//#include<math.h>
//#include<string.h>
//#include<time.h>
#define P(type,x) fprintf(stdout,"%"#type"\n",x)
typedef struct {
	int point;
	char team[32];
}LEAGUE;

LEAGUE d[10];
int n;
void sort();
int main() {
	int a,c, f=0, i;
	while (fscanf(stdin, "%d", &n), n) {
		for (i = 0; i < n; i++)
			fscanf(stdin, "%s %d%*d%d", d[i].team, &a, &c),getchar(),d[i].point = a * 3 + c;
		if (f) puts("");
		sort();
		for (i = 0; i < n; i++,f=1) fprintf(stdout, "%s,%d\n", d[i].team, d[i].point);
	}
	return 0;
}

void sort(){
	int i, j;
	LEAGUE tmp;
	for (i = 0; i < n-1; i++)
		for(j=n-1;j>i;j--)
		if (d[j-1].point < d[j].point)
			tmp = d[j-1], d[j-1] = d[j], d[j] = tmp;
}

Measured memory_bytes: 620
#include <iostream>
#include <vector>
#include <utility>
#include <set>
#define llint long long
#define mod 998244353

using namespace std;

llint n;
vector<llint> S[200005], T[200005];
set<pair<llint, llint> > s;

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

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	llint u, v;
	for(int i = 1; i <= n-1; i++){
		cin >> u >> v;
		S[u].push_back(v);
		S[v].push_back(u);
	}
	for(int i = 1; i <= n-1; i++){
		cin >> u >> v;
		T[u].push_back(v);
		T[v].push_back(u);
		if(u > v) swap(u, v);
		s.insert(make_pair(u, v));
	}
	
	llint ans = n*(n-1) % mod * modpow(4, mod-2) % mod;
	
	llint tmp = (n-2) * (n-1) % mod * modpow(8, mod-2);
	tmp *= 2, tmp %= mod;
	ans += mod - tmp, ans %= mod;
	
	tmp = (n-1)*(n-1) % mod;
	for(int i = 1; i <= n; i++){
		tmp += mod - (llint)S[i].size() * (llint)T[i].size() % mod;
		tmp %= mod;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < S[i].size(); j++){
			if(S[i][j] < i) continue;
			if(s.count(make_pair(i, S[i][j]))) tmp++, tmp %= mod;
		}
	}
	ans += tmp * modpow(16, mod-2) % mod;
	ans %= mod;
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 40708
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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; }

int N,M,R,A,B,C,cost,ans=1e9;
int d[200][200];

void warshall_floyd(int n) { // nは頂点数
  for (int i = 0; i < n; i++)      // 経由する頂点
    for (int j = 0; j < n; j++)    // 開始頂点
      for (int k = 0; k < n; k++)  // 終端
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}

int main(){
    cin>>N>>M>>R;
    vector<int> r(R);
    rep(i,200){
      rep(j,200){
        d[i][j]=10000000;
      }
    }
    rep(i,R)cin>>r[i];
    rep(i,M){
        cin>>A>>B>>C;
        d[A-1][B-1]=C;
        d[B-1][A-1]=C;
    }
    sort(r.begin(),r.end());
    warshall_floyd(N);
    do{
        cost=0;
        rep(i,R-1){
          cost+=d[r[i]-1][r[i+1]-1];
        }
        if(cost<ans)ans=cost;
    }while(next_permutation(r.begin(),r.end()));
    out(ans);
}


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

// #include <atcoder/all>

// #LIB#

using namespace std;
// using namespace atcoder;
using ll = long long;
#define double long double
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x, c) for (auto&& x : (c))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))
#ifdef ONLINE_JUDGE
#define endl _endl
const char _endl = (cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout.precision(16), '\n');
#endif

int main() {
  ll n, x, m;
  cin >> n >> x >> m;
  vector<ll> pm(m), loopsum(m + 1), loopirev(m + 1);
  rep(i, m) pm[i] = (i * i) % m;
  vector<bool> seen(m);
  ll cur = x, i = 0;
  while (!seen[cur]) {
    seen[cur] = true;
    loopirev[cur] = i;
    loopsum[i + 1] = loopsum[i] + cur;
    ++i;
    cur = pm[cur];
  }
  ll loopbeginindex = loopirev[cur];
  ll loopendindex = i;
  ll loop1s = loopsum[loopendindex] - loopsum[loopbeginindex];
  ll ans = 0;
  if (n < loopbeginindex) {
    ans = loopsum[n];
  } else {
    ll nn = n - loopbeginindex;
    ll li = loopendindex - loopbeginindex;
    ans = loop1s * (nn / li) + loopsum[loopbeginindex + (nn % li)];
  }
  cout << ans << endl;
}


Measured memory_bytes: 5556
n=int(input())
t=list(map(int,input().split()))
v=list(map(int,input().split()))
T=sum(t)
d=[0 for _ in range(2*T+2)]
l=[0]
for i in range(n):
    for j in range(t[i]*2):
        l.append(v[i])
l.append(0)
for i in range(2*T):
    d[i+1] = min(d[i]+0.5,l[i+1])

l.reverse()
d2=[0 for _ in range(2*T+2)]

for i in range(2*T):
    d2[i+1] = min(d2[i]+0.5,l[i])

d2.reverse()
l.reverse()

d3=[0 for _ in range(2*T+2)]
for i in range(2*T+1):
    d3[i]= min(d[i],d2[i])

res = 0
for i in range(T*2):
    res += (d3[i]+d3[i+1])/4
print(res)

Measured memory_bytes: 47600
solve :: [Int] -> Int
solve [a,b,c,x,y] =
        if a + b > 2 * c
           then (2 * c * min x y) +
               if d > 2 * c then 2 * c * z
                            else d * z
           else (a * x) + (b * y)
  where
    (z,d) = case x of _ | x < y     -> (y-x, b)
                        | x > y     -> (x-y, a)
                        | otherwise -> (0, 0)

main :: IO ()
main = print =<< solve . map read . words <$> getLine

Measured memory_bytes: 508
#pragma GCC optimize ("O2")
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-label"

#define DEBUG 1
#define dd if (DEBUG)

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, A) for (auto & a : A)
#define all(a) (a).begin (), (a).end ()
#define rall(a) (a).rbegin (), (a).rend ()
#define sz(a) (int) (a).size ()
#define szl(a) (int) (a).length ()
#define FASTIO cin.sync_with_stdio (0); cin.tie (0); cin.exceptions (cin.failbit);

typedef long long ll;
typedef pair <int, int> pii;
#define f first
#define s second
#define mp(a, b) make_pair((a), (b))
typedef vector <int> vi;
typedef vector <vi> mi;
typedef vector <ll> vll;
typedef vector <vll> mll;
#define pb(a) push_back ((a))

const ll MOD = 1e+9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int INFi = 0x3f3f3f3f;
const ll MAXN = 1e+6+7;

int main ()
{
    FASTIO;
    int i, j, n, mn = -1, sum = 0;
    cin >> n;
    vi A (n);
    trav (a, A)
    {
        cin >> a;
        if (mn == -1)
        {
            mn = a;
            ++sum;
        }
        else if (a < mn)
        {
            mn = a;
            ++sum;
        }
    }
    cout << sum << '\n';
    

    return 0;
}




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

using namespace std;

typedef long long ll;
typedef vector<ll> vll;

#define pb push_back
#define mp make_pair

#define mod 1000000007

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define vin(v, n) for (int i = 0; i < (int)(n); i++) cin >> (v)[i];

vll primes(1e7, 1);
void sieve() {
	for (ll i = 2; i < 1e7; i++) {
		if (primes[i] == 1) {
			for (ll j = 2 * i; j < 1e7; j++) {
				primes[j] = 0;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	sieve();
	
	vector<pair<ll, ll>> nums;

	ll n;
	cin >> n;

	map<ll, ll> counts;
	unordered_set<ll> uniq;
	for (ll i = 0; i < n; i++) {
		ll a;
		cin >> a;

		counts[a]++;

		nums.pb(mp(a, i));

		uniq.insert(a);
	}

	sort(all(nums));

	if (uniq.find(1) != uniq.end()) {
		if (counts[1] > 1) cout << 0;
		else cout << 1;
	}
	else {
		ll ans = 0;
		for (ll i = 0; i < n; i++) {
			if (counts[nums[i].first] == 1) {
				//cout << nums[i].first << endl;
				if (primes[nums[i].first]) {
					ans++;
				}

				else {
					bool can = true;
					for (ll j = 2; j * j <= nums[i].first; j++) {
						if (nums[i].first % j == 0) {

							if (uniq.find(j) != uniq.end() || uniq.find(nums[i].first / j) != uniq.end()) {
								//cout << "found " << j << endl;
								can = false;
								break;
							}
						}
					}

					if (can) ans++;
				}
			}
		}

		cout << ans;
	}

}


Measured memory_bytes: 105180
import itertools
N,M,Q = map(int,input().split())
x = [list(map(int,input().split()))  for _ in range(Q)]
d=0
ans=0
B=[]

#Aの場合の数を全列挙
ele = [k for k in range(1,M+1)]

for i in itertools.combinations_with_replacement(ele,N):
  A = list(i)
  d=0
  for j in range(Q):
    if A[x[j][1]-1] - A[x[j][0]-1] == x[j][2]:
      d += x[j][3]
      
  else:
    if d>ans:
      ans = d
     
print(ans)

Measured memory_bytes: 9096
#include <stdio.h>

int main(void)
{
	int i, n, temp, max, min;
	long sum = 0;

	max = -1000000;
	min = 1000000;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		
		scanf("%d", &temp);

		sum += temp;

		if (temp > max) {
			max = temp;
		}

		if (temp < min) {
			min = temp;
		}
	}

	printf("%d %d %ld\n", min, max, sum);

	return 0;
}

Measured memory_bytes: 600
#include<cassert>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
LL Abs(LL x)
{
	return x<0?-x:x; 
}
int n,m;
int d[40];
int x[1005],y[1005];
bool judge(LL x,LL y,int t)
{
	return Abs(x)+Abs(y)<d[t+1]; 
}
void print(LL x,LL y,int step)
{
	if(step==-1)
	{
		return;
	}
	if(judge(x+d[step],y,step-1))
	{
		print(x+d[step],y,step-1);
		printf("L");
		return;
	}
	if(judge(x-d[step],y,step-1))
	{
		print(x-d[step],y,step-1);
		printf("R");
		return;
	}
	if(judge(x,y+d[step],step-1))
	{
		print(x,y+d[step],step-1);
		printf("D");
		return;
	}
	if(judge(x,y-d[step],step-1))
	{
		print(x,y-d[step],step-1);
		printf("U");
		return;
	}
	assert(0);
}
bool solve()
{
	int r=(x[1]+y[1])&1;
	for(int i=2;i<=n;++i)
	{
		if(((x[i]+y[i])&1)!=r)
		{
			return false;
		}
	}
	m=31;
	d[0]=1;
	for(int i=1;i<m;++i)
	{
		d[i]=d[i-1]<<1;
	}
	d[m]=1;
	if(r==1)
	{
		printf("%d\n",m);
		for(int i=0;i<m;++i)
		{
			if(i) printf(" ");
			printf("%d", d[i]);
		}
		printf("\n");
	} 
	else
	{
		printf("%d\n",m+1);
		printf("1");
		for(int i=0;i<m;++i)
		{
			printf(" %d",d[i]);
		}
		printf("\n");
		for(int i=1;i<=n;++i)
		{
			++x[i];
		}
	}
	for(int i=1;i<=n;++i)
	{
		if(r==0)
		{
			printf("L");
		}
		print(x[i],y[i],m-1);
		printf("\n");
	}
	return true;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&x[i],&y[i]);
	}
	if(!solve())
	{
		printf("-1\n");
	}
	return 0; 
} 

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;


public class Main {
	 static class FastReader 
	    { 
	        BufferedReader br; 
	        StringTokenizer st; 
	       
	  
	        public FastReader() 
	        { 
	            br = new BufferedReader(new
	                     InputStreamReader(System.in)); 
	        } 
	  
	        String next() 
	        { 
	            while (st == null || !st.hasMoreTokens()) 
	            { 
	                try
	                { 
	                    st = new StringTokenizer(br.readLine()); 
	                } 
	                catch (IOException  e) 
	                { 
	                    e.printStackTrace(); 
	                } 
	            } 
	            return st.nextToken();
	            
	        } 
	  
	        int nextInt() 
	        { 
	            return Integer.parseInt(next()); 
	        } 
	  
	        long nextLong() 
	        { 
	            return Long.parseLong(next()); 
	        } 
	  
	        double nextDouble() 
	        { 
	            return Double.parseDouble(next()); 
	        } 
	  
	        String nextLine() 
	        { 
	            String str = ""; 
	            try
	            { 
	                str = br.readLine(); 
	            } 
	            catch (IOException e) 
	            { 
	                e.printStackTrace(); 
	            } 
	            return str; 
	        }

			public Character charAt(int i) {
				// TODO Auto-generated method stub
				return null;
			} 
	    }

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

	/**
	 * @param args
	 * @throws IOException
	 */

	public static void main(String[] args)throws IOException  {
		FastReader s=new FastReader();		
		int d = s.nextInt();
		int t = s.nextInt();
		int sp = s.nextInt();
		if((double)d/sp<=t)System.out.println("Yes");
		else System.out.println("No");
		
		
		
	}
}
	



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

int main() {

  long long int A,B,V,W,T; 

  cin >>A>>V>>B>>W>>T;
  
  long long int Dist;
  long long int speed;
  if(W>=V){
    cout<<"NO"<<endl;
  }
  if(V>W){
  speed=V-W;
  if (A>B) {
   Dist=A-B;
  }
  if(B>A){
    Dist=B-A;
  }
  if(speed*T>=Dist){
    cout<<"YES"<<endl;
  }
      if(speed*T<Dist){
    cout<<"NO"<<endl;
  }
    
  }
 return 0;
}

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

#define y1 as214
#define ii pair < int , ll >
#define iii pair < int , ii >
#define iv pair < ii , ii >

#define fi first
#define se second
#define fr front()
#define pb push_back

#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)
#define REP(i , n) for(int i = 0 ; i < n ; ++i)

#define ll long long
#define oo INT_MAX

/// dp[i] là quãng đường dài nhất để xuất phát từ 1 và kết thúc tại i.

const int N = 1e5 + 5;
ll n;
ll dp[N] , f[N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    FOR(i , 1 , n)
        cin >> f[i];
    dp[1] = 0;
    dp[2] = abs(f[2] - f[1]);
    FOR(i , 3 , n)
        dp[i] = min(dp[i - 1] + abs(f[i] - f[i - 1]) , dp[i - 2] + abs(f[i] - f[i - 2]));
    cout << dp[n] << endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
string s;
long long ans=0,pow3[100005];
int main()
{
	cin>>s;
	long long cur=1;
	pow3[0]=1;
	for(int i=1;i<s.size();i++)
	{
		pow3[i]=pow3[i-1]*3;
		pow3[i]%=1000000007;
	}
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='1')
		{
			ans+=cur*pow3[s.size()-1-i];
			cur*=2;
			ans%=1000000007;
			cur%=1000000007;
		}
	}
	ans+=cur;
	cout<<ans%1000000007<<endl;
	return 0;
}


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

int main() {
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  
  if (e-a<=k && e-b<=k && e-c<=k && e-d<=k && d-a<=k && d-b<=k && d-c<=k && c-a<=k && c-b<=k && b-a<=k) {
  
  cout << "Yay!";
  }
  
  else {
    cout << ":(";
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <utility>
#include <algorithm>
#include <functional>
#include <deque>
#define INF 1000000000
#define MOD 1000000007
#define mod(x) ((x % MOD) + MOD) % MOD

using namespace std;

typedef long long ll;
typedef pair<int,int> P;

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

  ll map_o[] = {0, 2, 3, 1};
  ll map_x[] = {2, 0, 1, 3};
  char animal[] = {'S', 'S', 'W', 'W'};

  for (ll start = 0; start < 4; start++) {

    queue<ll> que;
    que.push(start);

    ll tmp = start;
    for (ll i = 0; i < N; i++) {
      if (s[i] == 'o') {
        tmp = map_o[tmp];
      } else {
        tmp = map_x[tmp];
      }
      que.push(tmp);
    }

    if (tmp == start) {
      while (que.size() > 1) {
        printf("%c", animal[que.front()]);
        que.pop();
      }
      printf("\n");
      return 0;
    }

  }

  cout << -1 << endl;

  return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef pair<int,int> pii;
typedef pair<long long, int> pli;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

ll mod = 1000000007;

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

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

  int n;
  cin >> n;

  vi a(n),b(n);

  rep(i,n)cin >> a[i] >> b[i];

  if(n % 2 == 1){
    int m = (n-1)/2;
    sort(all(a));
    sort(all(b));
    int l = a[m], r = b[m];
    cout << r - l + 1 << endl;
  }else{
    int lm = n/2 - 1, rm = n/2;
    sort(all(a));
    sort(all(b));
    int l_l = a[lm], l_r = b[lm];
    int r_l = a[rm], r_r = b[rm];

    ll ret = (r_r + l_r)/2 - (r_l + l_l)/2 + 1;
    ret = ret * 2 - 1;
    if((r_r + l_r)%2 == 1)ret++;
    if((r_l + l_l)%2 == 1)ret--;

    cout << ret << endl;
  }
}

Measured memory_bytes: 4780
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
using namespace std;
typedef int64_t ll;
typedef vector<ll> vll;
struct Solution {
    void solve(std::istream& in, std::ostream& out) {
        ll N, M;
        in >> N >> M;
        vll ab;
        rep(i, M) {
            ll a, b;
            in >> a >> b;
            if (a == 1) {
                ab.push_back(b);
            }
            if (b == N) {
                ab.push_back(a);
            }
        }
        sort(ab.begin(), ab.end());
        bool ans = false;
        rep(i, (int)ab.size() - 1) {
            if (ab[i] == ab[i + 1]) {
                ans = true;
                break;
            }
        }
        out << (ans ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    }
};
void solve(std::istream& in, std::ostream& out) {
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}
#include <fstream>
#include <iostream>
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;
    solve(in, out);
    return 0;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_V 100
#define MAX_E 10000
 
int V,E,par[MAX_V],rnk[MAX_V];
 
struct Colony{
    double x,y,z,r;
    Colony(){}
    Colony(double x,double y,double z,double r) : x(x),y(y),z(z),r(r) {}
};
 
struct Edge{
    int u,v;
    double dist;
    Edge(){}
    Edge(int u,int v,double dist) : u(u),v(v),dist(dist) {}
};
 
bool comp(const Edge &e1,const Edge &e2){
    return e1.dist < e2.dist;
}
 
Edge es[MAX_E];
 
void init(){
    for(int i = 0 ; i < V ; i++){
	par[i] = i;
	rnk[i] = 0;
    }
}
 
int find(int x){
    if(par[x] == x){
	return x;
    }
    return par[x] = find(par[x]);
}
 
void unite(int x,int y){
    x = find(x);
    y = find(y);
 
    if(x == y) return;
 
    if(rnk[x] < rnk[y]){
	par[x] = y;
    }else{
	par[y] = x;
	if(rnk[x] == rnk[y]){
	    rnk[x]++;
	}
    }
}
 
bool same(int x,int y){
    return find(x) == find(y);
}
 
double kruskal(){
    sort(es,es+E,comp);
    init();
    double res = 0.0;
    for(int i = 0 ; i < E ; i++){
	Edge e = es[i];
	if(!same(e.u,e.v)){
	    unite(e.u,e.v);
	    res += e.dist;
	}
    }
    return res;
}
 
double getDist(const Colony &c1,const Colony &c2){
    return sqrt(pow(c1.x-c2.x,2)+pow(c1.y-c2.y,2)+pow(c1.z-c2.z,2))-c1.r-c2.r;
}
 
int main(){
    while(cin >> V,V){
	E = 0;
	double x,y,z,r;
	Colony C[MAX_V];
	for(int i = 0 ; i < V ; i++){
	    cin >> x >> y >> z >> r;
	    C[i] = Colony(x,y,z,r);
	}
     
	for(int i = 0 ; i < V ; i++){
	    for(int j = i+1 ; j < V ; j++){
		double dist = getDist(C[i],C[j]);
		es[E++] = Edge(i,j,max(dist,0.0));
	    }
	}
	printf("%.3f\n",kruskal());
    }
    return 0;
}

Measured memory_bytes: 3144
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }
void Taka() { cout << "Takahashi" << endl; }
void Aoki() { cout << "Aoki" << endl; }
void digit(int d) { cout << fixed << setprecision(d); }
void IOup() { cin.tie(0); ios::sync_with_stdio(false); }

int a[100001];
bool used[100001];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];

	int s = 1, ans = 0;
	while (1) {
		ans++;
		used[s] = true;
		s = a[s];
		if (used[s]) {
			ans = -1;
			break;
		}
		if (s == 2)
			break;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 768
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vvvvll = vector<vector<vector<vector<ll>>>>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define vllin(x,n) vll (x)(n);FOR(i,0,n-1){cin >>(x)[i];}
#define vllin2(a,b,n) vll (a)(n);vll (b)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vllin3(a,b,c,n) vll (a)(n);vll (b)(n);vll (c)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vlling(x,n) (x).assign(n,0);FOR(i,0,n-1){cin >>(x)[i];}
#define vlling2(a,b,n) (a).assign(n,0);(b).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vlling3(a,b,c,n) (a).assign(n,0);(b).assign(n,0);(c).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vpl4in(x,n) vpl4 (x)((n),mp(0,0));FOR(i,0,n-1){cin >>x[i].fi>>x[i].se;}
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define says(x) cout<<(x)<<(' ');
#define sas cout<<(' ');
#define sayR(x) cout<<fixed<<setprecision(10)<<(x);
#define salR(x) cout<<fixed<<setprecision(10)<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define pow(a,b) ll(pow(a,b))

ll MOD=1000000007;

signed main(){
        llin(n);
        llin(a);
        llin(b);
        llin(c);
        llin(d);
        stin(s);
        ll e=max(c,d);
        FOR(i,a,e-3){
                if(s[i]=='#'&&s[i+1]=='#'){
                        sal("No");
                        return 0;
                }
        }
        if(c<d){
                sal("Yes");
                return 0;
        }
        if(c==d){
                sal("No");
                return 0;
        }
        FOR(i,b-2,d-2){
                if(s[i]=='.'&&s[i+1]=='.'&&s[i+2]=='.'){
                        sal("Yes");
                        return 0;
                }
        }
        sal("No")
}

Measured memory_bytes: 640
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds; 

#define int long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define f first
#define s second
#define sz(x) (int)x.size()
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout << (x) << endl
#define watch2(x,y) cout << (x) << " " << (y) << endl
#define watch3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.14159265358979323846

typedef long long ll;
typedef long double ld; 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> oset;

// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

const int mod = 1e9 + 7;
const int inf = 9e18;
const int N = 1e5 + 5;

int n,m,q,a[55],b[55],c[55],d[55],score=0;

void dfs(int level,int val,vi ans){
    ans.pb(val);
    if(level==n){
        int temp=0;
        for(int i=1;i<=q;++i){
            if(ans[b[i]-1]-ans[a[i]-1]==c[i]){
                temp+=d[i];
            }
        }
        score=max(score,temp);
        return;
    }
    for(int i=val;i<=m;++i){
        dfs(level+1,i,ans);
    }
}

void solve(){
    cin>>n>>m>>q;
    for(int i=1;i<=q;++i){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }
    vi ans;
    for(int i=1;i<=m;++i){
        dfs(1,i,ans);
    }
    cout<<score;
}

signed main(){
    fastio;
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 3596
#include<map>
#include<bits/stdc++.h>
#include<string>
#include<algorithm>
typedef long long int ll;
using namespace std;
#define MAXN 100005
#define X first
#define Y second
#define MOD 1000000007
#define inf 1e9
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
ll n,i,j,t;

vector<vector<ll > > adj(MAXN,vector<ll >());
ll u,v;
vector<ll > val(MAXN,0);
vector<bool > used(MAXN,false);
map<pair<ll,ll >,ll > mp;
vector<ll > ans(MAXN);
ll max_ans=0;

void dfs(ll a){
    used[a]=true;
    ll cnt=1;
    for(auto to:adj[a]){
        if(!used[to]){
            if(cnt==val[a]) cnt++;
            val[to]=cnt;
            max_ans=max(cnt,max_ans);
            ans[mp[{a,to}]]=cnt++;
            dfs(to);
        }
    }
}

int main()
{
    fastio;
    cin>>n;
    for(i=0;i<n-1;i++){
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
        mp[{u,v}]=i;
        mp[{v,u}]=i;
    }
    dfs(1);
    cout<<max_ans<<endl;
    for(i=0;i<n-1;i++) cout<<ans[i]<<endl;
}


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

ans = dict()
ans['AC'] = 0
ans['WA'] = 0
ans['TLE'] = 0
ans['RE'] = 0
for i in range(N):
    S = input()
    ans[S] += 1
        
print("AC x", ans['AC'])
print("WA x", ans['WA'])
print("TLE x", ans['TLE'])
print("RE x", ans['RE'])

Measured memory_bytes: 9204
fn run() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let s: Vec<char> = s.trim().chars().collect();
    let n = s.len();
    let ans = match (s[0] == s[n - 1], n % 2 == 0) {
        (true , true ) => "First",
        (true , false) => "Second",
        (false, true ) => "Second",
        (false, false) => "First",
    };
    println!("{}", ans);
}

fn main() {
    run();
}

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

int main(){
    int n;
    cin>>n;
    long long int a[n],sum=0;
    std::map<int,long long int> m;
    auto it= m.begin();
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
        it=m.find(a[i]);
        if(it!=m.end())
            (*it).second++;
        else
            m[(a[i])]=1;
    }
    
    long long int g,b,c;
    cin>>g;
    for(int i=0;i<g;i++){
        cin>>b>>c;
        it = m.find(b);
        if(it!=m.end() && (*it).second!=0){
            auto it2=m.find(c);
            if(it2==m.end())
                m[c]=(*it).second;
            else
                m[c]+=(*it).second;
            
            sum+=((*it).second*(c-b));
            (*it).second=0;
        }
        cout<<sum<<endl;
    }
    
}

Measured memory_bytes: 9016
package main

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

const pi = math.Pi

var mod int = pow(10, 9) + 7
var Umod uint64 = 1000000007
var ans, cnt, sum int

func main() {
	reader.Split(bufio.ScanWords)
	N, _ := strconv.Atoi(read())
	fmt.Println(pow(N, 3))
}

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

var reader = bufio.NewScanner(os.Stdin)

func read() string {
	reader.Scan()
	return reader.Text()
}

func lcm(x, y int) int {
	return (x / gcd(x, y)) * y
}

func gcd(x, y int) int {
	if x%y == 0 {
		return y
	} else {
		r := x % y
		return gcd(y, r)
	}
}

var fac [1000000]int
var finv [1000000]int
var inv [1000000]int

func combination_init() {
	fac[0], fac[1] = 1, 1
	finv[0], finv[1] = 1, 1
	inv[1] = 1

	// invは a^(-1) mod p
	// pをaで割ることを考える

	// p/a*(a) + p%a = p
	// p/a*(a) + p%a = 0          (mod p)
	// -p%a = p/a*(a)             (mod p)
	// -p%a *a^(-1)= p/a          (mod p)
	// a^(-1)= p/a * (-p%a)^(-1)  (mod p)
	// a^(-1) =

	for i := 2; i < 1000000; i++ {
		fac[i] = fac[i-1] * i % mod
		inv[i] = mod - inv[mod%i]*(mod/i)%mod
		finv[i] = finv[i-1] * inv[i] % mod
	}
}

func combination(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[y] * finv[x-y] % mod) % mod
	//return fac[x] / (fac[y] * fac[x-y])
}

func permutation(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[x-y] % mod) % mod
	//return fac[x] / fac[x-y]
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}
func pow(x, y int) int { return int(math.Pow(float64(x), float64(y))) }
func abs(x int) int    { return int(math.Abs(float64(x))) }
func floor(x int) int  { return int(math.Floor(float64(x))) }
func ceil(x int) int   { return int(math.Ceil(float64(x))) }

type SortBy []int

func (a SortBy) Len() int           { return len(a) }
func (a SortBy) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool { return a[i] < a[j] }

type PriorityQueue []int

func (h PriorityQueue) Len() int            { return len(h) }
func (h PriorityQueue) Less(i, j int) bool  { return h[i] < h[j] }
func (h PriorityQueue) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *PriorityQueue) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *PriorityQueue) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}


Measured memory_bytes: 640
n = int(input())
x = input()

c1 = x.count('1')
if c1 > 1:
    cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

def f(n):
    ans = 0
    while n > 0:
        ans += 1
        n = n % bin(n).count('1')
    return ans

if c1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
    exit()

for i in range(n):
    if x[i] == '1':
        print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

Measured memory_bytes: 80988
#!/usr/bin/env python3
#ABC72 C

from itertools import accumulate

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

x = [0]*(10**5+3)

for i in a:
    x[i] += 1
    x[i+3] -= 1

x = list(accumulate(x))
print(max(x))


Measured memory_bytes: 57156
#include <bits/stdc++.h>
using namespace std; 
#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll long long int
#define ld long double
#define fi first 
#define se second 
#define mp make_pair
#define pb push_back
#define ull unsigned long long int
#define vll vector<ll>
#define vld vector<ld>
#define pll pair<ll,ll> 
#define pld pair<ld,ld> 
#define vpll vector<pll>
#define vpld vector<pld>
#define all(X) X.begin(),X.end()
#define mo 1000000007
ll gcd(ll a ,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll poww(ll a,ll n){if(n==0)return 1;ll p=poww(a,n/2);p=(p*p)%mo;if(n%2)p=(a*p)%mo;return p;}
////////////////////////////////////////////////////
 int n ; string s;
 ll suf[4003][3]; 
 ll ans;
 void func(char a, char b , int x)
 { //if(a=='G'&&b=='R'&&x==2)
// cout<<ans<<"*"<<endl; 
 	for(int i = 1; i<n-1; i++)
 	{
 		if(s[i]!=b)
 		continue; 
 		for(int j = 0; j<i; j++)
 		{
 			if(s[j]!=a)
 			continue; 
 			int pos = i+(i-j); 
 			ans+=(suf[i+1][x]); 
 			if(pos<n&&s[pos]!=a&&s[pos]!=b)
 			ans--; 
		 }
	 }
	// if(a=='G'&&b=='R'&&x==2)
 //cout<<ans<<"*"<<endl; 
 }
ll tn ; 
void solve()
{
 cin>>n>>s; 
 ll a[3]={0}; 
 for(int i = n-1; i>=0 ; i--)
 {
 	if(s[i]=='R')
 	a[0]++; 
 	else if(s[i]=='G')
 	a[1]++; 
 	else
 	a[2]++; 
 	suf[i][0]=a[0];
 	suf[i][1]=a[1];
 	suf[i][2]=a[2];
 	
 }
 ans = 0; 
 string temp = "RGB"; 
 for(int i = 0; i<3; i++)
 {
 	for(int j = 0; j<3; j++)
 	{
 		for(int k = 0; k<3; k++)
 		{
 			if(i!=j&&i!=k&&j!=k)
 			{
 				func(temp[i],temp[j],k); 
 				//cout<<i<<" "<<j<<" "<<k<<" "<<ans<<endl; 
			 }
		 }
	 }
 }
 
 cout<<ans; 
}
int main()
{ ios; 

ll t ;t = 1; 
  for(tn = 1; tn<=t; tn++)
	solve(); 
	return 0 ; 
}


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

void solve(std::istream &in, std::ostream &out);

int main() {
#ifdef LOCAL
  freopen("../IO/a.in", "r", stdin);
//  freopen("../IO/a.out", "w", stdout);
#else
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
#endif
  solve(std::cin, std::cout);
  return 0;
}

struct event_t {
  int l;
  int type;
  int x;
  event_t() = default;
  event_t(int l, int type, int x) : l(l), type(type), x(x) {}
  bool operator <(const event_t &rhs) const {
    return make_pair(l, type) < make_pair(rhs.l, rhs.type);
  }
};

void solve(std::istream &in, std::ostream &out) {
  int N,Q;
  in >> N >> Q;
  vector<int> ans(Q, -1);
  vector<event_t> events;
  events.reserve(2 * N + Q);
  for (int i = 0, s, t, x; i < N; ++i) {
    in >> s >> t >> x;
    events.emplace_back(s - x, 0, x);
    events.emplace_back(t - x, -1, x);
  }
  for (int i = 0, d; i < Q; ++i) {
    in >> d;
    events.emplace_back(d, 1, i);
  }
  sort(events.begin(), events.end());
  set<int> setik;
  for (const event_t &event : events) {
    int type = event.type;
    if (type == -1) {
      setik.erase(event.x);
    } else if (type == 0) {
      setik.insert(event.x);
    } else {
      if (!setik.empty()) {
        ans[event.x] = *setik.begin();
      }
    }
  }
  for (int a : ans) {
    out << a << '\n';
  }
}

Measured memory_bytes: 20332
#include<bits/stdc++.h>
using namespace std;
main(){
	long long n,m;
	cin>>n>>m;
	vector<pair<int,int> > p(m);
	for(int i=0;i<m;i++){
		cin>>p[i].first>>p[i].second;
	}
	sort(p.begin(),p.end());
	int count = 0;
	priority_queue<int, vector<int>, std::greater<int> > pq;
	for(int i=0;i<m;i++){
		if(pq.size() == 0){
			pq.push(p[i].second);
			count++;
		}else{
			pq.push(p[i].second);
			if(p[i].first < pq.top()){
				continue;
			}else{
			//	cout<<p[i].first<<" "<<p[i].second<<endl;
				pq = priority_queue <int, vector<int>, std::greater<int> >();
				pq.push(p[i].second);
				count++;
			}
		}
	}
	cout<<count<<endl;
}

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

int N,M,C;

struct edge{
  int to,c,s;
  bool operator>(const edge &e) const {
    return c > e.c;
  }
};
vector<edge> G[111];
int H[111][111];

int dijk(){
  fill(H[0],H[N],(1<<29));
  priority_queue<edge,vector<edge>,greater<edge> > q;
  q.push( (edge){0,0,0} );
  while( !q.empty() ){
    edge p = q.top(); q.pop();
    int id = p.to;
    int c = p.c;
    int s = p.s;
    if( H[id][s] < c ) continue;
    for(int i=0;i<(int)G[id].size();i++){
      edge e = G[id][i];
      int nc = c + e.c;
      int ns = s + e.s;
      if( nc > C ) continue;
      if( ns > N ) continue;
      if( H[e.to][ns] > nc ) {
	H[e.to][ns] = nc;
	q.push( (edge){e.to,nc,ns} );
      }
    }
  }
  int ret = (1<<29);
  for(int i=0;i<N;i++){
    if( H[N-1][i] <= C ) ret = min( ret, i );
  }
  return ret;
}

int main(){
  while( cin >> N >> M >> C && (N||M||C) ){
    for(int i=0;i<M;i++){
      int f,t,c;
      cin >> f >> t >> c;
      --f; --t;
      G[f].push_back((edge){t,c,0});
      G[f].push_back((edge){t,0,1});
    }
    cout << dijk() << endl;    
    for(int i=0;i<N;i++) G[i].clear();    
  }
}

Measured memory_bytes: 1436
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}
template<class A,size_t N,class T>void Fill(A(&a)[N],const T&v){fill((T*)a,(T*)(a+N),v);}

const int MOD = 1e9+7; //998244353;

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m=MOD){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m=MOD){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
//V<ll>Fac,Rac;void setF(int n,int m=MOD){Fac=Rac=V<ll>(++n);Fac[0]=1;FOR(i,1,n)Fac[i]=Fac[i-1]*i%m;Rac[n-1]=modInv(Fac[n-1],m);FORR(i,n-1,1)Rac[i-1]=Rac[i]*i%m;}
//ll comb(int a,int b,int m=MOD){return a<b||b<0?0:Fac[a]*Rac[b]%m*Rac[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int N = 2e5;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  cout << s[0] << s[1] << s[2] << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <time.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
#define rep(i,n) for(ll i=0;i<(n);i++)
int main() {
	ll a, b, c;
	cin >> a >> b >> c;
	vector<ll> yojo;
	map<ll, ll>mp;
	for (int i = 0; i < c; i++) {
		if (mp[a + i] == 0 && a + i <= b) {
			yojo.push_back(a + i);
			mp[a + i]++;
		}
		if (mp[b - i] == 0 && b - i >= a) {
			yojo.push_back(b - i);
			mp[b - i]++;
		}
	}
	sort(yojo.begin(), yojo.end());
	for (int i = 0; i < yojo.size(); i++)cout << yojo[i] << endl;
	return 0;
}

Measured memory_bytes: 256
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: i32 = read(&mut stdin_lock, &mut buf, b' ');

    let mut ans = 0;
    for i in 0..n {
        let mut x = i + 1;
        let mut c = 0;
        while x > 0 {
            x /= 10;
            c += 1;
        }
        if c % 2 != 0 {
            ans += 1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
N = int(input())
A = list(map(int, input().split()))

D1 = [0]*(N+1)
D2 = [0]*N

s = 0
last = 0
for i in range(N):
    a = A[i]
    d = abs(last - a)
    D1[i] = d
    s += d
    last = a
D1[N] = abs(last)
s += abs(last)

last = 0
for i in range(N-1):
    D2[i] = abs(last - A[i+1])
    last = A[i]
D2[N-1] = abs(A[N-2])

# print(D1, D2)
for i in range(N):
    ans = s - (D1[i] + D1[i+1]) + D2[i]
    print(ans)


Measured memory_bytes: 15924
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 1e6 + 10;
char s[N];

int main() {
  int n;
  scanf("%d", &n);
  scanf("%s", s);
  vector<int64> sumM(n + 1);
  for (int i = 1; i <= n; ++i) {
    sumM[i] = sumM[i - 1] + (s[i - 1] == 'M');
  }
  vector<int64> sumC(n + 1), cntC(n + 1);
  for (int i = 1; i <= n; ++i) {
    sumC[i] = sumC[i - 1] + (s[i - 1] == 'C' ? sumM[i] : 0);
    cntC[i] = cntC[i - 1] + (s[i - 1] == 'C');
  }
  int m;
  scanf("%d", &m);
  while (m--) {
    int k;
    scanf("%d", &k);
    int64 ret = 0;
    for (int i = 0; i < n; ++i) {
      if (s[i] != 'D') continue;
      int R = min(n, i + k);
      ret += sumC[R] - sumC[i] - (cntC[R] - cntC[i]) * sumM[i];
    }
    printf("%lld\n", ret);
  }
  return 0;
}


Measured memory_bytes: 24704
#include<iostream>

using namespace std;

int main(void) {
int S;
cin >> S;
int h;
int m;
int s;
int modh;

h = S / 3600;
modh = S % 3600;
m = modh / 60;
s = modh % 60;

cout << h << ":" << m << ":" << s << endl;

return 0;
}

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

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

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

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

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

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

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

//main code

LL gcd(LL a,LL b) {
	LL bigger = max(a,b);
	LL smaller = min(a,b);
	if (bigger % smaller != 0) {
		return gcd(smaller,(bigger % smaller));
	}
	return smaller;
}

int main(int argc, char const* argv[])
{
	LL n,m;
	cin >> n >> m;
	string s,t;
	cin >> s >> t;
	LL d = gcd(n,m);
	LL mul = (n*m)/d;
	LL s_index = 0, t_index = 0;
	for (int i = 0; i < d; i++) {
		if (s[s_index] != t[t_index]) {
			cout << -1 << endl;
			return 0;
		}
		s_index += n/d;
		t_index += m/d;
	}
	cout << mul << endl;
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using llong = long long;

int main(void) {
	int n; cin >> n;
	vector<llong> A(n), B(n), C(n);
	for (int i = 0; i < n; i++) scanf("%lld", &A[i]);
	for (int i = 0; i < n; i++) scanf("%lld", &B[i]);
	for (int i = 0; i < n; i++) scanf("%lld", &C[i]);

	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	sort(C.begin(), C.end());

	llong res = 0;
	llong low, up;
	for (int j = 0; j < n; j++) {
		low = lower_bound(A.begin(), A.end(), B[j]) - A.begin();
		up = (C.end() - upper_bound(C.begin(), C.end(), B[j]));
		res += (up * low);
	}

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 2560