akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <type_traits>
using namespace std;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(),x.end()
auto& errStream=cerr;
#ifdef LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

ll read(){
	ll i;
	scanf("%"  SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

signed main(){
	int n=read();
	bool win=false;
	REP(_,n){
		int x=read();
		if(x%2==1)
			win=true;
	}
	if(win)
		cout<<"first"<<endl;
	else
		cout<<"second"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
  string S, A, B;
  long K, coa = 0, cob = 0;
  cin >> S >> K;
  A = S;
  for(int i = 0; i < A.size() - 1; i++){
    if(A.at(i) == A.at(i + 1)){
      A.at(i + 1) = '0';
      coa++;
    }
  }
  if(A.at(0) != A.at(A.size() - 1))cout << coa * K << endl;
  else {
    B = S;
    B.at(0) = '0';
    cob++;
    for(int i = 1; i < B.size() - 1; i++){
      if(B.at(i) == B.at(i + 1)){
        B.at(i + 1) = '0';
        cob++;
      }
    }
    if(A.at(0) == B.at(B.size() - 1))cout << coa + (K - 1) * cob;
    else {
      if(K % 2 == 1)cout << coa * (K / 2 + 1) + cob * (K / 2);
      else cout << (coa * K + cob * K) / 2;
    }
  }
  return 0;
}

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

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

typedef long long ll;

const char nl = '\n' ;
const ll MOD = 1e9 + 7;


int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   string s, t; cin >> s >> t;
   sort(all(s));
   sort(all(t));
   reverse(all(t));
   if(s.compare(t) < 0)
      cout << "Yes" << nl;
   else
      cout << "No" << nl;
   return 0;
}


Measured memory_bytes: 3624
def solve(c):
    w, h = len(c[0]), len(c)
    dp = [[0] * w for _ in range(h)]
    
    #?????????
    for x in range(w):
        if c[1][x] == 0:
            dp[1][x] = 1
    
    for y in range(2, h):
        for x in range(w):
            if c[y][x] == 1:
                continue
            if c[y - 2][x] == 2:
                dp[y][x] += dp[y - 2][x]
            if c[y - 1][x] == 0:
                dp[y][x] += dp[y - 1][x]
                
            if c[y][x] == 0:
                if c[y - 1][x - 1] == 0:
                    dp[y][x] += dp[y - 1][x - 1]
                if c[y - 1][x + 1] == 0:
                    dp[y][x] += dp[y - 1][x + 1]

    return sum(dp[-1]) + sum(dp[-2][x] for x in range(w) if c[-2][x] == 2)

import sys
f = sys.stdin

while True:
    w, h = map(int, f.readline().split())
    if w == 0:
        break
    course = [[1] * (w + 2)] + [[1] + list(map(int, f.readline().split())) + [1] for _ in range(h)]
    print(solve(course))

Measured memory_bytes: 6772
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<limits>
#include<deque>
#include<map>
#include<list>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>
#include<cstdio>
#include<memory>
#include<bitset>
#include<stack>
#include<functional>
#include<queue>
#include<regex>
#include<time.h>
#include<type_traits>

using namespace std;
using ll = long long;

constexpr ll MOD = 1000000007;
constexpr ll INF = 1050000000;
constexpr ll LONGINF = 1050000000000000000;


int main() {

	int h, w; cin >> h >> w;

	vector<vector<int>> c(10, vector<int>(10, 0));

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> c[i][j];
		}
	}

	for (int x = 0; x < 3; x++) {
		for (int i = 0; i < 10; i++) {//なんとかフロイド法だっけ？
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 10; k++) {
					if (c[k][i] > c[k][j] + c[j][i]) {
						c[k][i] = c[k][j] + c[j][i];
					}
				}
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			int x; cin >> x;
			if (x == -1) {

			}
			else {
				ans += c[x][1];
			}
		}
	}

	cout << ans << endl;



	return 0;
}

Measured memory_bytes: 256
M = 10 ** 9 + 7

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

# negative
def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

invs = [None]
for i in range(1, max(a, b) + 1):
	invs.append(calc_inverse(i, M))

def c(a, b):
	n = 1
	
	for i in range(a - b + 1, a + 1):
		n = (n * i) % M
	
	for i in range(1, b + 1):
		n = (n * invs[i]) % M
	
	return n

print((pow(2, n, M) - c(n, a) - c(n, b) - 1) % M)



Measured memory_bytes: 11060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<ll,ll>
#define poly vector<ll>
#define mem(a) memset((a),0,sizeof(a))
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x.size()))
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
ll rnd(){
	ull ans=0;
	For(i,0,4)ans=ans<<15^rand();
	return ans%((ull)1<<63);
}
int main(){
	#ifdef Brollan
		freopen("1.in","r",stdin);
	#endif
	int x=read(),sum=0;
	For(i,1,1000000){
		sum+=x;
		if(i>=3&&sum%360==0){
			cout<<i<<endl; return 0;
		}
	}
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll d[4];

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

  rep(i,3){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    d[a]++; d[b]++;
  }
  bool ok=true;
  rep(i,4)if(d[i]==3)ok=false;
  if(ok)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;

  return 0;
}


Measured memory_bytes: 256
using System;

