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

const int INF = 1<<28;
const int MAXD = 111;
const int MAXT = 31;
int T;
int t[MAXT], F[MAXD];
int dp[MAXD][MAXT];

int main() {
  for(; cin >> T && T; ) {
    for(int i = 0; i < T; ++i) {
      cin >> t[i];
    }
    int N; cin >> N;
    fill(F, F+MAXD, INF);
    for(int i = 0; i < N; ++i) {
      int D, M; cin >> D >> M;
      F[D] = min(F[D], M);
    }
    fill(dp[0], dp[MAXD], INF);
    dp[1][0] = 0;
    for(int i = 1; i+1 < MAXD; ++i) {
      for(int j = 0; j < T; ++j) {
        dp[i+1][1%T] = min(dp[i+1][1%T], dp[i][j] + 1);
        if(t[j] <= F[i]) {
          dp[i+1][(j+1)%T] = min(dp[i+1][(j+1)%T], dp[i][j]);
        }
      }
    }
    cout << *min_element(dp[MAXD-1], dp[MAXD]) << endl;
  }
  return 0;
}

Measured memory_bytes: 1172
#include <bits/stdc++.h>
using namespace std;
#define ll	    long long
#define vi      vector <ll>
#define vii     vector <pair<int,int>>
#define ii      pair<int,int>
#define loop(n)	for(ll i=0;i<n;i++)
#define pb      push_back
const ll mod=1e9+7;
void fast();
int main()
{
    fast();
    int a[3][3];
    int n;
    for(int j=0;j<3;j++){
        for(int k=0;k<3;k++){
            cin>>a[j][k];
        }
    }
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        for(int j=0;j<3;j++){
        for(int k=0;k<3;k++){
            if(a[j][k]==x)
                a[j][k]=-1;
        }
    }
    }
    for(int i=0;i<3;i++){
        if(a[i][0]==-1&&a[i][1]==-1&&a[i][2]==-1)
            return cout<<"Yes\n",0;
    }
    for(int i=0;i<3;i++){
        if(a[0][i]==-1&&a[1][i]==-1&&a[2][i]==-1)
            return cout<<"Yes\n",0;
    }
    if(a[0][0]==-1&&a[1][1]==-1&&a[2][2]==-1)
        return cout<<"Yes\n",0;
    if(a[0][2]==-1&&a[1][1]==-1&&a[2][0]==-1)
        return cout<<"Yes\n",0;
    cout<<"No\n";
}
void fast(){
std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
/*

*/


Measured memory_bytes: 256
/* To Kaise Hain Aaplog*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) (x).begin(), (x).end()

void shuru_krte_hai_bina_kisi_bakchodi_ke()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
const ll m = 998244353;

const ll s = 1e6 + 2;
vector<ll> v[s];
bool vis[s]={0};

void dfs(int s){
    vis[s] = true;
    for(int node : v[s]){
        if(!vis[node]){
            dfs(node);
        }
    }
}
int main()
{
    //shuru_krte_hai_bina_kisi_bakchodi_ke();

/* long long yaad se daal de har jagah*/
#define int long long

    int n,m,ans=0;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i);
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;




signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  string s; cin>>s;
  // string s="bcdefghijklmnopqrstuvwxyz";
  // reverse(all(s));
  // s='a'+s;
  ll n=s.size();
  set<char> se;
  rep(i,n){
    se.insert(s[i]);
  }
  
  rep(i,26){
    char c='a'+i;
    if(!se.count(c)){
      s+=c;
      cout<<s<<endl;
      return 0;
    }
  }
  
  for(ll i=n-1; i>=1; i--){
    se.erase(s[i]);
    if(s[i-1]<s[i]){
      string t=s.substr(0,i-1);
      rep(j,26){
        char c='a'+j;
        if(s[i-1]<c && !se.count(c)){
          t+=c;
          cout<<t<<endl;
          return 0;
        }
      }
    }
  }
  cout<<-1<<endl;
}


Measured memory_bytes: 256
/*
       This sky
       Is lonely and grey
       But every night I feel your gravity waves
       And the world is cold
       But it's beautiful
       I wish you were here now
       I miss your soul
       But you lost your light
       When the darkness called
       I still stand here waiting
       The last to fall
       The last to fall
       The last to fall
       The last to fall
                            */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename X> ostream& operator << (ostream& x,const vector<X>& v){for(ll i=0;i<v.size();++i) x<<v[i]<<" ";return x;}
