akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<cmath>
#include<algorithm>

int main()
{
std::vector<int> a(4, 0);
std::string str;
std::cin >> str;
int l = str.length();
for(int i = 0; i < l; i++){
    if(str[i] == 'N'){
        a[0]++;
    } else if(str[i] == 'W'){
        a[1]++;
    } else if(str[i] == 'S'){
        a[2]++;
    } else if(str[i] == 'E'){
        a[3]++;
    }
}
if((a[0] + a[2] > 0 && a[0] * a[2] == 0) || (a[1] + a[3] > 0 && a[1] * a[3] == 0)){
    std::cout << "No" << std::endl;
} else {
    std::cout << "Yes" << std::endl;
}

return 0;
}

Measured memory_bytes: 256
n=int(input())
A=list(map(int,input().split()))
from collections import deque
ans=deque([])
d=deque(A)
for i in range(0,n):
    if i%2==0:
        ans.append(d[i])
    if i%2==1:
        ans.appendleft(d[i])
a=list(ans)
if n%2==1:
    c=a[::-1]
else:
    c=a
print(" ".join(map(str, c)))

Measured memory_bytes: 34036
'use strict';
(function(stdin) { 
  var inputs = stdin.toString();
  (function(S) {
    //????????????????????????
    console.log(~~(S / (60 * 60) )+':'+~~(S % (60 * 60) / 60)+':'+~~(S % 60));
  }(parseInt(inputs.trim(),10))); //????°??????????????¶?????????°?????????
}(require('fs').readFileSync('/dev/stdin', 'utf8')));

Measured memory_bytes: 7640
{
  const main = (
    input: string
  ): void | string | number | string[] | number[] => {
    const r = _reader(input)
    const [a, b] = r.ss()

    return a < b ? a.repeat(Number(b)) : b.repeat(Number(a))
  }

  const _reader = (str: string, i = 0) => {
    const lines = str.trim().split('\n')
    const s = () => lines[i++] || ''
    const n = () => Number(s())

    const mn = (v: string[]) => v.map(Number)
    const sp = (v: string) => v.split(' ')
    const ss = () => sp(s())
    const nn = () => mn(ss())
    const nls = () => mn(lines.slice(i))
    const nnls = () => lines.slice(i).map(v => mn(sp(v)))

    return { lines, s, n, ss, nn, nls, nnls }
  }

  const _getInput = () => require('fs').readFileSync('/dev/stdin', 'utf8')
  const _res = main(_getInput())

  if (typeof _res === 'number' || typeof _res === 'string') console.log(_res)
  if (typeof _res === 'object') console.log(_res.join(' '))
}


Measured memory_bytes: 7372
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

#define INF 93193111451418101
#define LEP(a, n) for(int a = 0; a < n; ++a)
#define FOR(a, s, n) for(int a = s; a < n; ++a)

#define IN std::cin
#define OUT std::cout
using std::endl;

#define LL long long int
#define ll long long int

#define itn int
#define fro for

int main()
{

	ll N, A, B, ans = 0, buf;

	IN >> N >> A >> B;

	FOR(a, 1, N + 1)
	{
		buf = 0;
		buf += a % 100000 / 10000;
		buf += a % 10000 / 1000;
		buf += (a % 1000) / 100;
		buf += (a % 100) / 10;
		buf += (a % 10);

		if (A <= buf && buf <= B) ans += a;

	}

	OUT << ans << endl;

	return 0;
}

Measured memory_bytes: 256
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
    }
    let mut vec = vec![[0usize; 2]; n];
    for i in 0..n {
        input! {
            a: usize,
        }
        vec[i] = [i + 1, a];
    }
    vec.sort_by(|&x, &y| x[1].cmp(&y[1]));

    println!(
        "{}",
        vec.iter()
            .map(|&x| x[0].to_string())
            .collect::<Vec<_>>()
            .join(" ")
    );
}


Measured memory_bytes: 10084
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
#from fractions import gcd
#from math import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


r = I()
print(3*r**2)

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

int main(void){
    int N;
    long long D;
    cin >> N >> D;
    vector<long long> X(N), Y(N);
    for(int i=0;i<N;i++) cin >> X.at(i) >> Y.at(i);

    int ans = 0;

    for(int i=0;i<N;i++){
        if( (X.at(i)*X.at(i))+(Y.at(i)*Y.at(i)) <= D*D ) ans++;
    }

    cout << ans << endl;

    return 0;
}

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