class Program
{
    static void Main()
    {
        var l = Console.ReadLine();
        for (int i = 0; i < 8; i++)
        {
            if (Calc(i, l))
            {
                Console.Write(l[0]);
                int cp = i;
                for (int j = 1; j <= 3; j++)
                {
                    if (cp % 2 == 0)
                    {
                        Console.Write('+');
                    }
                    else
                    {
                        Console.Write('-');
                    }
                    cp /= 2;
                    Console.Write(l[j]);
                }
                Console.Write("=7");
                Console.WriteLine();
                return;
            }
        }
    }

    static bool Calc(int n, string input)
    {
        int r = (input[0] - '0');
        for (int i = 1; i <= 3; i++)
        {
            if (n % 2 == 0)
            {
                r += input[i] - '0';
            }
            else
            {
                r -= input[i] - '0';
            }
            n /= 2;
        }
        return r == 7;
    }
}

Measured memory_bytes: 13140
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef __int128_t lll;
ll MOD;
ll powmod(ll a, lll k){
    ll ap=a, ans=1;
    while(k){
        if(k&1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k>>=1;
    }
    return ans;
}
vector<vector<ll>> matrixmul(int l, int m, int n, vector<vector<ll>> a, vector<vector<ll>> b){
	vector<vector<ll>> c;
	for(int i=0; i<l; i++){
		vector<ll> v;
		for(int j=0; j<n; j++){
			ll x=0;
			for(int k=0; k<m; k++){
				x+=(a[i][k]*b[k][j]);
				x%=MOD;
			}
			v.push_back(x);
		}
		c.push_back(v);
	}
	return c;
}
vector<vector<ll>> matrixpow(int n, vector<vector<ll>> a, ll k){
	vector<vector<ll>> ap=a, ans;
	for(int i=0; i<n; i++){
		vector<ll> v;
		for(int j=0; j<n; j++){
			if(i==j){
				v.push_back(1);
			}else{
				v.push_back(0);
			}
		}
		ans.push_back(v);
	}
	while(k){
		if(k&1) ans=matrixmul(n, n, n, ap, ans);
		ap=matrixmul(n, n, n, ap, ap);
		k>>=1;
	}
	return ans;
}
int main()
{
    ll l, a, b; cin>>l>>a>>b>>MOD;
    ll p=1;
    ll cnt[20]={};
    ll s[20]={};
    for(int i=0; i<18; i++){
        ll x=(p-a+b-1)/b, y=(10*p-a+b-1)/b;
        if(x>=l || 10*p-a<=0){
          p*=10; continue;
        }
        y=min(y, l);
      x=max(0ll, x);
      if(x==y){
          p*=10; continue;
      }
        cnt[i]=y-x;
        vector<vector<ll>> mat;
        vector<ll> v[3];
      v[0].resize(3);
        v[0][0]=10*p%MOD, v[0][1]=1, v[0][2]=b%MOD;
        mat.push_back(v[0]);
      v[1].resize(3);
        v[1][0]=0, v[1][1]=1, v[1][2]=b%MOD;
        mat.push_back(v[1]);
      v[2].resize(3);
        v[2][1]=0, v[2][2]=1, v[2][0]=0;
        mat.push_back(v[2]);
        vector<vector<ll>> mp=matrixpow(3, mat, y-x-1);
      ll a1=a+x*b;
        s[i]=(mp[0][0]*(a1%MOD)+mp[0][1]*(a1%MOD)+mp[0][2])%MOD;
        p*=10;
    }
  //for(int i=0; i<18; i++) cout<<cnt[i]<<endl;
  //cout<<cnt[0]<<" "<<cnt[1]<<" "<<s[0]<<" "<<s[1]<<endl;
    ll ans=0;
    lll c=0;
    for(int i=17; i>=0; i--){
        ans+=s[i]*powmod(10, c)%MOD;
        c+=(lll)cnt[i]*(lll)(i+1);
        ans%=MOD;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
local mod=1000000007

local function bmul(x,y)
    return (x*y)%mod
end

local function badd(x,y)
    return (x+y)%mod
end

local function bsub(x,y)
  return x<y and x-y+mod or x-y
end

local function bmod(x)
    x=tostring(x)
    local ten=10
    local cry=1
    local xod=0
    for i=#x,1,-1 do
        local xub=tonumber(x:sub(i,i))
        xod=badd(xod,bmul(xub,cry))
        cry=bmul(cry,ten)
    end
    return xod
end

local function bpow(x,y)
    x=bmod(x)
    y=bmod(y)
    local xpy=1
    while 0<y do
        if y%2==1 then
            xpy=bmul(xpy,x)
            y=y-1
        end
        x=bmul(x,x)
        y=y//2
    end
    return xpy
end

local function comb(x,y)
    local xyi=1
    local yii=1
    for i=1,y do
        xyi=bmul(xyi,x+1-i)
        yii=bmul(yii,i)
    end
    return bmul(xyi,bpow(yii,mod-2))
end

local n,k=io.read("n","n")
for i=1,k do
    print(comb(n-k+1,i)*comb(k-1,i-1)%mod)
end

Measured memory_bytes: 2820
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	int cnt=0,num=0,n;
	string s;
	cin>>n>>s;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='D')
		num--;
		else
		num++;
		cnt=max(cnt,num);
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 256
// Hint: Don't look, No need, Let'em Play.

#pragma optimize("O2")
#include <bits/stdc++.h>
#include "bits/stdc++.h"

using namespace std;

#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#ifndef bhupixb
    #define var(...)
    #define stl(...)
#endif

void solve() {
    int n, k;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < k;++i) {
        ans += a[i];
    }
    cout << ans << '\n';
}

signed main() {
    fast;
    int t = 1; // cin >> t;
    while (t--) {
        solve();
    }


  return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
using namespace std;



int main(){
  int N;
  cin >> N;
  
  int hmax;
  cin >> hmax;
  for(int x=1; x < N; x++)
  {
    int h;
    cin >> h;
    if(hmax < h)
    {
      hmax = h;
    }
    else if(hmax - 1 > h)
    {
      cout << "No" << endl;
      return 0;
    }
  }

    cout << "Yes" << endl; 
  return 0;
}

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


def all_even(A):
    for a in A:
        if a % 2 != 0:
            return False
    return True


count = 0
while all_even(A):
    A = [i // 2 for i in A]
    count += 1

print(count)


Measured memory_bytes: 2940
from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [0]*N
sAB = [0]*N
rlt = 0

A.sort()
B.sort()
C.sort()

for i in range(N):
  AB[i] = bisect_left(A, B[i])

sAB[0] = AB[0]
for i in range(N-1):
  sAB[i+1] = sAB[i] + AB[i+1]

for i in range(N):
  j = bisect_left(B, C[i])
  if j == 0:
    continue
  else:
    rlt += sAB[j-1]
  
print(rlt)

Measured memory_bytes: 106340
import sys
input = sys.stdin.readline

def main():
  N,K = map(int,input().split())
  A = sorted(list(map(int,input().split())))
  
  AM = []
  AP = []
  for a in A:
    if a > 0:
      AP.append(a)
    elif a < 0:
      AM.append(a)

  INF = 10**18+1
  l = -INF
  r = INF
  while(l+1 < r):
    # 積がc未満となるペアの個数xを求める。
    # K番目の積は、それより小さい積の個数がK未満である席のうち最大のもの。
    c = (l+r)//2
    x = 0
    if c > 0:
      i = len(AP)-1
      for j in range(len(AP)):
        if j >= i:
          break
        while(j < i and AP[i]*AP[j] >= c):
          i -= 1
        x += i-j
      i = 0
      for j in range(len(AM)-1,-1,-1):
        if j <= i:
          break
        while (i < j and AM[i]*AM[j] >= c):
          i += 1
        x += j-i
      #print(c,x)
      x += len(AP)*len(AM)
      x += (len(AP)+len(AM))*(N-len(AP)-len(AM))
      if N-len(AP)-len(AM) > 1:
        x += (N-len(AP)-len(AM))*(N-len(AP)-len(AM)-1)//2
    elif c == 0:
      x += len(AP)*len(AM)
    else:
      i = 0
      for j in range(len(AM)):
        while(i < len(AP) and AP[i]*AM[j] >= c):
          i += 1
        x += len(AP)-i

    #print(l,r,c,x)
    if x < K:
      l = c
    else:
      r = c
  print(l)

if __name__ == '__main__':
  main()


Measured memory_bytes: 89172
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
int inf = 1e9 + 7;

vector<int> g[maxn];
int ans[maxn], ar[maxn], n;
int lis[maxn];

void dfs(int u, int p = -1)
{
    //cout << "u = " << u << '\n';
    int k = lower_bound(lis, lis + n, ar[u]) - lis;
    int pre_val = lis[k];
    lis[k] = ar[u];
    //for(int i = 0; i < 5; i ++)cout << lis[i] << ' '; cout << '\n';
    ans[u] = lower_bound(lis, lis + n, inf) - lis;
    for(int v : g[u]){
        if(v != p)dfs(v, u);
    }
    lis[k] = pre_val;
}

int main() 
{
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> ar[i];
    }
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    memset(lis, 0x3f, sizeof(lis));
    inf = lis[0];
    dfs(1, -1);
    for(int i = 1; i <= n; i++)cout << ans[i] << '\n';
    return 0;
}


Measured memory_bytes: 31280
# coding:utf-8
import sys

# 最大公約数
def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

# 最小公倍数
def lcm(a, b):
  return a*b/gcd(a, b)

for s in sys.stdin:
  a, b = map(int,s.split())
  gcd_num = gcd(a, b)
  lcm_num = lcm(a, b)
  print "%d %d"%(gcd_num, lcm_num)




Measured memory_bytes: 4644
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

//typedef pair<int,int> P;



int main(){
	int N;
	long long A[200000];
	long long B[200000];

	scanf("%d", &N);
	for(int i=0;i<N;i++){
		scanf("%lld", &A[i]);
	}
	for(int i=0;i<N;i++){
		scanf("%lld", &B[i]);
	}

	long long num[30];

	for(int k=29;k>=0;k--){
		num[k] = 0;
		long long T = (1<<k);
		long long a[200000];
		long long b[200000];
		for(int i=0;i<N;i++){
			a[i] = A[i]%(2*T);
			b[i] = B[i]%(2*T);
		}
		sort(b,b+N);
		for(int i=0;i<N;i++){
			num[k] += lower_bound(b, b+N, 2*T-a[i]) - lower_bound(b, b+N, T-a[i]);
			num[k] += lower_bound(b, b+N, 4*T-a[i]) - lower_bound(b, b+N, 3*T-a[i]);
		}
	}

	for(int i=0;i<30;i++){
		//printf("%d ", num[i]);
	}

	long long ans = 0;
	for(int i=0;i<30;i++){
		if(num[i]%2==1) ans += (1<<i);
	}

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

	return 0;
}


Measured memory_bytes: 6400
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#define PAIR pair<long long,int>
using namespace std;

class island{
public:
    vector<PAIR> road;
    void add(int goal,int much){
        road.push_back(PAIR(much,goal));
    }
};
long long func(vector<island>&,int,int);
int main(){
    int n,m;
    while(cin>>n>>m&&n){
        vector<island> map(n+1);
        for(int i=0;i<m;++i){
            int type;
            cin>>type;
            if(type==1) {
                int a,b,much;
                cin>>a>>b>>much;
                map[a].add(b,much);
                map[b].add(a,much);
            }else{
                int s,g;
                cin>>s>>g;
                cout<<func(map,s,g)<<endl;
            }
        }
    }
    return 0;
}

long long func(vector<island>& map,int s,int g){
    vector<long long> much(map.size()+1,-1);
    priority_queue<PAIR,vector<PAIR>,greater<PAIR> > que;
    que.push(PAIR(0,s));
    much[s]=0;
    while(!que.empty()){
        PAIR dpair = que.top();
        que.pop();
        long long time = dpair.first;
        int np = dpair.second;
        if(much[np]!=time){
            continue;
        }
        for(vector<PAIR>::iterator itr = map[np].road.begin();itr!=map[np].road.end();++itr){
            long long ntime = time + itr->first;
            int ng = itr->second;
            if(much[ng]==-1||much[ng]>ntime){
                much[ng]=ntime;
                que.push(PAIR(ntime,ng));
            }
        }
    }
    return much[g];
}


Measured memory_bytes: 3176
#include <stdio.h>

int main()
{
    int input1, input2;

    // 入力
    scanf("%d %d", &input1, &input2);

    // 約数かチェック
    if( (input2%input1) == 0 ) {
        // 割り切れるので約数
        printf("%d\n", (input1+input2));
    }
    else {
        // 割り切れないので約数ではない
        printf("%d\n", (input2-input1));
    }

    return 0;
}


Measured memory_bytes: 128
# -*- coding: utf-8 -*-
N,M = map(int, input().split())
G = [[] for j in range(N)]
#グラフの読み込み
for i in range(M):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
visited = [False]*N
visited[0] = True
#再帰
def DFS(v,visited):
    #もし全てTrueなら1を返す
    if all(visited):
        return 1
    ans = 0
    for i in G[v]:
        if visited[i]:
            continue
        visited[i] = True
        ans += DFS(i,visited)
        visited[i] = False
    return ans

print(DFS(0,visited))


Measured memory_bytes: 9120
#include <stdio.h>
#include <stdlib.h>
void CountingSort(int *,int *,int);
int C[10001]={0},i;
int main(void){
  int n,*A,*B;
  scanf("%d",&n);
  A=(int *)malloc(sizeof(int)*n);
  B=(int *)malloc(sizeof(int)*n);
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);
  
  CountingSort(A,B,n);
  for(i=0;i<n;i++){
    printf("%d",B[i]);
    if(i!=n-1)printf(" ");
  }
  printf("\n");
  return 0;
}
void CountingSort(int *A,int *B,int k){
  /*C[i]にiの出現数を記録する */
  i=0;
  while(i<k){
    C[A[i++]]++;
  }

  /*C[i]にi以下の数の出現数を記録する*/
  i=0;
  while(i<10001){
    C[i]=C[i]+C[i-1];
    i++;
  }

  for(i=k-1;i>=0;i--){
    B[C[A[i]]-1]=A[i];
    C[A[i]]--;
  }
}


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

int main() {
    string s, t;
    cin >> s >> t;

    int r = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] != t[i]) r++;
    }

    cout << r << endl;

    return 0;
}