template <typename X> ostream& operator << (ostream& x,const set<X>& v){for(auto it:v) x<<it<<" ";return x;}
template <typename X, typename Y> ostream& operator << (ostream& x, const pair<X,Y>& v) {x<<v.ff<<" "<<v.ss;return x;}
template <typename T, typename S> ostream& operator << (ostream& os, const unordered_map<T, S>& v) { for (auto it : v) os << it.first << "=>" << it.second << endl; return os; }
struct pair_hash {inline std::size_t operator()(const std::pair<ll, ll> & v) const {return v.first*31+v.second;}};
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC targett("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define fr first
#define sc second
#define tra(it,m) for(auto it=m.begin();it!=m.end();++it)
#define dbg(x) cout<<#x<<" = "<<x<<'\n';
#define fri(i,s,n) for(ll i=s;i<n;i++)
#define mod 1000000007
#define mod2 998244353
#define vct2 vector<vector<ll>>
#define vct vector<ll>
#define pll pair<ll,ll>
#define rz(n) resize(n)
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define arrin(a,n) for(ll i = 0; i < n ; i++){cin>>a[i];}
#define arrout(a,n) for(ll i = 0;i < n; i++){cout<<a[i]<<" ";}
#define ex(s) cout<<s<<endl,exit(0);
#define inf 4e18
#define five 100005;
#define six 1000005;
#define printclock cerr<<"Time"<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
//_______________________________________________________________________________________
int main()
{
       int a[5];
       arrin(a,5);
       fri(i,0,5){
              if(a[i]==0){
                     cout<<i+1<<endl;
                     return 0;
              }
       }
}


Measured memory_bytes: 3592
#include<stdio.h>
int main()
{
    int n, i, a[100], x, y, z, c=0;
    scanf("%d", &n);
    for(i=0; i<n; i++)
    {
        scanf("%d", &a[i]);
    }
    for(i=1; i<n-1; i++)
    {
            x = a[i-1];
            y= a[i];
            z = a[i+1];
            if((x<y && y<z) || (z<y && y<x))
                c++;
    }
    printf("%d\n", c);
    return 0;
}

Measured memory_bytes: 1732
#include<stdio.h>
int main()
{
    int p, q, r, s, n, flag;
    while(scanf("%d",&n)!=EOF)
    {
        flag=0;
        for(p=0 ; p<=9 ; p++)
        {
            for(q=0 ; q<=9 ; q++)
            {
                for(r=0 ; r<=9 ; r++)
                {
                    for(s=0 ; s<=9 ; s++)
                    {
                        if(p+q+r+s == n)
                            flag++;
                    }
                }
            }
        }
        printf("%d\n",flag);
    }
    return 0;
}

Measured memory_bytes: 596
//includes
#include<iostream>
#include<vector>
#include<set>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<iomanip>
#include<numeric>
#include<assert.h>
#include<cstring>
#include<unordered_map>
#include<bitset>

//macros and consts
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(),(a).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define FORE(i,a) for(auto &i : a)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define accm accumulate
#define Fi first
#define Se second
#define INF 1e9
#define llINF (1LL<<60)
#define mINF -1e9
#define mllINF -(1LL<<60)
#define endl "\n"
#define CONT continue
#define BRK break
#define modulo(n, m) (((n)%(m)+(m))%m)

//shorter types
using namespace std;
using ll = long long;
using vi = std::vector<int>;
using vc = std::vector<char>;
using vll = std::vector<long long>;
using vs = std::vector<string>;
using Mi = map<int,int>;
using Mll = map<ll,ll>;
using UMi = unordered_map<int,int>;
using UMll = unordered_map<ll,ll>;
using Pi = pair<int,int>;
using Pll = pair<ll,ll>;
using vPi = vector<Pi>;
using vPll = vector<Pll>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;
using pqgi = priority_queue<int,vector<int>,greater<int>>;
using pqsi = priority_queue<int,vector<int>,less<int>>;
using pqgll = priority_queue<int,vector<int>,greater<int>>;
using pssll = priority_queue<int,vector<int>,less<int>>;
template<class T>
using vec = vector<T>;

//here begins your code
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int N;
  cin >> N;

  int c = (double)N/(double)1.08;

  for(int i = 0 ; i < 10 ; i++){
  	if(long((c + i) * 1.08) == N){
  		cout << (c+i) << endl;
  		return 0;
  	}
  }
  cout << ":(" << endl;

  //check types
  //do not eb if you resize
  //resize before you access by idx
  return 0;
} 

Measured memory_bytes: 888
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;



int main(){
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll ans=0;
    for(ll i=2;i<s.size();i++){
        if(s[i-2]=='A' && s[i-1]=='B' && s[i]=='C')ans++;
    }
    cout << ans << endl;
    return 0;
}



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

using namespace std;

const int N = 1010;

int noNum ;

int v1 [N] , v2[N] ;

int main(){
    scanf("%d",&noNum);

    for ( int i = 1 ; i <= noNum ; i++ ){
        int x ;
        scanf("%d",&x);
        v1 [ i ] = x ;
        v1 [ i ] += v1 [ i - 1 ] ;
    }

    for  ( int i = 1 ; i <= noNum ; i++ ){
        scanf("%d", &v2 [ i ] );
    }

    for ( int i=noNum ; i>0 ; i-- ){
        v2[ i ] += v2 [ i+1 ] ;
    }

    int valMax = 0 ;
    for ( int i=1 ; i<=noNum ; i++ ){
        valMax = max ( valMax , v1 [ i ] + v2[ i ] );
    }

    printf("%d",valMax );
    return 0;
}


Measured memory_bytes: 256
// Problem : B - ... (Triple Dots)
// Contest : AtCoder - AtCoder Beginner Contest 168
// URL : https://atcoder.jp/contests/abc168/tasks/abc168_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//mst,pq,mp,st,q
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) begin(x),end(x)

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

signed main()
{
    io
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
		int k;
		cin>>k;
		string s;
		cin>>s;
		int n = s.size();
		if(n>k)
		{
			cout<<s.substr(0,k)<<"...";
		}
		else
		cout<<s;    	
    }
    return 0;
}


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