int main(){
	long long int a,b;
	cin>>a>>b;
	long long int ans=0;
	long long int left,right;
	if (a%2==0) {
		left=a;
	}else {
		left=a-1;
		ans=ans^left;
	}
	if (b%2==1) {
		right=b;
	}else {
		right=b+1;
		ans=ans^right;
	}
	long long int num1=(right-left+1)/2;
	ans=ans^(num1%2);
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define long long long
#define ull unsigned long long
#define up(i,a,b) for (int i=a; i<=b; i++)
#define upadj(i,adj) if (adj.size()>0) up(i,0,adj.size()-1)
#define down(i,a,b) for (int i=a; i>=b; i--)
#define endl '\n'
#define pb push_back
#define X first
#define Y second
#define II pair<int, int>
#define III pair<int, pair<int, int> >
#define V vector
#define debug(X) cerr<< #X << "=" <<X << endl
#define show(X,a,b) {cerr << #X << " = "; up(__,a,b) cerr << X[__] << ' '; cerr << endl;}
#define gc getchar
#define pc putchar
using namespace std;

inline void read(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for (;((c<48 || c>57) && c != '-') ;c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
inline void writeln(int x){

         char buffor[21];
         register int i=0;
         int neg=0; if (x<0) {neg=1; x= -x;}
         do{
               buffor[i++]=(x%10)+'0';
               x/=10;
            } while(x);
           i--;
           if (neg) pc('-');
           while(i>=0) pc(buffor[i--]);
           pc('\n');
       }
const int N= (int) 1e5+10;
int n,m,q;
V<int> a[N];
struct query
{
    int v,d,c;
}que[N];
int f[N][11];

void input()
{
    cin>>n>>m;
    up(i,1,m)
    {
        int u,v; cin>>u>>v;
        a[u].pb(v); a[v].pb(u);
    }
    cin>>q;
    up(i,1,q)
    {
        int v,d,c; cin>>v>>d>>c;
        que[i]= {v,d,c};
    }

}
void dfs(int u,int d,int col)
{
    if (f[u][d]!=0) return;
    f[u][d]= col;
    if (d==0) return;
    dfs(u,d-1,col);
    for (auto v: a[u]) dfs(v,d-1,col);
}
void solve()
{
    down(i,q,1) dfs(que[i].v,que[i].d,que[i].c);
    up(i,1,n) cout<<f[i][0]<<endl;
}

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

    #ifdef I_Love_Pork
    #define TASK "tmp"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
    #endif

    input();
    solve();

    return 0;
}


Measured memory_bytes: 12024
#include <bits/stdc++.h>
using namespace std;
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;
}

#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define F first
#define S second

typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1000000;
const int minf = -1000000;
const ll lnf = 1e12;
const ll mlnf = -1e12;
const double e = 1e-10;

void debug_vector(vector<int>& v)
{
    int n = v.size();
    for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}


//////////////////////
//// coding start ////
//////////////////////

// global variet



void solve();

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



void solve(){
    long long N; cin >> N;
    long long ans = 0;
    for (long long i = 1; i <=N; i++){
        if (i % 3 == 0 || i % 5 == 0){
            continue;
        }
        else{
            ans += i;
        }
    }
    printf("%lld\n", ans);
}


Measured memory_bytes: 3764
#include <iostream>
#include <stdio.h>

#define MAX_N 100'000

using namespace std;

int A[MAX_N];

int main() {
  int N;
  cin >> N;
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  int cnt = 0;
  for (int i = 0; i < N; ++i) {
    if (i == A[A[i] - 1] - 1) {
      ++cnt;
    }
  }
  printf("%d\n", (int)(cnt / 2));
}

Measured memory_bytes: 3536
s = input()
n = len(s)

a = (n-1)//2
b = (n+3)//2

def is_kaibun(s):
    for i in range(len(s)//2):
        if s[i] != s[-1-i]:
            return False
    return True


if (is_kaibun(s)==True) and (is_kaibun(s[:a])==True) and (is_kaibun(s[(b-1):])==True):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>

int main(void){
    int id;
    char blood[2];
    int bldCnt[4];
    
    bldCnt[3]=bldCnt[2]=bldCnt[1]=bldCnt[0]=0;
    while (scanf("%d,%s",&id,blood)!=EOF){
        if (strcmp(blood,"A")==0) bldCnt[0]++;
        if (strcmp(blood,"B")==0) bldCnt[1]++;
        if (strcmp(blood,"AB")==0) bldCnt[2]++;
        if (strcmp(blood,"O")==0) bldCnt[3]++;    
    }
    for (int i=0; i<4; i++){
        printf("%d\n", bldCnt[i]);
    }

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
		/*#ifndef ONLINE_JUDGE
	    // for getting input from input.txt
	    freopen("input.txt", "r", stdin);
	    // for writing output to output.txt
	    freopen("output.txt", "w", stdout);
	#endif*/
fast();
//ll  t;cin>>t;while(t--)

{  ll sum=753;
	string s;
	cin>>s;
	ll n=s.length();
	string z=s.substr(0,3);
	ll ans=stoi(z);
	ans=abs(sum-ans);
	for(int i=1;i<n-2;i++)
	{
		string t=s.substr(i,3);
		ll temp=stoi(t);
		temp=abs(sum-temp);
		if(temp<ans)
		{
			ans=temp;
		}
	}cout << ans<<endl;

}
return 0;
}

Measured memory_bytes: 256
N = int(input())
#L=[list(map(int, input().split())) for i in range(int(input()))]

L=list(map(int, input().split()))
#print(L)
#L=[list(map(int, input().split())) for i in range(N)]
L_odd=L[::2]
j=0
for i in L_odd:
    #print(i)
    if i%2==1:
        j+=1
print(j)

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

using namespace std;

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

    vector<long long> monsters(n + 1);
    vector<long long> heroes(n);

    long long result = 0;

    for (long long i = 0; i <= n; i++)
    {
        cin >> monsters[i];
    }
    for (long long i = 0; i < n; i++)
    {
        cin >> heroes[i];
    }

    long long j = 0;
    for (long long i = 0; i < n; i++)
    {
        if (heroes[i] >= monsters[j])
        {
            if (monsters[j + 1] >= heroes[i] - monsters[j])
            {
                monsters[j + 1] -= (heroes[i] - monsters[j]);
                result += heroes[i];
            }
            else
            {
                result += monsters[j] + monsters[j + 1];
                monsters[j + 1] = 0;
            }
        }
        else
        {
            result += heroes[i];
        }
        // cout << result << endl;
        j++;
    }

    cout << result;

    return 0;
}

Measured memory_bytes: 1792
N = int(input())
balls = [tuple(map(int, input().split())) for _ in range(N)]

balls.sort()

ans = N
for i in range(N):
    for j in range(i+1, N):
        p, q = balls[j][0]-balls[i][0], balls[j][1]-balls[i][1]
        useds = [False] * N
        num = 0
        for a in range(N):
            if useds[a]: continue
            useds[a] = True
            num += 1
            x, y = balls[a]
            for b in range(a+1, N):
                if useds[b]: continue
                if balls[b] == (x+p, y+q):
                    useds[b] = True
                    x, y = balls[b]
        ans = min(ans, num)

print(ans)


Measured memory_bytes: 46044
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;
#define INF 100000000
typedef long long ll;

int table[11][1000]; // memo[n][s]には最終的にn個の数字を使って和がsのものを何通りで作れるかが入る
int memo[11];

void dfs(int depth, int sum) {
    table[depth-1][sum]++;
    for (int i = 0; i < 10; i++) {
        if (memo[i] == 0) {
            memo[i] = 1;
            dfs(depth+1, sum + depth * i);
            memo[i] = 0;
        }
    }
}

int main(void) {
    dfs(1, 0);
    int n, s;
    while (cin >> n >> s) {
        if (n > 10 || s > 330) {
            cout << 0 << endl;
        } else {
            cout << table[n][s] << endl;
        }
    }
}

Measured memory_bytes: 1204
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,x=0,y=0,z=0,ans=0,m,j,tmp;
char s[15];
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%s",s);
		m=strlen(s);
		for(j=0;j<m;j++)if(s[j]=='A'&&j+1<m&&s[j+1]=='B')ans++;
		if(s[0]!='B'&&s[m-1]=='A')x++; 
		if(s[0]=='B'&&s[m-1]!='A')y++; 
		if(s[0]=='B'&&s[m-1]=='A')z++; 
	}
	if(z==0)
	{
		ans+=min(x,y);
	}
	else
	{
		ans+=z-1;
		if(x>0)x--,ans++;
		if(y>0)y--,ans++;
		tmp=min(x,y);
		ans+=tmp;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner sc = new Scanner(System.in);

		isprime = new boolean[MAX_N + 1];
		numofprimes = new int[MAX_N + 1];

		Arrays.fill(isprime, true);
		isprime[0] = isprime[1] = false;
		for (int i = 2; i*i <= MAX_N; i++) {
			if (isprime[i] == false) continue;
			for (int j = i+1; j <=MAX_N; j++) {
				if (j % i == 0) isprime[j] = false;
			}
		}

		for (int i = 2; i <= MAX_N; i++) {
			if (isprime[i]) {
				numofprimes[i] = numofprimes[i-1] + 1;
			} else {
				numofprimes[i] = numofprimes[i-1];
			}
		}

		while ( sc.hasNext() ) {
			int n = sc.nextInt();
			System.out.println( numofprimes[n] );
		}
	}

	public static final int MAX_N = 999_999;

	public static int[] numofprimes;

	public static boolean[] isprime;

}

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