Measured memory_bytes: 3920
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		if(S.equals("AAA") || S.equals("BBB")) {
			System.out.println("No");
		}else {
			System.out.println("Yes");
		}
	}
}

Measured memory_bytes: 22228
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let v = read_vec::<i64>();
    let ave_nx = v.iter().sum::<i64>();
    let mut min_diff = std::i64::MAX;
    let mut min_index = 0;
    for i in 0..n {
        let diff = (v[i] * n as i64 - ave_nx).abs();
        if diff < min_diff {
            min_diff = diff;
            min_index = i;
        }
    }
    println!("{}", min_index);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
using System;
using System.Collections.Generic;
using System.Linq;


namespace _527_SettingGoStones
{
	class Program
	{
		static void Main ( string[] args )
		{
			while (true)
			{
				//input
				int stoneAllCount = int.Parse (Console.ReadLine ());

				if (stoneAllCount == 0)
				{
					break;
				}

				int[] stoneState = new int[stoneAllCount];

				for (int lp = 0; lp < stoneAllCount; lp++)
				{
					stoneState[lp] = int.Parse (Console.ReadLine ());
				}

				//process

				List<Stones> list = new List<Stones> (stoneState.Length);

				for (int lp = 0; lp < stoneState.Length; lp++)
				{
					bool isOdd = (lp + 1) % 2 == 1;

					//?\???°?????´???
					if (isOdd)
					{
						//??????????????????
						list = Stones.Put (list, new Stones (stoneState[lp], 1));
					}
					//??¶??°?????´???
					else
					{
						int rightIndex = list.Count - 1;
						int sideColor = list[rightIndex].Color;

						//????????¨??????????????´???
						if (stoneState[lp] == sideColor)
						{
							//??????????????????
							list = Stones.Put (list, new Stones (stoneState[lp], 1));
						}
						//????????´???
						else
						{
							//???????????????????????????????????????????????§?????????????????????????????????????????????
							int mixIndex = list.Count - 1;

							list[mixIndex].Convert ();
							list[mixIndex].AddCount (1);

							//??±???
							//??????????´????????????°
							if (0 < mixIndex)
							{
								list[mixIndex - 1].AddCount (list[mixIndex].Count);
								list.RemoveAt (mixIndex);
							}
						}
					}
				}

				//output
				int whiteCount = list.Where (item => item.Color == Stones.White).Sum (item => item.Count);

				Console.WriteLine (whiteCount);
			}
		}
	}
}