class UnionFind {
public:
    vector < int > par; // 各元の親を表す配列
    vector < int > siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1) {
        for (int i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(int sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1);
        for (int i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    int root(int x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(int x, int y) { // 連結判定
        return root(x) == root(y);
    }

    int size(int x) { // 素集合のサイズ
        return siz[root(x)];
    }
};
int main() {
  int n,m;
  cin>>n>>m;
  UnionFind uf(n);
  int ans=0;
  rep(i,m){
    int a,b;
    cin>>a>>b;
    if(!(uf.issame(a,b))){
      uf.merge(a,b);
    }
  }
  for(int i=0;i<n;i++) ans=max(ans,uf.size(i));
  cout<<ans<<endl;
}

Measured memory_bytes: 4836
#include <iostream>
#include <vector>
#include <string>
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < n; i++)
using namespace std;

int main(){
  int a;
  string s;
  cin >> a >> s;
  if (a >= 3200) cout << s << endl;
  else cout << "red" << endl;
  
  return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
int main()
{
  int m[200000],n,i;
  int max,min;

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

 min = m[0];
 max = m[1]-m[0];
 for(i=1;i<n;i++){

if(max<m[i]-min) 
 max=m[i]-min;

if(min > m[i])
 min=m[i];

}
printf("%d\n",max);

return 0;
}

Measured memory_bytes: 2532
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int H, W, i1, i2;
    
    
    while (1) {
    
        cin >> H >> W;
        if (H == 0 && W == 0) break;
            
        for (i1=0; i1<H; i1++) {
            
            for (i2=0; i2<W; i2++){
                cout << "#";
            }
            
            cout << "\n";
        }
        
        cout << endl;
        
    }
    
}

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

vector<bool> seen, calculated;
vector<vector<int>> graph;
vector<int> dp;

int dfs(int v){
    if(seen[v]){
        return (calculated[v] ? dp[v] : -1);
    }
    seen[v] = true;
    for(auto e : graph[v]){
        int res = dfs(e);
        if(res == -1) return -1;
        dp[v] = max(dp[v], res + 1);
    }
    calculated[v] = true;
    return dp[v];
}

int toId(int i, int j){
    if(i < j) return toId(j, i);
    return (i*(i-1) / 2 + j + 1);
}

int main() {
    int n;
    cin >> n;
    graph.resize(n * (n - 1) / 2 + 1);
    for(int i = 0; i < n; i++){
        int a = 0;
        for(int j = 0; j < n - 1; j++){
            int b;
            cin >> b, b = toId(i, b-1);
            graph[a].push_back(b);
            a = b;
        }
    }

    seen.resize(n * (n - 1) / 2 + 1);
    calculated.resize(n * (n - 1) / 2 + 1);
    dp.resize(n * (n - 1) / 2 + 1);
    cout << dfs(0) << endl;
    return 0;
}

Measured memory_bytes: 29696
import itertools
N = str(input())
P = ''.join(list(map(str, input().split())))
Q = ''.join(list(map(str, input().split())))
l=[]
for v in itertools.permutations(P):
    l.append(''.join(v))
print(abs(sorted(l).index(P)-sorted(l).index(Q)))

Measured memory_bytes: 6424
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
using namespace std;

using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1e9+5;
constexpr long long INFLL = 1LL<<62;
constexpr double eps = (1e-9);

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

  int n, t;
  cin >> n >> t;
  vector<pair<int, int>> dish;
  rep(i, n) {
    int a, b;
    cin >> a >> b;
    dish.push_back({a, b});
  }
  sort(ALL(dish));

  // i 番目までの料理を t-1 秒までに完食した場合の美味しさの最大値
  vector<vector<int>> dp(n, vector<int>(t, 0));
  for (int j = dish[0].first; j < t; j++) dp[0][j] = dish[0].second;  // 0 番目の料理だけ食べる

  for (int i = 1; i < n; i++) {
    int a = dish[i].first;
    int b = dish[i].second;
    for (int j = 0; j < t; j++) {
      if (j - a >= 0) dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);
      else dp[i][j] = dp[i-1][j];
    }
  }

  int ans = dish[0].second;
  for (int i = 1; i < n; i++) {
    chmax(ans, dp[i-1][t-1] + dish[i].second);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 38496
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1000000;
int cnt[3], b[3], c[3];
void get() {
	if( cnt[0] >= cnt[1] && cnt[1] >= cnt[2] )
		c[b[0] = 2] = 0, c[b[1] = 1] = 1, c[b[2] = 0] = 2;
	else if( cnt[0] >= cnt[2] && cnt[2] >= cnt[1] )
		c[b[0] = 2] = 0, c[b[2] = 1] = 2, c[b[1] = 0] = 1;
	else if( cnt[1] >= cnt[0] && cnt[0] >= cnt[2] )
		c[b[1] = 2] = 1, c[b[0] = 1] = 0, c[b[2] = 0] = 2;
	else if( cnt[1] >= cnt[2] && cnt[2] >= cnt[0] )
		c[b[1] = 2] = 1, c[b[2] = 1] = 2, c[b[0] = 0] = 0;
	else if( cnt[2] >= cnt[0] && cnt[0] >= cnt[1] )
		c[b[2] = 2] = 2, c[b[0] = 1] = 0, c[b[1] = 0] = 1;
	else if( cnt[2] >= cnt[1] && cnt[1] >= cnt[0] )
		c[b[2] = 2] = 2, c[b[1] = 1] = 1, c[b[0] = 0] = 0;
}
int lst[MAXN + 5], nxt[MAXN + 5];
int a[MAXN + 5], n;
void erase(int x) {
	lst[nxt[x]] = lst[x], nxt[lst[x]] = nxt[x];
	cnt[a[x]]--;
}
char s[MAXN + 5];
vector<int>v;
int main() {
	scanf("%s", s + 1), n = strlen(s + 1);
	for(int i=0;i<=n+1;i++)
		lst[i] = i - 1, nxt[i] = i + 1;
	a[0] = a[n + 1] = -1;
	for(int i=1;i<=n;i++) {
		cnt[a[i] = s[i] - 'A']++;
		if( a[i] == a[i-1] ) erase(i);
	}
	get();
	for(int i=nxt[0];i!=n+1;i=nxt[i])
		if( a[i] == c[2] && a[lst[i]] != a[nxt[i]] )
			v.push_back(i);
	for(int i=0;i<v.size()&&cnt[c[2]]!=cnt[c[1]];i++)
		erase(v[i]);
	v.clear();
	for(int i=nxt[0];i!=n+1;i=nxt[i])
		if( a[i] == c[2] && a[lst[i]] == c[0] && a[nxt[i]] == c[0] )
			v.push_back(i);
	for(int i=0;i<v.size()&&cnt[c[2]]!=cnt[c[1]];i++)
		erase(v[i]), erase(nxt[v[i]]);
	v.clear();
	for(int i=nxt[0];i!=n+1;i=nxt[i])
		if( a[i] == c[2] && a[nxt[i]] == c[1] )
			v.push_back(i);
	for(int i=0;i<v.size()&&cnt[c[0]]!=cnt[c[1]];i++)
		if( a[lst[v[i]]] != c[0] || a[nxt[nxt[v[i]]]] != c[0] )
			erase(v[i]), erase(nxt[v[i]]);
	v.clear();
	for(int i=nxt[0];i!=n+1;i=nxt[i])
		if( a[i] == c[2] && a[lst[i]] == c[1] )
			v.push_back(i);
	for(int i=0;i<v.size()&&cnt[c[0]]!=cnt[c[1]];i++)
		if( a[nxt[v[i]]] != c[0] || a[lst[lst[v[i]]]] != c[0] )
			erase(v[i]), erase(lst[v[i]]);
	v.clear();
	if( cnt[0] == cnt[1] && cnt[0] == cnt[2] ) {
		for(int i=nxt[0];i!=n+1;i=nxt[i])
			putchar(a[i] + 'A');
	}
}

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

int main() {
    int N;
    cin>>N;
    vector<long> A;
    long tmp;
    for(int i=0;i<N;++i){
        cin>>tmp;
        A.push_back(tmp);
    }
    sort(A.begin(), A.end());
    bool ans = true;
    for(int i=1;i<N;++i){
        if(A[i]==A[i-1])ans = false;
    }
    if(ans)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


Measured memory_bytes: 2420
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int H,W,K; cin >> H >> W >> K;
    vector<vector<char> > c(H,vector<char>(W));
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> c[i][j];
        }
    }
    int out=0;
    for(int i=0;i<(1<<H);i++){
        for(int j=0;j<(1<<W);j++){
            vector<vector<char>> cc=c;
            for(int x=0;x<H;x++){
                if(i & (1<<x)){
                    for(int a=0;a<W;a++){
                        cc[x][a] = '*';
                    }
                }
            }
            for(int y=0;y<W;y++){
                if(j & (1<<y)){
                    for(int a=0;a<H;a++){
                        cc[a][y] = '*';
                    }
                }
            }
            int cnt=0;
            for(int x=0;x<H;x++){
                for(int y=0;y<W;y++){
                    if(cc[x][y]=='#') cnt++;
                }
            }
            if(cnt==K) out++;
        }
    }
    cout << out << endl;
    return 0;
}