ans = 0
for i in range(n):
    town_a = a[i]
    town_b = a[i+1]
    power = b[i]
    if power > town_a:
        ans += town_a
        power -= town_a
    else:
        ans += power
        continue
    if power > town_b:
        ans += town_b
        a[i+1] = 0
    else:
        ans += power
        a[i+1] -= power
print(ans)

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

using ll = long long;
using vi = vector<int>;
using vll = vector<long long>;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

constexpr long long mod = 1000000007;

#define rep(i, n) for (int i = 0; i < n; i++)

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

    int n;
    cin >> n;
    map<int, int> mp;
    rep(i, n) {
        int t;
        cin >> t;
        if (mp.count(t)) {
            mp[t]++;
        } else {
            mp[t] = 1;
        }
    }

    int cnt = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        if (itr->first <= itr->second) {
            cnt += itr->second - itr->first;
        } else {
            cnt += itr->second;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,t,a,h,ans; cin>>n>>t>>a;
  double d=100100,tmp;
  for(int i=1; i<=n; i++){
    cin>>h;
    tmp=abs(t-h*0.006-a);
    if(d>tmp) d=tmp,ans=i;
  }
  cout<<ans;
}

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

ll d[200][200],ans=1e10;
int n,m,R;

void warshall_floid(){
    for(int k = 0;k < n;k ++){
        for(int i = 0;i < n;i ++){
            for(int j = 0;j < n;j ++){
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
} 

int main(){
    cin >> n >> m >> R;
    vector<int> r(R);
    fill(d[0],d[200],1e10);
    for(int i = 0;i < 200;i ++){
        d[i][i] = 0;
    }
    for(int i = 0;i < R;i ++){
        cin >> r[i];
        r[i] --;
    }
    for(int i = 0;i < m;i ++){
        ll a,b,c;
        cin >> a >> b >> c;a --;b --;
        d[a][b] = c;
        d[b][a] = c;
    }

    warshall_floid();

    sort(r.begin(),r.end());
    do{
        ll cost = 0;
        for(int i = 0;i < r.size()-1;i ++){
            cost += d[r[i]][r[i+1]];
        }
        ans = min(ans,cost);
    }while(next_permutation(r.begin(),r.end()));

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

Measured memory_bytes: 512
#include <cstdio>
#include <algorithm>

int n,m;
int p[55][2],q[55][2];

int main(void)
{
    int i,j;
    int u,v;

    scanf("%d %d",&n,&m);
    for(i = 1;i <= n;++i)
        scanf("%d %d",&p[i][0],&p[i][1]);
    for(i = 1;i <= m;++i)
        scanf("%d %d",&q[i][0],&q[i][1]);

    for(i = 1;i <= n;++i)
    {
        u = 1000000000;
        v = -1;
        for(j = 1;j <= m;++j)
            if(std::abs(p[i][0] - q[j][0]) + std::abs(p[i][1] - q[j][1]) < u)
                u = std::abs(p[i][0] - q[j][0]) + std::abs(p[i][1] - q[j][1]),v = j;
        printf("%d\n",v);
    }
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		String ans = "";

		if (A % 2 != B % 2) {
			ans = "IMPOSSIBLE";
		} else {
			ans = String.valueOf((A + B) / 2);

		}

		System.out.println(ans);
		sc.close();

	}
}


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


#define int long long 

int32_t main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, t, ans = 0, p = -1e10; cin >> n >> t;
	for(int i = 1; i <= n; i++) {
		int x; cin >> x;
		int y = x + t - 1;
		if(x <= p) {
			ans += y - p;
		} else {
			ans += t;
		}
		p = y;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3532
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}

int main() {
	ll H, N;
	cin>>H >> N;
	int n = min(H, N);
	int m = max(H, N);

	for (int i = 0; i < m; i++) {
		cout<< n;
		
	}

	
	
}


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

int main(int argc, char **argv)
{
	float d,t,s;
  cin>>d>>t>>s;
  if (d/s>t) cout<<"No"<<"\n";
  else cout<<"Yes"<<"\n";
	return 0;
}


Measured memory_bytes: 3716
while True:
    n, x = map(lambda a: int(a), input().split(" "))
    if (n, x) == (0, 0):
        break
    if x < 1 + 2 + 3 or x > n + (n - 1) + (n - 2):
        print(0)
        continue
    values = list(range(1, n + 1 if n - 3 <= x else x + 1))
    N = len(values)
    count = 0
    for i1 in range(N - 2):
        for i2 in range(i1 + 1, N - 1):
            for i3 in range(i2 + 1, N):
                if values[i1] + values[i2] + values[i3] == x:
                    count += 1
    print(count)



Measured memory_bytes: 5596
import System.Random
import Control.Monad
main = do
  xs <- (return . map (read::String->Int) . words) =<< getLine
  ys <- (return . map (read::String->Int) . words) =<< getLine
  css <- replicateM 1000 $ randomRIO (0, 3)
  putStrLn $ (\b -> if b then "Yes" else "No") $ any (== ys) $ scanl f1 xs $ map (toEnum::Int->Command) css
  
data Command = N | S | E | W deriving (Show, Enum)
f1 :: [Int] -> Command -> [Int]
f1 [x1,x2,x3,x4,x5,x6] N = [x2,x6,x3,x4,x1,x5]
f1 [x1,x2,x3,x4,x5,x6] S = [x5,x1,x3,x4,x6,x2]
f1 [x1,x2,x3,x4,x5,x6] E = [x4,x2,x1,x6,x5,x3]
f1 [x1,x2,x3,x4,x5,x6] W = [x3,x2,x6,x1,x5,x4]
f0 c | c == 'N' = N
f0 c | c == 'S' = S
f0 c | c == 'E' = E
f0 c | c == 'W' = W


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

int main() {
  int n; cin >> n;
  ll l1 = -1, l2 = 2;
  for (int i = 1; i <= n; i++) {
    if (i & 1)
      l1 = l1 + l2;
    else
      l2 = l1 + l2;
  }
  cout << (n & 1 ? l1 : l2) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

void solve(int n, long i, long j){
  assert(i<(1L<<n) && j<(1L<<n));
  if(n==1){
    if(i!=j) cout << "R" << endl;
    else cout << "L" << endl;
    return;
  }

  bool bi = i >= (1L<<(n-1));
  bool bj = j >= (1L<<(n-1));

  bool ans;
  if(bj) ans = i%4==1 || i%4==2;
  else ans = i%4==0 || i%4==3;

  if(ans) cout << "R";
  else cout << "L";

  i /= 2;

  if(ans){ // R
    if(bj) j = (1L<<n) - j - 1;
  }
  else { // L
    if(bj) j = j - (1L<<(n-1));
    else j = (1L<<(n-1)) - j - 1;
  }

  solve(n-1, i, j);
}

int main(){
  long n,i,j;
  while(cin>>n>>i>>j, n|i|j){
    solve(n, i-1,j-1);
  }

  return 0;
}

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

int main(){
  int A,B,C,K,ans = 0;
  int a = 0;
  
  cin >> A >> B >> C;
  cin >> K;

  int max = A;
  if(max < B){
    max = B;
    a = 1;
  }
  if(max < C){
    max = C;
    a = 2;
  }

  if(a == 0){
    cout << A * pow(2,K) + B + C << endl;
  }else if(a ==1){
    cout << A + B * pow(2,K) + C << endl;
    
  }else{
    
    cout << A + B + C* pow(2,K) << endl;

  }
  
  
  return 0;
}


Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = [0] + LI()

for i in range(1, n + 1):
    A[i] = (A[i] + A[i - 1] - 1) % k


ans = 0
D = defaultdict(int)
for j in range(n + 1):
    if j >= k:
        D[A[j - k]] -= 1
    ans += D[A[j]]
    D[A[j]] += 1





print(ans)


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

int main(){

  long long N, W, i, j;
  cin>>N>>W;
  vector<long long> v(N), w(N);
  vector<vector<long long>> dp(N+1, vector<long long>(W+1, 0));

  for(i=0; i<N; i++){
    cin>>w[i]>>v[i];
  }

  for(i=0; i<N; i++){
    for(j=0; j<W+1; j++){
      if(j+w[i]<=W) dp[i+1][j+w[i]]=max(dp[i][j]+v[i], dp[i+1][j+w[i]]);
      dp[i+1][j]=max(dp[i][j], dp[i+1][j]);
    }
  }
  
  /*for(i=0; i<N+1; i++){
    for(j=0; j<W+1; j++){
      cout<<dp[i][j]<<" ";
    }
    cout<<endl;
  }*/
  cout<<dp[N][W]<<endl;
  return 0;
}

Measured memory_bytes: 83164
#include<bits/stdc++.h>
#define y1 wzpakking
#define ll long long
#define pa pair<int,int>
#define mo 998244353
using namespace std;
const int N=300005;
int fac[N],inv[N];
int n,a,b,ans;
long long k;
int C(int x,int y){
	return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo;
}
int main(){
	scanf("%d%d%d%lld",&n,&a,&b,&k);
	fac[0]=inv[0]=inv[1]=1;
	for (int i=2;i<=n;i++)
		inv[i]=1ll*inv[mo%i]*(mo-mo/i)%mo;
	for (int i=1;i<=n;i++){
		fac[i]=1ll*fac[i-1]*i%mo;
		inv[i]=1ll*inv[i-1]*inv[i]%mo;
	}
	for (int red=0;red<=n;red++){
		long long rest=k-1ll*red*a;
		if (rest<0||rest>1ll*b*n||rest%b) continue;
		int blue=rest/b;
		ans=(ans+1ll*C(n,red)*C(n,blue))%mo;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 2560
S = input()
K = input()

#A = int(l[0])


length_1 = len(S)
K = int(K)

i =int(S)
v_1 = []
#cnt = []
while i > 0:
    v_1.append( i % 10 )
    #cnt.append(1)
    i //= 10 # 必須
v_1.reverse()

length_n = 0
target_v_num = 0

while length_n < K:
    V = v_1[target_v_num]
    length_n = length_n + 1
    if V > 1:
        length_n = length_n + K
    target_v_num = target_v_num + 1


print(V)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define MOD ((int)(1e9+7))
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define float long double


	
int32_t main()
{
	IOS
	int n;cin>>n;
	int ans=0;
	int ba=0,a=0,b=0;
	for(int i=0;i<n;i++)
	{
		string s;cin>>s;
		for(int j=0;j<=(int)s.length()-2;j++)if(s.substr(j,2)=="AB")ans++;
		ba+=(s[0]=='B' && s[(int)s.length()-1]=='A');
		a+=(s[0]!='B' && s[(int)s.length()-1]=='A');
		b+=(s[0]=='B' && s[(int)s.length()-1]!='A');
	}
	
	int c=0;
	if(ba==0)c=min(a,b);
	else if( ba && a+b>0) c=ba + min(a,b);
	else if( ba && a+b==0) c=ba-1;
	ans+=c;
	cout<<ans<<endl;
	
	
	
		
		
			
			
	
	
	
}
	
			
	
	
	
	
	

	

	

	
		


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		int student = sc.nextInt();
		int[] school = new int[student];
		//記憶する配列作成
		int[] memory = new int[student];
		for(int i = 0;i<student; i++) {
			school[i] = sc.nextInt();
		}
		//memory配列にデータを入れ込む。
		for(int i=0 ; i<student; i++) {
			memory[school[i]-1] = i+1;
		}
		//最終結果出力
		for(int i= 0; i<memory.length; i++) {
			System.out.println(memory[i] + " ");
		}

	}
}

Measured memory_bytes: 63188
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
typedef long long ll;
int n, m;


int main()
{
    scanf("%d%d", &n, &m);
    if(n >= 10)printf("%d\n", m);
    else{
        printf("%d", m + 100 * (10 - n));
    }

    return 0;
}


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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> e(3 * n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> e[3 * i + j];
    }
  }
  vector<int> dp(3 * (n + 1));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        if (j == k) continue;
        dp[3 * (i + 1) + j] =
            max(dp[3 * (i + 1) + j], dp[3 * i + k] + e[3 * i + j]);
      }
    }
  }
  int ans = max({dp[3 * n], dp[3 * n + 1], dp[3 * n + 2]});
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
package main