class Stones
{
	public Stones ( int color, int count )
	{
		this.Color = color;
		this.Count = count;
	}

	public int Color { set; get; }
	public int Count { set; get; }
	public static int White = 0;
	public static int Black = 1;

	public void Convert ()
	{
		if (Color == White)
			Color = Black;
		else
			Color = White;
	}

	public void AddCount ( int count )
	{
		Count += count;
	}

	public static List<Stones> Put ( List<Stones> list, Stones item )
	{
		if (0 < list.Count)
		{
			int rightIndex = list.Count - 1;
			int sideColor = list[rightIndex].Color;

			//???????????????????¢??????????????????????????????°??±???
			if (item.Color == sideColor)
			{
				list[rightIndex].AddCount (item.Count);
			}
			//????????´????????°?????????????????????????????\??????
			else
			{
				list.Add (item);
			}
		}
		else
		{
			list.Add (item);
		}

		return list;
	}
}

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

using namespace std;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

struct LowLink
{
  UnionFind uf;
  vector< vector< int > > g;
  vector< int > used, ord, low, parent;

  LowLink(size_t v) : g(v), used(v, 0), ord(v), low(v), uf(v), parent(v, -1) {}

  virtual void add_edge(int x, int y)
  {
    g[x].push_back(y);
    g[y].push_back(x);
  }