Measured memory_bytes: 3588
X = int(input())

dp = [0] * 110000
dp[100] = 1
dp[101] = 1
dp[102] = 1
dp[103] = 1
dp[104] = 1
dp[105] = 1

for i in range(X + 1):
    dp[i + 100] = max(dp[i], dp[i + 100])
    dp[i + 101] = max(dp[i], dp[i + 101])
    dp[i + 102] = max(dp[i], dp[i + 102])
    dp[i + 103] = max(dp[i], dp[i + 103])
    dp[i + 104] = max(dp[i], dp[i + 104])
    dp[i + 105] = max(dp[i], dp[i + 105])

print(dp[X])

Measured memory_bytes: 9932
using System;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            var nm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            long ans = 1;
            for (int i = 1; i <= nm[0]; i++)
            {
                ans *= i;
                ans %= 1000000007;
            }
            for (int i = 1; i <= nm[1]; i++)
            {
                ans *= i;
                ans %= 1000000007;
            }
            Console.WriteLine(Math.Abs(nm[0] - nm[1]) <= 1 ? nm[0] == nm[1] ? ans * 2 % 1000000007 : ans : 0);
        }
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) {
    cout << "Bad\n";
  } else {
    cout << "Good\n";
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int main() {
  int N;
  cin >> N;
  int t = 0, x = 0, y = 0;
  REP(i, N) {
    int t1, x1, y1;
    cin >> t1 >> x1 >> y1;
    if((t1-t)>=abs(x1-x)+abs(y1-y)&&(t1-t)%2==(abs(x1-x)+abs(y1-y))%2){

    }else{
      puts("No");
      return 0;
    }
    t = t1, x = x1, y = y1;
  }
  puts("Yes");
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
int main(){
    int q;
    while(cin>>q && q){
        vector<string> A(q);
        vector<int> B(q);
        int mm=0;
        REP(i,q){
            string s;
            cin >> s;
            A[i]=s;
            B[i]= s.find_last_of(".")+1;
            mm =max(mm,B[i]);
        }
        map<int,int> S;
        map<int,int> T;
        REP(i,q){
            T[B[i]]=i;
        }
        REP(i,q){
            S[B[q-1-i]]=q-1-i;
        }
        int n=1;
        while(mm>=n){
            int f=-1;
            REP(i,q){
                if(n>B[i]){
                    
                    if(f!=-1){
                        for(int j=f+1; j<i; j++){
                            A[j][n-1]=' ';
                        }
                    }
                    f=-1;
                    continue;
                    
                } else if(n==B[i]) {
                    A[i][n-1]='+';
                    f=i;
                } else{
                    if(S[n]<=i && i<=T[n]) A[i][n-1]='|';
                    else A[i][n-1]=' ';
                }
            }
            n++;
        }
        REP(i,q){
            cout << A[i] << "\n";
        }
    }  
}


Measured memory_bytes: 3856
import java.io.BufferedReader;

import java.io.InputStreamReader;
class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));// ??\????????????????????????
            String line = br.readLine();
            
            System.out.println((long)getCubeOf(line));

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static double getCubeOf(String line) {
    	long x = Long.parseLong(line);
    	
    	return (long)Math.pow(x, 3);
    }
}

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