import (
  "fmt"
)

func main() {
  var N int
  fmt.Scan(&N)
  
  tmp := N
  total := 0
  for tmp > 0 {
    total = total + tmp % 10
    tmp = tmp / 10
  }
  if N % total == 0 {
    fmt.Println("Yes")
  } else {
    fmt.Println("No")
  }
}

Measured memory_bytes: 512
import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		String in = stdIn.nextLine();
		
		in = in.replaceAll("apple", "AAAAA");
		in = in.replaceAll("peach", "apple");
		in = in.replaceAll("AAAAA", "peach");
		System.out.println(in);
	}
}

Measured memory_bytes: 17128
n = int(input())
length = list(map(int,input().split()))

# n = 1 or 2
if n == 1 or n == 2:
  print(0)
  exit()

# n >= 3
len_count = {}
for l in length:
  if l not in len_count:
    len_count[l] = 1
  else:
    len_count[l] += 1

uniq_len = sorted(list(set(length)))
n_len = len(uniq_len)
triangle = []

from itertools import combinations
for c in combinations(uniq_len,3):
  c = sorted(list(c))
  if c[0] + c[1] > c[2]:
    triangle.append(c)
      
ans = 0
for t in triangle:
  ans += len_count[t[0]] * len_count[t[1]] * len_count[t[2]]