  void dfs(int idx, int &k, int par = -1)
  {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];

    for(auto &to : g[idx]) {
      if(!used[to]) {
        dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        parent[to] = idx;
        if(ord[idx] >= low[to]) uf.unite(idx, to);
      } else if(to != par) {
        low[idx] = min(low[idx], ord[to]);
      }
    }
  }

  void dfs()
  {
    int k = 0;
    dfs(0, k);
  }
};

struct ArticulationPoints : LowLink
{
  ArticulationPoints(size_t v) : LowLink(v) {}

  vector< int > build()
  {
    LowLink::dfs();
    vector< int > vs;
    int sum = 0;
    for(int i = g.size() - 1; i >= 1; i--) {
      if(parent[i] == 0) ++sum;
      else if(ord[parent[i]] <= low[i]) vs.push_back(parent[i]);
    }
    if(sum > 1)vs.push_back(0);
    sort(begin(vs), end(vs));
    vs.erase(unique(begin(vs), end(vs)), end(vs));
    return (vs);
  }
};

struct BiConnectedComponents : LowLink
{
  vector< pair< int, int > > edges;
  vector< int > comp;

  BiConnectedComponents(size_t v) : LowLink(v), comp(v) {}

  void add_edge(int x, int y)
  {
    LowLink::add_edge(x, y);
    edges.push_back(minmax(x, y));
  }

  int operator[](int k)
  {
    return (comp[k]);
  }

  void build(vector< vector< int > > &t)
  {
    LowLink::dfs();
    int ptr = 0;
    vector< int > cc(g.size());
    for(int i = 0; i < g.size(); i++) {
      if(i == uf.find(i)) cc[i] = ptr++;
    }

    t.resize(ptr);
    for(int i = 0; i < g.size(); i++) {
      comp[i] = cc[uf.find(i)];
    }
    for(auto &e : edges) {
      int x = comp[e.first], y = comp[e.second];
      if(x == y) continue;
      t[x].push_back(y);
      t[y].push_back(x);
    }
  }
};


void solve()
{
  int V, E;
  cin >> V >> E;
  ArticulationPoints graph(V);
  vector< vector< int > > latte(V), malta(V);
  for(int i = 0; i < E; i++) {
    int s, t;
    cin >> s >> t;
    graph.add_edge(s, t);
    latte[s].emplace_back(t);
    latte[t].emplace_back(s);
  }
  for(int i : graph.build()) cout << i << endl;
}

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

Measured memory_bytes: 6316
using System;

namespace ConsoleApp8
{
    class Program
    {
        static void Main(string[] args)
        {
            string a = Console.ReadLine();
            int n = int.Parse(a);
            string b = Console.ReadLine();
            string[] vs = b.Split(' ');
            long[] c = new long[n];
            for (int i = 0; i < n; i++)
            {
                c[i]= int.Parse(vs[i]);
            }
            int cnt = 0;
            for (int i = 0; i < n - 2; i++)
            {
                for (int j = i + 1; j < n-1; j++)
                {
                    for (int k = j + 1; k < n; k++)
                    {
                        if (c[i] != c[j] && c[i] != c[k] && c[j] != c[k])
                        {
                            double d = (double)(c[i] + c[j] + c[k])/2;
                            if (c[i] < d && c[j] < d && c[k] < d)
                            {
                                cnt++;        
                            }
                        }

                    }
                }
            }
            Console.WriteLine(cnt);
            //Console.ReadLine();
        }
    }
}