int main()
{

    int a,b,c,p,q,r,A,B;

    cin>>a;

    A=a/100;
    B=a%100;

  if((B>0 && B<13) && (A>0 && A<13))
    {
        cout << "AMBIGUOUS\n";
    }
    else if(A>0 && A<13)
    {
        cout << "MMYY\n";
    }
    else if(B>0 && B<13)
    {
        cout << "YYMM\n";
    }
    else
    {
        cout << "NA\n";
    }

    return 0;
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/abc127/tasks/abc127_e

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(_i, n) printf("%d%c", a[_i], _i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(_i, n) REP(_j, m) printf("%d%c", a[_i][_j], _j + 1 == m ? '\n' : ' '); puts("")

//------------------------------------------------------------------------------
ll mod_pow(ll x, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) {
      res = res * x % mod;
    }
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}

ll mod_inverse(ll x, ll mod) {
  return mod_pow(x, mod - 2, mod);
}

ll mod_comb(ll n, ll k, ll mod) {
  if (n < 0 || k < 0 || n < k) return 0;
  ll a = 1, b = 1;
  while(k > 0) {
    a = a * n-- % mod;
    b = b * k-- % mod;
  }
  return a * mod_inverse(b, mod) % mod;
}

//------------------------------------------------------------------------------

const int M_MAX = 2*1e5;
const int MOD = 1e9+7;

int N, M, K;

void solve() {
  ll x = 1;
  ll y = 1;
  FOR(i, -1, 1) {
    x = x * (M + i) % MOD;
    y = y * (N + i) % MOD;
  }
  REP(i, 2) {
    x = x * N % MOD;
    y = y * M % MOD;
  }
  ll ans = (x + y) % MOD;
  ans = ans * mod_inverse(6, MOD) % MOD;
  ans = ans * mod_comb(N * M - 2, K - 2, MOD) % MOD;
  printf("%lld\n", ans);
}

void input() {
  scanf("%d%d%d", &N, &M, &K);
}

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


Measured memory_bytes: 384
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
using namespace std;


const long long modn = 1e9+7;
long long F[100000+20];
int main ()
{
    long long temp=1;
    F[0]=1;
    for(long long i=1; i<=100000; i++){
        temp=(temp*i)%modn;
        F[i]=temp;
    }
#undef SONG
    #ifdef SONG
    for(int i=1; i<=100000; i++)
        printf("%d %lld\n",i,F[i]);
#endif
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF){

        if(abs(n-m)>1){
            printf("0\n");
            continue;
        }
        printf("%lld\n",((n==m)?2LL:1LL)*F[n]*F[m]%modn);
    }
    return 0;
}



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

int W, H;

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

void solve(int cx, int cy, vector<vector<int>>& v) {
    v[cx][cy] = 0;
    for(int i=0; i<8; ++i) {
        int nx = cx + dx[i];
        int ny = cy + dy[i];
        if(nx >= 0 && nx < W && ny >= 0 && ny < H && v[nx][ny] == 1) {
            solve(nx, ny, v);
        }
    }
}