print(ans)

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

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

  vector<int> p(N);
  rep(i,0,N-1) cin >> p[i];

  sort(p.begin(), p.end());

  int ans = 0;
  rep(i,0,K-1) ans += p[i];

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


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

f = [[0]*(N+1)]*(N+1)
f[0][0] = min(A[0],B[0])

sum_f = f[0][0]

for i in range(N):
    f[i][i+1] = min(A[i+1],B[i]-f[i][i])
    sum_f += f[i][i+1]
    if i == N-1:
        break
    f[i+1][i+1] = min(A[i+1]-f[i][i+1],B[i+1])
    sum_f += f[i+1][i+1]

print(sum_f)

Measured memory_bytes: 19004
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
const ll MOD = 1000000007;
using namespace std;

int main(){
    int n, x, mn=1000000; cin >> n >> x;
    REP(i, n){
        int m; cin >> m;
        x -= m;
        mn = min(mn, m);
    }
    cout << n + x/mn << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int n; cin >> n;
  vector<ll> data(n); REP(i,n) cin >> data[i];
  ll sum = 0;
  FOR(i,1,n){
    if(data[i] < data[i-1]){
      sum += data[i-1] - data[i];
      data[i] = data[i-1];
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 4832
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
     nm = input[0].split(" ");
	//文字列から10進数に変換するときはparseIntを使います
	var N = parseInt(nm[0], 10);
	var M = parseInt(nm[1], 10);
   var n = nm[0];
	var m = nm[1];
  var A ='';var B = '';var AB =[];
  for (i=0;i<M;i++){A +=n;}

　　　
  for (i=0;i<N;i++){B +=m;}
 　　　　 AB.push( A,B);
    
   
 //   console.log(A,B);
 
//  console.log(AB);
  AB.sort();
 // console.log(AB);
 　console.log(AB[0]);
    

	
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        s: Chars,
    };
    let vs: String = s.iter().collect();
    if s[s.len() - 1] == 's' {
        println!("{}{}", vs, "es");
    } else {
        println!("{}{}", vs, "s");
    }
}


Measured memory_bytes: 2176
a,b=input().split(" ")
a=int(a)
b=int(b)
 
a_str=""
b_str=""
for i in range(a):
  b_str=b_str+str(b)
for i in range(b):
  a_str=a_str+str(a)
if int(a_str[0]) > int(b_str[0]):
  print(b_str)
elif int(a_str[0]) < int(b_str[0]):
  print(a_str)
else:
  print(a_str)

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;

int const mod = 1e9 + 7;
ll n, k;

ull nhan(ull a,ull b)
{
    if (b == 0) return 0;
    ull t;
    t = nhan(a, b/2) % mod;
    t = t % mod + t % mod;
    if (b % 2 == 0)
        return t % mod;
    else return (t % mod + a % mod) % mod;
}

ull mu(ull a,ull b)
{
  if (b == 0)
    return 1;
  ull t;
  t = mu(a, b/2) % mod;
  t = nhan(t, t) % mod;
  if (b % 2 == 0) return t % mod;
  else return nhan(t,a) % mod;
}

int main()
{
    cin >> n >> k;
    ull ans = 0;
    for(int i = k; i <= n + 1; ++i)
		ans = (ans + nhan(i, n - i + 1) + 1) % mod;
		cout << ans % mod;
}


Measured memory_bytes: 3628
#include<iostream>
#include <cstdlib>
#include<list>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<stack>
#define MAX 101
using namespace std;
int main() {
	int n, a, k, d, data[MAX][MAX] = { 0,0 }; cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a >> k;
		for (int j = 0; j < k; j++)
		{
			cin >> d;
			data[i][d - 1] = 1;
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (j)cout << " ";
			cout << data[i][j];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    ll h, w;
    cin >> h >> w;
    ll ans = (h % 3 == 0 || w % 3 == 0) ? 0 : min(h,w);
    if (ans != 0) {
        FOR(i,1,h) {
            vector<ll> s(3);
            s[0] = i * w;
            ll w1 = w / 2;
            ll w2 = w - w1;
            s[1] = (h-i) * w1;
            s[2] = (h-i) * w2;
            sort(ALL(s));
            ans = min(ans,s[2]-s[0]);
        }
        FOR(i,1,w) {
            vector<ll> s(3);
            s[0] = i * h;
            ll h1 = h / 2;
            ll h2 = h - h1;
            s[1] = (w-i) * h1;
            s[2] = (w-i) * h2;
            sort(ALL(s));
            ans = min(ans,s[2]-s[0]);
        }    }

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define swap(a, b, type) { type _tmp = a; a = b; b = _tmp; }
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int A[3], K;

	cin >> A[0] >> A[1] >> A[2] >> K;

	sort(A, A + 3);

	rep(i, K) A[2] *= 2;

	cout << A[0] + A[1] + A[2] << endl;

	return 0;
}


Measured memory_bytes: 256
#print("<input>") #
N,M=map(int,input().split())
A=[[] for i in range(N)]
for i in range(M):
    Pi,Si=map(str,input().split())
    Pi=int(Pi)
    A[Pi-1].append(Si)

#print("<test>") #
#print("A=",A) #

nAC=0
nWA=0
inWA=0
j=0
for i in range(N):
    #print("i=",i) #
    if len(A[i])==0:
        pass
    else: 
        while A[i][j]=="WA":
            inWA+=1
            nWA+=1
            #print("j=",j) #
            #print("inWA=",inWA) #
            #print("nWA=",nWA) #
            if j==len(A[i])-1:
                nWA-=inWA
                break
            else:
                pass
            j+=1
        if A[i][j]=="AC":
            nAC+=1
        else:
            pass
        inWA=0
        j=0
        #print("inWA=",inWA) #
        #print("nWA=",nWA) #
        

#print("<ans>") #
print("{0} {1}".format(nAC,nWA))

Measured memory_bytes: 20368
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1e8
using namespace std;

struct edge{
	int to,cost,id,h;
	edge(){}
	edge(int tt,int cc,int hh,int ii){
		to=tt;
		cost=cc;
		id=ii;
		h=hh;
	}
};

struct data{
	int cost,h,v;
	data(){}
	data(int vv,int hh,int cc){
		v=vv;
		h=hh;
		cost=cc;
	}
	bool operator<(const data &d1)const{
		return d1.cost<cost;
	}
};

int n,m,h,k,p;
vector<edge> G[101];
int s,t;
int cost[1<<9];
int dist[101][30];

int dijk(int bit){
	memset(dist,-1,sizeof(dist));
	priority_queue<data> que;
	que.push(data(s,0,0));
	dist[s][0]=0;
	while(que.size()){
		data q=que.top();
		que.pop();
		if(dist[q.v][q.h]<q.cost)continue;
		for(int i=0;i<G[q.v].size();i++){
			edge e=G[q.v][i];
			int nc=q.cost;
			if(!(bit>>e.id & 1))nc+=e.cost;
			if(q.h+e.h<=h && (dist[e.to][q.h+e.h]>nc || dist[e.to][q.h+e.h]==-1)){
				dist[e.to][q.h+e.h]=nc;
				que.push(data(e.to,q.h+e.h,nc));
			} 
		}
	}
	int res=INF;
	for(int i=0;i<=h;i++){
		if(dist[t][i]!=-1)res=min(res,dist[t][i]);
	}
	return res;
}

int l[300],d[300],pbit[300];
int dp[300][1<<8];

int main(void){
	while(1){
		scanf("%d %d %d %d",&n,&m,&h,&k);
		if(n+m+h+k==0)break;
		for(int i=0;i<n;i++){
			G[i].clear();
		}
		for(int i=0;i<m;i++){
			int a,b,c,hh,r;
			scanf("%d %d %d %d %d",&a,&b,&c,&hh,&r);
			a--;
			b--;
			r--;
			G[a].push_back(edge(b,c,hh,r));
			G[b].push_back(edge(a,c,hh,r));
		}

		scanf("%d %d",&s,&t);
		s--;
		t--;
		scanf("%d",&p);
		
		memset(pbit,0,sizeof(pbit));

		for(int i=0;i<p;i++){
			scanf("%d %d",&l[i],&d[i]);
			for(int j=0;j<l[i];j++){
				int ki;
				scanf("%d",&ki);
				ki--;
				pbit[i]+=(1<<ki);
			}
		}
		for(int i=0;i<(1<<k);i++){
			cost[i]=dijk(i);
		}

		for(int i=0;i<=p;i++){
			for(int j=0;j<(1<<k);j++){
				dp[i][j]=INF;
			}
		}
		dp[0][0]=0;
		for(int i=0;i<p;i++){
			for(int j=0;j<(1<<k);j++){
				if(dp[i][j]>=0){
					dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
					dp[i+1][j|pbit[i]]=min(dp[i+1][j|pbit[i]],dp[i][j]+d[i]);
				}
			}
		}
		int res=INF;
		for(int i=0;i<(1<<k);i++){
			res=min(res,dp[p][i]+cost[i]);
		}
		printf("%d\n",res==INF?-1:res);
	}
	return 0;
}

Measured memory_bytes: 1456
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
 
int main(void)
{
    string str;
    int N;
    cin >> N;
    cin >> str;
    ll R,G,B;
    R=B=G=0;
    for(int a=0;a<N;a++){
        if(str[a]=='R'){
            R++;
        }else if(str[a]=='G'){
            G++;
        }else{
            B++;
        }
    }
    ll ans=R*G*B;
    for(int a=1;a<=N;a++){
        for(int x=0;x+2*a<N;x++){
            char k=str[x];
            char f=str[x+a];
            char g=str[x+2*a];
            if(k!=f&&f!=g&&g!=k){
                ans--;
            }
        }
    }
    cout << ans <<endl;
}

Measured memory_bytes: 3636
#include <iostream>

using namespace std;

int main(){

    int N;
    cin >> N;
    bool second = true;
    int a;

    for (int i=0; i<N; i++) {
        cin >> a;
        if (a%2 != 0) {
            second = false;
            break;
        }
    }

    if (second) {
        cout << "second" << endl;
    }
    else {
        cout << "first" << endl;
    }

    return 0;
}


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

int main() {
  string s;
  cin >> s;
  int ans = 0;
  rep(i, s.size() / 2) {
    if (s[i] != s[s.size() - 1 - i]) {
      ans++;
    }
  }

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

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

int main() {
  int N;
  cin >> N;
  int a[N];
  for(int i=0; i<N; i++){
    cin >> a[i];
  }
  int m=a[0];
  int M=a[0];
  for(int i=0; i<N; i++){
    if(m>a[i]){
      m=a[i];
    }
    else if(M<a[i]){
      M=a[i];
    }
  }
  cout << M-m << endl;
}


Measured memory_bytes: 256
program prob5
    implicit none
    character(len=500005) :: s
    character(len=1) :: tmps
    integer(8) :: is(500005), n, i, tmp, tmpi
    integer(8) :: ans
    read(*,*) s

    n = len_trim(s) + 1

    do i = 1, n
        is(i) = 0
    end do

    if(s(1:1) == '<') then
        tmpi = 1
        tmps = '<'
    else
        tmpi = 2
        is(1) = 0
        tmps = '>'
    end if
    tmp = 1
    do i = 2, n-1
        if (s(i:i) == tmps) then
            tmp = tmp + 1
        else
            is(tmpi) = tmp
            tmp = 1
            tmpi = tmpi + 1
            tmps = s(i:i)
        end if
    end do
    is(tmpi) = tmp

    
    ans = 0
    do i = 1, n
        ans = ans + is(i) * (is(i) - 1) / 2
    end do

    do i = 1, n
        if (mod(i,2) == 0) then
            cycle
        else
            ans = ans + max(is(i), is(i+1))
        end if
    end do
   
    write(*,*) ans

    stop
contains
end program prob5

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


int main(){
   int n,count10 = -1,count1=-1,count5=-1;
   long long m;
   cin >> n >> m ;
   for (int i = 0;i <= n;i++){
       for (int j = 0;j <= n-i;j++){
           int  c = n-i-j;
           int total = 10000*i + 5000*j + 1000*c;
           if (total == m){
               count10 = i;
               count5 = j;
               count1 = c;
           }

       }
   }
    cout << count10 << " " << count5 << " " << count1 << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_upd>
//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : K-th element in a set (counting from zero).
*/
using namespace std;

#define LL long long
#define LD long double
#define PB push_back
#define MP make_pair
#define all(x) x.begin(), x.end()

const LL MOD = 998244353;
const LD EPS = 0.0000001 ;

LL pows(LL a, LL b)
{
	if (b == 0) return 1LL;
	LL temp = pows(a, b / 2);
	temp = (temp * temp) % MOD;
	if (b % 2) temp = (temp * a) % MOD;
	return temp;
}

int main(void)
{
	LD L; cin >> L;
	LD sz = L / 3.0;
	LD vol = sz * sz * sz;

	cout << fixed << setprecision(10) << vol << endl;

	return 0;
}




Measured memory_bytes: 256
#include<stdio.h>
#define MAX 5000
#define NIL -1

struct Node_struct{int p, l, r;}; 
typedef struct Node_struct Node;
Node A[MAX];
int D[MAX], H[MAX];

int Sibling(int i){
  if(A[i].p == NIL) return NIL;
  if(A[A[i].p].l != i && A[A[i].p].l != NIL) return A[A[i].p].l;
  if(A[A[i].p].r != i && A[A[i].p].r != NIL) return A[A[i].p].r;
  return NIL;
}

void print(int u){
  int i, c, degree = 0;
  printf("node %d: parent = %d, sibling = %d, ", u, A[u].p, Sibling(u));
  if(A[u].l != NIL) degree += 1;
  if(A[u].r != NIL) degree += 1;
  printf("degree = %d, ", degree);
  printf("depth = %d, ", D[u]);
  printf("height = %d, ", H[u]);
  if(A[u].p == NIL) printf("root\n");
  else if(A[u].l == NIL && A[u].r == NIL) printf("leaf\n");
  else printf("internal node\n");
}

void calcDepth(int u, int p){
  if(u == NIL) return;
  D[u] = p;
  calcDepth(A[u].l, p + 1);
  calcDepth(A[u].r, p + 1);
}

int Height(int u) {
  int h1 = 0, h2 = 0;
  if(A[u].l != NIL) h1 = Height(A[u].l) + 1;
  if(A[u].r != NIL) h2 = Height(A[u].r) + 1;
  if(h1 >= h2) return H[u] = h1;
  else return H[u] = h2;
}

int main(){
  int i, n, root;
  int id, left, right;
  scanf("%d", &n);
  for(i = 0 ; i < n ; i++) A[i].p = A[i].l = A[i].r = NIL;
  for(i = 0 ; i < n ; i++){
    scanf("%d %d %d", &id, &left, &right);
    A[id].l = left;
    if(left != NIL) A[left].p = id;
    A[id].r = right;
    if(right != NIL) A[right].p = id;
  }
  for(i = 0 ; i < n ; i++) if(A[i].p == NIL) root = i;
  calcDepth(root, 0);
  Height(root);
  for(i = 0 ; i < n ; i++) print(i);
}



Measured memory_bytes: 1956
#include <bits/stdc++.h>
using namespace std;
long long int lmin(long long int a, long long int b){
    if(a<b)return a;
    else return b;
}
int main()
{
    long long int n,W;
    cin >> n >> W;
    vector<long long int>w(n),v(n);
    long long int tmp=0;
    
    for (long long int i = 0; i < n; i++)
    {
        cin >> w[i] >> v[i];
        tmp = max(v[i],tmp);
    }

    long long max_v = tmp*n;
    long long max_w = 10000000000000;
    //dp[i][j]: 品物iまで見たときの価値jでの最小の重さ
    vector<vector<long long int>> dp(n+1,vector<long long int>(max_v+1,0));
    for(int i=0;i<=max_v;i++)dp[0][i]=max_w;
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0; j<=max_v;j++){
            if(v[i]>j){
                dp[i+1][j] = dp[i][j];
            }
            else dp[i+1][j] = lmin(dp[i][j], dp[i][j-v[i]]+w[i]);
        }
    }
    long long int res = 0;
    for(long long int i=0; i<=max_v;i++){
        if(dp[n][i]<=W)res=i;
    }
    cout << res << endl;
      
    return 0;
}

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

int main() {
	int N; string s, t;
	cin >> N >> s >> t;
	int i=0;
	while(s.substr(i, N-i)!=t.substr(0, N-i)) ++i;
	cout << i+N << endl;
	return 0;
}


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

int main() {
	int a, b;
	cin >> a >> b;
	if (b % a==0) {
		cout << a + b << endl;
	}
	else {
		cout << b - a << endl;
	}
}

Measured memory_bytes: 256