Measured memory_bytes: 27376
N,P = map(int, input().split())
A = list(map(lambda x:int(x)%2, input().split()))
A0 = A.count(0)
A1 = A.count(1)
if P == 1:
    if A1 == 0:
        print(0)
    else:
        print(2**(A1-1)*2**A0)
else:
    if A1 == 0:
        print(2**A0)
    else:
        print(int(2**(A1-1)*2**A0))


Measured memory_bytes: 3060
n, m, l = map(int, input().split())
a = []
b = []

for i in range(n):
    a.append(list(map(int, input().split())))
for j in range(m):
    b.append(list(map(int, input().split())))

for i in range(n):
    li = []
    for j in range(l):
        su = 0
        for k in range(m):
            su += a[i][k] * b[k][j]
        li.append(su)
    print(" ".join(list(map(str, li))))



Measured memory_bytes: 6244
n = int(input())
a = list(map(int,input().split()))

cnt = 0
while a:
    for i in range(len(a)):
        if a[0] == 0:
            a.pop(0)
            break
        else:
            a[i] -= 1
            if i != len(a)-1:
                if a[i+1] == 0:
                    cnt += 1
                    break
            if i == len(a)-1:
                cnt += 1

print(cnt)

Measured memory_bytes: 3064
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)]
dpsum = [[0] * (m + 1) for _ in range(n + 1)]
mod = pow(10, 9) + 7
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s[i - 1] == t[j - 1]:
            dp[i][j] = 1
            if not i == 1 and not j == 1:
                dp[i][j] += dpsum[i - 1][j - 1]
                dp[i][j] %= mod
        dpsum[i][j] = dpsum[i - 1][j] + dpsum[i][j - 1] - dpsum[i - 1][j - 1] + dp[i][j]
        dpsum[i][j] %= mod
ans = dpsum[n][m] + 1
print(ans)

Measured memory_bytes: 134452
import bisect
s = input()
l = len(s)
ch = [[] for _ in range(26)]
s *= 2
for i in range(l*2):
  ch[ord(s[i]) - ord("a")].append(i)
  
t = input()
ans = 0
now = -1
for i in t:
  idx = ord(i) - ord("a")
  if not ch[idx]:
    print(-1)
    break
  temp = bisect.bisect_right(ch[idx], now)
  ans += ch[idx][temp] - now
  now = ch[idx][temp]%l
else:
  print(ans)

Measured memory_bytes: 12020
open System
let R T = stdin.ReadLine()|> T
let RS T = stdin.ReadLine().Split()|>Array.map T
let Mod = (1e9|>int64)+7L
[<EntryPoint>]
let main argv =
    let N = R int
    let S,T = RS string|>fun c -> c.[0],c.[1]
    for i in [0..N-1] do
        stdout.Write S.[i]
        stdout.Write T.[i]
    stdout.WriteLine ""
    0


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)

#define Rep(j,n) for(int j=0;j<(int)(n);++j)

#define int long long

using namespace std;

signed main()
{
  int x=0,y=0;
  cin >> x;
int vv[x];
rep(i,x){
  vv[i]=0;
cin >> vv[i];
}
sort(vv,vv+x);
rep(i,x-1){
  y+=vv[i];
}
if(y>vv[x-1]){
  cout << "Yes" << '\n';
}else{
  std::cout << "No" << '\n';
}
}



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

const int N = 1e5 + 5;
int sz[N];
vector<int> g[N];

ll dfs(int node, int h) {
	ll ans = h;
	for (int to : g[node]) {
		ans += dfs(to, h + 1);
	}
	return ans;
}

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

    int n;
    cin >> n;

    map<ll, int> mp;

    for (int i = 0; i < n; i++) {
    	ll d;
    	cin >> d;
    	mp[d] = i;
    	sz[i] = 1;
    }

    while (!mp.empty()) {
    	ll x = mp.rbegin()->first;
    	int y = mp.rbegin()->second;

    	// cout << x + 2 * sz[y] - n << " " << y << "\n";

    	if (mp.size() == 1) {
    		break;
    	}

    	if (x + 2 * sz[y] - n >= x) {
    		cout << "-1";
    		return 0;
    	}

    	if (!mp.count(x + 2 * sz[y] - n)) {
    		cout << "-1";
    		return 0;
    	}

    	int z = mp[x + 2 * sz[y] - n];

    	sz[z] += sz[y];
    	g[z].push_back(y);

    	mp.erase(prev(mp.end()));
    }

    int rt = mp.begin()->second;

    if (dfs(rt, 0) != mp.begin()->first) {
    	cout << "-1";
    	return 0;
    }

    for (int i = 0; i < n; i++) {
    	for (int to : g[i]) {
    		cout << i + 1 << " " << to + 1 << "\n";
    	}
    }

    return 0;   
}

Measured memory_bytes: 12800
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x != None: x, y = x.left if key < x.key else x.right, x
    if y == None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    return result == None

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    elif e[0] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))