int main() {
    while(cin >> W >> H, W) {
        vector<vector<int>> v(W, vector<int>(H));
        for(int i=0; i<H; ++i) {
            for(int j=0; j<W; ++j) {
                cin >> v[j][i]; // 0: sea, 1:island
            }
        }
        int ans=0;
        for(int i=0; i<W; ++i) {
            for(int j=0; j<H; ++j) {
                if(v[i][j] == 1) {
                    solve(i, j, v);
                    ++ans;
                }
            }
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3188
def mapint_inp():
    return map(int, input().split())

def intinp():
    return int(input())

N = input()
l = len(N)

if N[-1] in ["2","4","5","7","9"]:
    print("hon")
elif N[-1] in ["0","1","6","8"]:
    print("pon")
else:
    print("bon")

Measured memory_bytes: 9112
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
const int INF = +100100100;
typedef pair<ll,ll> P;
const ll MO = 1000000007;

int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n)cin>>a[i];
    sort(a.begin(),a.end());
    stack<P> st;
    ll pre = a[0];
    rrep(i,n-1){
        if(pre==a[i]){
            st.emplace(pre,a[i]);
            pre=0;
        }
        else pre = a[i];
    }
    ll x,y;
    if(st.size()>=2){
        x = st.top().first;st.pop();
        y = st.top().first;st.pop();        
    }else {
        x = 0; y = 0;
    }

    cout << x * y << endl;
    return 0;

}

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

zero_count = 0
minus_count = 0
s = 0
min_num = abs(a[0])

for i in range(n):
    if a[i] < 0:
        minus_count += 1
    elif a[i] == 0:
        zero_count += 1
    s += abs(a[i])
    min_num = min(min_num, abs(a[i]))

if minus_count % 2 == 0:
    print(s)
else:
    if zero_count == 0:
        print(s - 2 * min_num)
    else:
        print(s)


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

int main() {
  bool ans=false;
  int64_t A, B, V, W, T;
  cin >> A >> V;
  cin >> B >> W;
  cin >> T;
  if (W < V && A > B)
  {
      if ((A-B) <= T*(V-W))
      {
          ans = true;
      }
      
  }

  if (W < V && A < B)
  {
      if ((B-A) <= T*(V-W))
      {
          ans = true;
      }
  }
  
  
  if (ans == true)
  {
    cout << "YES" << endl;
  }else
  {
    cout << "NO" << endl;
  }
  
  return 0;

}

Measured memory_bytes: 3632
#include <cctype>
#include <stdio.h>
#include <iostream>
using namespace std;


int main()
{
	char ch;
	while(1){
		scanf("%c",&ch);
		if(islower(ch)){
			printf("%c",toupper(ch));
		}else if(isupper(ch)){
			printf("%c",tolower(ch));
		}else{
			printf("%c",ch);
		}
		if(ch == '\n') break;
	}
	return 0;
}

Measured memory_bytes: 3120
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#define repp(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define repm(i,a,b) for(int i=(int)a;i>(int)b;--i)
using ll=long long;
static const ll mod = 1e9 + 7;
static const ll INF = 1LL << 50;
using namespace std;

int main() {
	ll n;
	ll sum = 0;
	cin >> n;
	vector<string>s(n);
	vector<ll>ans(5, 0);
	repp(i, 0, n) {
		cin >> s[i];
		if (s[i][0] == 'A')++ans[0];
		else if (s[i][0] == 'C')++ans[1];
		else if (s[i][0] == 'H')++ans[2];
		else if (s[i][0] == 'M')++ans[3];
		else if (s[i][0] == 'R')++ans[4];
	}
	repp(i, 0, 3)repp(j, i + 1, 4) repp(k, j + 1, 5)sum += ans[i] * ans[j] * ans[k];
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 6144
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

int main(){
    int N, M;
    cin >> N >>M;
    vector<long> H(N);
    for (int i = 0; i < N; i++){
        cin >> H[i];
    }
    int a, b;
    map<int, set<int>> link;
    for (int i = 0; i < M; i++){
        cin >> a >> b;
        link[a].insert(H[b-1]);
        link[b].insert(H[a-1]);
    }
    int ans = 0;
    for (int i = 1; i <= N; i++){
        if (link[i].size() == 0) {
            ans++;
        }
        else {
            int max_h = *max_element(link[i].begin(), link[i].end());
            if (H[i-1] > max_h) ans++;
        }
    }
    cout << ans << endl;
}




Measured memory_bytes: 22796
#include<iostream>
#include<algorithm>
using namespace std;
static const int M = 200000;

int main(){
int R[M],n;

cin>>n;
for(int i=0;i<n;i++)cin>>R[i];

int maxv=-2000000000;
int minv=R[0];

for(int i=1;i<n;i++ ){
maxv=max(maxv,R[i]-minv);
minv=min(minv,R[i]);
}

cout<<maxv<<endl;

return 0;
}

Measured memory_bytes: 3888
n,m = (int(i) for i in input().split())
a = [[int(i) for i in input().split()] for i in range(n)]
b,x,num = [0]*n,[0]*(m+1),m
for i in range(n): x[a[i][0]]+=1
z = max(x)
ans,x[x.index(z)] = z,-1
while ans>(n-1)//num+1:
	for i in range(n):
		if x[a[i][b[i]]]==-1:
			while x[a[i][b[i]]]==-1: b[i]+=1
			x[a[i][b[i]]]+=1
	z = max(x)
	ans,x[x.index(z)],num = min(ans,z),-1,num-1
print(ans)

Measured memory_bytes: 4260
N = int(input())
A = [int(i) for i in input().split()]
ans = 0
check = [0]*30
for i in range(1, 31):
    check[i-1] = 2**i

for i in A:
    if i % 2 == 0:
        j = 0
        while check[j] <= i:
            if i % check[j] == 0:
                add = check[j]
            else:
                break
                
            j += 1
        ans += j
        
print(ans)

Measured memory_bytes: 4148
# include <bits/stdc++.h>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
#define Array vec<ll>
using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

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

ll lcm(ll a,ll b)
{
   return a/gcd(a,b)*b;
}

//累乗だってさ
ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}
//逆元だってさ
ll modinv(ll a,ll mod1) {
    return modpow(a, mod1 - 2, mod1);
}

const ll MAX = 1000000;
const ll MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


void solve(){
    
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n,m;
    cin>>n>>m;
    cout<<modpow(n, m, mod)<<endl;
    return 0;
}



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

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

using namespace std;

typedef pair<int,int> ii;
const int MAX_V = 101;
const int IINF = INT_MAX;
struct Edge { int dst,weight,hour,comp; };
struct Data {
  int cur,weight,hour,bitmask;
  bool operator < ( const Data &data ) const {
    if( weight != data.weight ) return weight > data.weight;
    return hour   > data.hour;
  }
};
int V,E,H,K,S,T,P;
vector<Edge> G[MAX_V],G2[MAX_V];
int mindist[MAX_V][27],dp[1<<8];
;
ii pass[300];

void set_up(){
  rep(i,(1<<K)) dp[i] = IINF;
  dp[0] = 0;
  rep(i,(1<<K)) if( dp[i] != IINF ) {
    rep(j,P) {
      int bit = i | pass[j].second;
      assert(bit<(1<<K));
      dp[bit] = min(dp[bit],dp[i]+pass[j].first);
    }
  }
}

int dijkstra(int bit){
  rep(i,V) G2[i].clear();
  rep(i,V){
    rep(j,G[i].size()){
      Edge edge = G[i][j];
      if( ( bit >> edge.comp ) & 1 ) edge.weight = 0;
      G2[i].push_back(edge);
    }
  }

  priority_queue<Data> Q;
  rep(i,V) rep(k,H+1) mindist[i][k] = IINF;
  Q.push((Data){S,dp[bit],0,0});
  mindist[S][0] = 0;
  while( !Q.empty() ){
    Data data = Q.top(); Q.pop();
    if( data.cur == T ) return data.weight;
    rep(i,G2[data.cur].size()){
      int next = G2[data.cur][i].dst;
      int nhour = data.hour + G2[data.cur][i].hour;
      if( nhour > H ) continue;
      if( mindist[next][nhour] > data.weight + G2[data.cur][i].weight ) {
	mindist[next][nhour] = data.weight + G2[data.cur][i].weight;
	Q.push((Data){next,mindist[next][nhour],nhour,data.bitmask});
      }
    }
  }
  return -1;
}

void compute(){
  set_up();
  int mini = IINF;
  rep(i,(1<<K)) if( dp[i] != IINF ) mini = min(mini,dijkstra(i));
  cout << mini << endl;
}

int main(){
  while( cin >> V >> E >> H >> K, V|E|H|K ) {

    rep(i,V) { G[i].clear(); }

    int a,b,c,h,r;
    rep(i,E) {
      cin >> a >> b >> c >> h >> r;
      --a, --b, --r;
      G[a].push_back((Edge){b,c,h,r});
      G[b].push_back((Edge){a,c,h,r});
    }
    
    cin >> S >> T;
    --S, --T;
    

    cin >> P;    

    int l,d,k;
    rep(i,P){
      cin >> l >> d;
      pass[i].first = d;
      pass[i].second = 0;
      rep(j,l) {
	cin >> k;
	assert( 1 <= k && k <= K );
	--k;
	pass[i].second |= (1<<k);
      }
    }


    compute();
    
  }
  return 0;
}

Measured memory_bytes: 1452
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
std::ostream& operator<<(std::ostream& os, __int128 T)
{
    if (T<0) os<<"-";if (T>=10 ) os<<T/10;if (T<=-10) os<<(-(T/10));
    return os<<( (int) (T%10) >0 ? (int) (T%10) : -(int) (T%10) ) ;
}
int n,m;
char s[2020][2020];
int sum[4][2020][2020];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]=='#')continue;
			sum[0][i][j]=sum[0][i][j-1]+1;
		}
	for(int i=1;i<=n;i++)
		for(int j=m;j>=1;j--)
		{
			if(s[i][j]=='#')continue;
			sum[1][i][j]=sum[1][i][j+1]+1;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]=='#')continue;
			sum[2][i][j]=sum[2][i-1][j]+1;
		}
	for(int i=n;i>=1;i--)
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]=='#')continue;
			sum[3][i][j]=sum[3][i+1][j]+1;
		}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]=='#')continue;
		//	cout<<i<<" "<<j<<" "<<sum[0][i][j]<<" "<<sum[1][i][j]<<" "<<sum[2][i][j]<<" "<<sum[3][i][j]<<endl;
			ans=max(ans,sum[0][i][j]+sum[1][i][j]+sum[2][i][j]+sum[3][i][j]-3);
		}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 67968
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define cps CLOCKS_PER_SEC
#define tests(t) int t; cin >> t; while(t--)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define eb emplace_back
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define fi first
#define se second
#define bitcount(x) __builtin_popcount(x)
#define bit(x) (1LL << x)
#define PI acos(-1.0)
#define EPS 1e-9