Measured memory_bytes: 55692
#include<iostream>
using namespace std;
int n, m, a, b;
int main() {
	while (true) {
		cin >> n >> m >> a >> b; if (n == 0)break;
		long double V = 1.0l*n / m;
		if (V >= 1.0l*a) cout << "0" << endl;
		else cout << ((m*a - n) + b - 1) / b << endl;
	}
}

Measured memory_bytes: 3068
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N;
    cin >> N;
    int h[N];
    int i;
    int max =0;
    int count = 0;
    for(i=0;i<N;i++)
    {
        cin >> h[i] ;
        if(h[i] >= max)
        {
            max = h[i];
            count ++;
        }
    }
    cout << count << endl;
    return 0;
    
}

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

using namespace std;

int main(){
  long long n, k; cin >> n >> k;
  vector<long long> num(100000);
  for(long long i=0;i<n;i++){
    long long a, b; cin >> a >> b;
    num[a] += b;
  }
  long long cnt=0;
  for(long long i=0;i<=num.size();i++){
    cnt += num[i];
    if(cnt>=k){
      cout << i << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i ++)
#define rep1(i, n) for (int i=1; i <= n; i ++)
#define _min(x, y) x = min(x, y)
#define _max(x, y) x = max(x, y)
using namespace std;



const int mod = 1000000007;

struct mint {
  long long x;
  mint(long long 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) {
     (x /= a.x) %= mod;
     return *this;
  }
  mint operator+(const mint a) {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) {
    mint res(*this);
    return res *= a;
  }
  mint operator/(const mint a) {
    mint res(*this);
    return res /= a;
  }
};



mint C[5000][5000];
void init() {
  C[0][0] = 1;
  rep(i, 4005) {
    rep(j, 4005) {
      C[i + 1][j] += C[i][j];
      C[i + 1][j + 1] += C[i][j];
    }
  }
}


mint comb(int n, int k) {
  return C[n][k];
}

mint f2(int n, int k) {
  return comb(n + k - 1, k - 1);
}

mint f(int n, int k) {
  if (n == 0 && k == 0) return 1;
  if (n < k || k < 1) return 0;
  return f2(n - k, k);
}




int main() {
  int n, k;
  int red, blue;
  cin >> n >> k;
  init();
  // rep(i, 5) {
  // rep(j, 5) {
  //   cout << C[i][j] << " ";
  // }
  // cout << endl;

  // }

  blue = k;
  red = n - k;

  // printf("red: %d, blue: %d\n", red, blue);
  rep1(i, k) {
    mint blue_pattern = f(blue, i);
    mint red_pattern = f2(red - (i - 1), i + 1);
    // cout << "red: " << red_pattern << "blue: " << blue_pattern << endl;
    mint ans = red_pattern * blue_pattern;
    cout << ans.x << endl;
  }
  return 0;
}


Measured memory_bytes: 195584
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
  int n,cou=0;
  cin>>n;
  const int N=n;
  int a[N];
  for(int i=0;i<N;i++){
    cin>>a[i];
    int s=a[i];
    while(s%2==0){
    cou++;
    s=s/2;
    }
  }
  cout<<cou<<endl;
  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
 
S = list(input())
Q = int(input())
is_forward = True
lia = []
lib = []
 
for i in range(Q):
    query = input()
 
    if query == '1':
        is_forward = not is_forward
    else:
        T, F, C = query.split()
        if is_forward:
            if F == '1':
                lia.append(C)
            else:
                lib.append(C)
        else:
            if F == '1':
                lib.append(C)
            else:
                lia.append(C)

if is_forward:
  lia.reverse()
  print(''.join(lia + S + lib))
else:
  S.reverse()
  lib.reverse()
  print(''.join(lib + S + lia))


Measured memory_bytes: 79096
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		char[] input = a.toCharArray();
		char[] output = new char[input.length];
		sc.close();
		int counter = 0;
		for (int i = 0; i < input.length; i++) {
			if (input[i] == '0') {
				output[counter] = '0';
				counter++;
			}
			else if (input[i] == '1') {
				output[counter] = '1';
				counter++;
			}
			else if (input[i] == 'B') {
				if (counter > 0) {
					counter--;
				}
			}
			else {
				
			}
		}
		String x = new String(output);
		System.out.println(x.substring(0, counter));
	}
}


Measured memory_bytes: 9424
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>

#define LP(i,n) for(int i=0;i<n;i++)
#define Mset(x,v) memset(x,v,sizeof(x))

using namespace std;
using LL=long long;

static const int MAX=10000;
static const int INFTY=(1<<21);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int n;
vector<pair<int,int> > adj[MAX];

void dijkstra(){
    priority_queue<pair<int,int> > PQ;
    int color[MAX];
    int d[MAX];
    for(int i=0;i<n;i++){
        d[i]=INFTY;
        color[i]=WHITE;
    }
    d[0]=0;
    PQ.push(make_pair(0,0));
    color[0]=GRAY;
    while(!PQ.empty()){
        pair<int,int> f=PQ.top();PQ.pop();
        int u=f.second;
        color[u]=BLACK;
        if(d[u]<f.first*(-1)) continue;
        for(int j=0;j<adj[u].size();j++){
            int v=adj[u][j].first;
            if(color[v]==BLACK) continue;
            if(d[v]>d[u]+adj[u][j].second){
                d[v]=d[u]+adj[u][j].second;
                PQ.push(make_pair(d[v]*(-1),v));
                color[v]=GRAY;
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<i<<" "<<(d[i]==INFTY?-1:d[i])<<endl;
    }
}

int main(){
    int k,u,v,c;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>u>>k;
        for(int j=0;j<k;j++){
            cin>>v>>c;
            adj[u].push_back(make_pair(v,c));
        }
    }
    dijkstra();
    return 0;
}



Measured memory_bytes: 7976
N,M,X=map(int, input().split())
*A,=map(int, input().split())

for i in range(M):
    if A[i] > X:
        r = M-i
        l = i - (1 if i>0 and A[i-1]==X else 0)
        print(min(l,r))
        exit()
print(0)

Measured memory_bytes: 38256
import std.stdio, std.string, std.conv;
import std.math;

void main() {
    auto input = getStdin!(real[])[0];
    auto area = input * input * PI;
    auto diameter = input * PI * 2.0;
    writefln("%.6f %.6f", area, diameter);
}

T getStdin(T)() {
    string[] cmd;
    string line;
    while ((line = chomp(stdin.readln())) != "") cmd ~= line;
    return to!(T)(cmd);
}

Measured memory_bytes: 2576
#include <stdio.h>

int	main(void)
{
	int	D[210];
	int	N, i, j, flag = 0;

	scanf("%d", &N);
	for (i = 0; i < 2 * N; i++)
		scanf("%d", &D[i]);
	for (i = 0; i < 2 * (N - 2); i += 2)
	{
		if (D[i] == D[i + 1] && D[i + 2] == D[i + 3] && D[i + 4] == D[i + 5])
		{
			flag = 1;
			break;
		}
	}
	if (flag)
		printf("Yes\n");
	else
		printf("No\n");
	return (0);
}

Measured memory_bytes: 1664
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class A
{
	public static void Main()
	{
		long A = GetLong();
		long B = GetLong();
		long C = GetLong();

		long ans = long.MaxValue;
		ans = Math.Min(ans, ((A + 1)/2 - A/2) * B * C);
		ans = Math.Min(ans, ((B + 1)/2 - B/2) * C * A);
		ans = Math.Min(ans, ((C + 1)/2 - C/2) * A * B);
		Console.WriteLine(ans);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}

Measured memory_bytes: 11092
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
 
using namespace std;
int MOD = 1000000007;

signed main(){
    int n,m,c;

    cin >> n >> m >> c;

    int b[30];
    int a[30][30];
    rep(i,m)cin >> b[i];
    rep(i,n)rep(j,m) cin >> a[i][j];

    int ans = 0;

    rep(i,n){
        int s = c;
        rep(j,m)s += a[i][j]*b[j];
        if(s > 0)ans++;
    }
    cout << ans << endl;
    
    

    return 0; 
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://abc121.contest.atcoder.jp/tasks/abc121_a
// rm -r -f test;oj dl http://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_c

Measured memory_bytes: 256
n = int(input())

abc = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * 3 for i in range(n + 1)]
dp[0] = [0, 0, 0]

for i in range(n): # i represents i_th day
    for j in range(3): # j represents j_th activity chosen on the i_th day
        for k in range(3): # k represents k_th activity to be chosen on the day after
            if k != j:
                dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abc[i][k])
print(max(dp[n]))

Measured memory_bytes: 49824
#include <stdio.h>
 
int main(){
	int A,B,K;
  	int i,number,sum=0;
  	int wari[150]={0};
 
  
  if(scanf("%d %d %d", &A,&B,&K) < 3) {
    fprintf(stderr, "error: ill-formed fraction.\n");
}
  
  for(i=1;i<=110;i++){
  	if(A%i == 0 && B%i ==0) wari[i]=1;
    else;
   // printf("wari[%d]%d ",i,wari[i]);
  }
  
  
  for(i=110;i>0;i--){
  	sum+=wari[i];
    if(sum==K) break;
    else;
  }
  
  printf("%d",i);
  
  return 0;
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/03/24  Problem: ABC 122 A / Link: http://abc122.contest.atcoder.jp/tasks/abc122_a  ----- */


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

	char c; cin >> c;
	char ans = 0LL;
	if (c == 'A')ans = 'T';
	if (c == 'T')ans = 'A';
	if (c == 'C')ans = 'G';
	if (c == 'G')ans = 'C';
	
	
	printf("%c\n", ans);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
bool used[555];
set<int> G[555];
void dfs(int v){
  if(used[v]) return;
  used[v]=1;
  for(int u:G[v]) dfs(u);
}
signed main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int s,t;
    cin>>s>>t;
    s--;t--;
    G[s].insert(t);
  }
  memset(used,0,sizeof(used));
  int cnt=0;
  for(int i=0;i<n;i++){
    if(used[i]) continue;
    cnt++;
    dfs(i);
  }
  cout<<m-n+cnt<<endl;
  return 0;
}

Measured memory_bytes: 3244
#include<iostream>
using namespace std;
string a;bool v[2]={0};
int main(){
    cin>>a;
    for(int i=0;i<a.length();i++){
        if(a[i]=='C') v[0]=1;
        if(a[i]=='F'&&v[0])  v[1]=1;
    }
    if(v[1]) cout<<"Yes";
    else cout<<"No";
    return 0;
}

Measured memory_bytes: 256