#define mod 1000000007
#define maxn 200005

using namespace std;

using namespace __gnu_pbds;
template<class key, class cmp = std::less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
///All indexing is 0-based
///methods: find_by_order(k); & order_of_key(k);
///To make it an ordered_multiset, use pairs of (value, time_of_insertion)
///to distinguish values which are similar

typedef long long ll;
typedef double ld;
typedef pair<ll, ll> par;


int main()
{
    #ifdef acm
    freopen("a.in","r",stdin);
    #endif // acm
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int a,b;
    cin >> b >> a;
    if(a >= b)
        cout << "unsafe\n";
    else
        cout << "safe\n";



}


Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int[] a = new int[3];
		for(int i=0;i<3;i++){
			a[i] = scanner.nextInt();
		}
		int count5 = 0;
		int count7 = 0;
		for(int i=0;i<3;i++){
			if(a[i] == 5){
				count5++;
			}else if(a[i] == 7){
				count7++;
			}
		}
		if(count5 == 2 && count7 == 1){
			System.out.println("YES");
		}else{
			System.out.println("NO");
		}
	}

}


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

static int minElement(const int* array, size_t size)
{
    size_t i;
    int min,num;

    assert(array != NULL);
    assert(size >= 1);

    min = array[0];
    for (i = 1; i < size; ++i) {
        if (min > array[i]) {
            min = array[i];
            num = i;
        }
    }

    return num;
}

int main(){
    int n, l;
    cin >> n >> l;

    int sum = 0;
    int taste[200], taste2[200];
    int h, ans;
    for (int i = 1; i <= n; i++) {
        sum += (l+i-1);
        taste[i-1] = l+i-1;
    }
   
    for (int i = 0; i < n; i++) {
        taste2[i] = abs(taste[i]);
    }

    ans = sum - (l+minElement(taste2, n));
    cout << ans << endl;
}

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

int main(void){
    int K,A,B;
    cin >> K >> A >> B;
    bool x = false;
    for(int i=A;i<=B;i++){
        if(i%K==0){
            x = true;
            break;
        }
    }
    if(x)
        cout << "OK"<<endl;
    else
        cout << "NG"<<endl;
    
    return 0;
}





Measured memory_bytes: 3636
from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import shortest_path, floyd_warshall
import numpy as np

import sys
def input():
	return sys.stdin.readline().strip()

N, M, L = list(map(int, input().split()))

graph = np.full((N, N), np.inf)
for i in range(M):
	A, B, C = list(map(int, input().split()))
	graph[A - 1, B - 1] = C
	graph[B - 1, A - 1] = C

graph = csr_matrix(graph)
dist = floyd_warshall(graph, directed=False)
graph2 = np.full((N, N), np.inf)
for i in range(N):
	for j in range(N):
		if dist[i, j] <= L:
			graph2[i, j] = 1
graph2 = csr_matrix(graph2)
num = shortest_path(graph2, directed=False)


Q = int(input())
for q in range(Q):
	s, t = list(map(int, input().split()))
	if num[s - 1][t - 1] < 10000000:
		print(int(num[s - 1][t - 1] - 1))
	else:
		print(-1)







Measured memory_bytes: 21220
#include <stdio.h>

int main(){
	int num[5];
	int i,j;
	int key;
	int mini = 0;
	
	scanf("%d %d %d %d %d",&num[0],&num[1],&num[2],&num[3],&num[4]);

	for(i = 0;i < 5 ;i++){
		key = num[i];
		mini = i;
		for(j = i;j < 5;j++){
			if(key > num[j]){
				key = num[j];
				mini = j;
			}
		}
		num[mini] = num[i];
		num[i] = key;
	}
	
	for(i = 0;i < 5;i++){
		if(i < 4){
			printf("%d ",num[4-i]);
		}else{
			printf("%d\n",num[0]);
		}
	}
	
	return 0;
}
			

Measured memory_bytes: 1028
//#include<iostream>
#include<cstring>
#include<cstdio>
//#include<math.h>
//#include<set>
//#include<queue>
//#include<bitset>
//#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;

#define LL long long
int qread()
{
	char c; int s=0,f=1; while ((c=getchar())<'0' || c>'9') (c=='-') && (f=-1);
	do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s*f;
}

//Pay attention to '-' , LL and double of qread!!!!

int n,K,m;
#define maxn 10000011
LL a[maxn]; int la=0;
LL ten[20];

int calc(LL x)
{
	int ans=0;
	while (x)
	{
		ans+=x%10;
		x/=10;
	}
	return ans;
}

bool check(LL x)
{
	LL ans=x; int cnt=0;
	while (ans%10==9) ans/=10,cnt++;
	if (ans==0) return 1;
	return calc(x+ten[cnt])*x<=calc(x)*(x+ten[cnt]);
}

int main()
{
//	freopen("out.txt","w",stdout);
	n=qread();
	ten[0]=1; for (int i=1;i<=16;i++) ten[i]=ten[i-1]*10;
	for (int i=1;i<=9;i++) a[++la]=i;
	for (int i=1;i<=14;i++)
	{
		LL b=ten[i]-1;
		for (int j=1;;j++)
		{
			LL c=b+j*ten[i];
			if (c>1e15) break;
			if (check(c)) a[++la]=c;
			else break;
		}
	}
	sort(a+1,a+1+la); la=unique(a+1,a+1+la)-a-1;
	for (int i=1;i<=n;i++) printf("%lld\n",a[i]);
	return 0;
}

Measured memory_bytes: 128