akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<queue>
#include<cassert>
#include<cstdio>

using namespace std;

typedef pair<int,int> P;
const int MAX = 21;
const int TM = 11;
const int INF = (1<<25);

char F[MAX][MAX];
int T[(1<<TM)][MAX][MAX];
int w,h,sx,sy;
vector<P> Trash;


struct State{
  int x,y,t,come;
  
  State(){}
  State(int x, int y, int t, int c):x(x),y(y),t(t),come(c){}
  bool operator < (const State& s) const { return t > s.t;}

};

void print(){
  for(int i = 0; i < (1<<Trash.size()); i++){
    for(int y = 0; y < h; y++){
      for(int x = 0; x < w; x++)
	if(T[i][y][x] != INF){
	  printf("%3d",T[i][y][x]);
	}else {cout << " X ";}
      cout << endl;
    }
    cout << endl;
  }
}

bool isInside(int x, int y){ return 0<=x&&x<w&&0<=y&&y<h;}

void init(){

  fill(T[0][0],T[0][0]+(1<<TM)*MAX*MAX,INF);
  Trash.clear();
}

void input(){
  for(int i = 0; i < h; i++)
    for(int j = 0; j < w; j++){
      cin >> F[i][j];
      if(F[i][j] == 'o'){
	sx = j;
	sy = i;
      }
      if(F[i][j] == '*') Trash.push_back(P(j,i));

    }
}

int getTrashNum(P p){
  for(int i = 0; i < Trash.size(); i++)
    if(Trash[i] == p) return i;
  
  cerr << "not found" << endl;
  return -1;
}
void solve(){

  priority_queue<State> Q;
  Q.push(State(sx,sy,0,0));
  T[0][sy][sx] = 0;

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

  while(!Q.empty()){
    State now = Q.top();
    Q.pop();

    if(T[now.come][now.y][now.x] < now.t) continue;
    
    for(int i = 0; i < 4; i++){
      State nex = now;
      nex.x += dx[i];
      nex.y += dy[i];
      nex.t++;

      if(!isInside(nex.x,nex.y)) continue;
      if(F[nex.y][nex.x] == 'x') continue;


      if(F[nex.y][nex.x] == '*'){
	int Tnum = getTrashNum(P(nex.x, nex.y));
	nex.come = (nex.come|(1<<Tnum));
      }

      
      if(T[nex.come][nex.y][nex.x] > nex.t){
	T[nex.come][nex.y][nex.x] = nex.t;
	Q.push(nex);
      }
    }
  }

  int ans = INF;

  // print();

  if(Trash.size() == 0) ans = 0;

   for(int i = 0; i < Trash.size(); i++)
     ans = min(ans,T[(1<<Trash.size())-1][Trash[i].second][Trash[i].first]);


  if(ans == INF) cout << "-1" << endl;
  else cout << ans << endl;
 
}
  
int main(){

  while(cin >> w >> h && w+h){
    init();
    input();
    solve();
  }
  return 0;
}

Measured memory_bytes: 4856
import heapq
import sys

input = sys.stdin.readline

def set_heapq(que, edge, used, v, add_dist=0):
    '''
    確定地点vからつながる辺を全てqueに設定し、返却する

    Parameters
    que : heapque(touple or list)
        辺を管理するキュー (距離、次の行き先)のtopuleまたはlistにて管理
    edge : 2d list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    v : int
        グラフ上のノード ダイクストラでは確定したノードがvにあたる
    add_dist : int
        確定した地点に足し合わせる距離 スタート地点以外では何かしらの値が追加されることになる

    Returns
    que : heapque(touple or list)
        引数queにvからつながる辺を追加したキュー
    '''
    for a,b in edge[v]:
        if used[b]:
            heapq.heappush(que,(a+add_dist,b))
    return que

def dijkstra_heap(s, edge):
    '''
    ダイクストラ法でsで指定された地点からの全てのノードまでの最短距離を返却
    
    Parameters
    s : int
        スタート地点
    edge : 2d list
        全ての辺を格納する二次元のリスト
    
    Returns
    d : list
        スタート地点から全てのノードの最短距離のリスト
    '''
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s], used[s] = 0, False
    edgelist = set_heapq([], edge, used, s)
    while len(edgelist):
        a, b = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[b]:
            continue
        d[b], used[b] = a, False
        # 確定地点vからつながる辺を全て優先度付きキューに入れる
        edgelist = set_heapq(edgelist, edge, used, b, d[b])
    return d
#########################

n,w = map(int,input().split())
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    edge[i+1].append([0, i])

for i in range(w):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
ret = dijkstra_heap(0, edge)[-1]
if ret == float("inf"):
    ret = -1
print(ret)



Measured memory_bytes: 66384
// 2020-07-24 20:55:28
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

ll n;
bool ok(vector<ll> a, vector<ll>& f, ll k, ll x) {
  rep(i, n) {
    ll q = x / f[i];
    if(a[i] > q) {
      ll d = min(a[i] - q, k);
      a[i] -= d;
      k -= d;
    }
    if(a[i] * f[i] > x) return false;
  }
  return true;
}
void answer() {
  ll k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  vector<ll> f(n);
  rep(i, n) cin >> f[i];
  sort(a.begin(), a.end());
  sort(f.rbegin(), f.rend());
  ll l = -1, r = 1e18;
  while(l + 1 < r) {
    ll m = (l + r) / 2;
    if(ok(a, f, k, m)) {
      r = m;
    } else {
      l = m;
    }
  }
  cout << r << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

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

int main() {
  int n; cin >> n;
  ll sum = 0;
  for (int i=1; i<n+1; ++i) {
    if (i%3 == 0 || i%5 == 0) continue;
    sum += i;
  }
  
  cout << sum << endl;
  
  return 0;
} 



Measured memory_bytes: 3636
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX =2000007;
const int MOD = 1000000007;
//

     signed main(){
   int n,k;
   cin>>n>>k;
   int x,ans=0;
   for(int i=0;i<n;i++){
       cin>>x;
       ans+=min(x,k-x);
   }
   cout<<2*ans<<endl;

     }


 


 






    





      

        


Measured memory_bytes: 3600
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main(){
    int n,A[1000];
    while(1){
        cin >> n;
        if (n == 0) break;
        for (int i = 0;i < n;i++) cin >> A[i];
        int sum = 0;
        for (int i = 0;i < n;i++) sum += A[i];
        double ave = 1.0*sum/n;
        double disp = 0.0;
        for (int i = 0;i < n;i++) {
            disp += pow((A[i]-ave),2);
        }
        printf("%lf\n",sqrt(disp/n));
    }
    return 0;
}


Measured memory_bytes: 3136
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <iterator>

using namespace std;

#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(v) reverse((v).begin(),(v).end())
#define ANS(ans) cout<<(ans)<<endl;
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
typedef vector<int> VI;
typedef pair<int, int> P;

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  for (int i = 0; i < (n); ++i)

struct MyStruct {
	int a, b;
};

bool comp(const MyStruct& s, const MyStruct& t) {
	if (s.b != t.b)
		return s.b < t.b; //syoujunn
	return s.a > t.a;
}


int main() {
	int a, b;
	cin >> a >> b;

	if ((a + b) % 2 == 0) {
		ANS((a + b) / 2);
	}
	else {
		ANS("IMPOSSIBLE");
	}
	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 ll long long
int main(){
    int n;
    bool hantei=false;
    int iti=0,ni=0,yon=0;
    cin >> n;
    vector<ll>a(n);
    rep(i,n) cin >> a[i];
    rep(i,n){
        int c=a[i];
        int cnt=0;
        while(c%2 == 0){
            cnt++;
            c /= 2;
        }
        if(cnt == 0) iti++;
        else if(cnt == 1)ni++;
        else yon++;
    }
    if(ni==0){
        if(iti<=yon+1) hantei=true;
    }
    else{
        iti++;
        if(iti<=yon+1) hantei=true;
    }
    if(hantei) cout << "Yes"<<endl;
    else cout << "No" <<endl;
return 0;
    
}

Measured memory_bytes: 1024
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

string S;
int s_len;

long dfs(int idx, int bit) {
  if (idx == s_len - 1) {
    long sum = 0;
    int last = 0;
    for (int i = 0; i < s_len - 1; ++i) {
      if ((bit & (1 << i)) > 0) {
        sum += stol(S.substr(last, i + 1 - last));
        last = i + 1;
      }
    }
    sum += stol(S.substr(last));
    return sum;
  }

  return dfs(idx + 1, bit) + dfs(idx + 1, bit | (1 << idx));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> S;
  s_len = S.size();

  cout << dfs(0, 0) << endl;
  return 0;
}

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

using namespace std;

const int INF = 1000000;
int N, X;
int m[1100];

int main(){
  cin >> N >> X;
  for(int i=0; i<N; ++i){
    cin >> m[i];
  }
  
  int XAd = X;
  for (int i=0; i < N; ++i){
    XAd-=m[i];
  }
  
  int minG = INF;
  for (int i=0; i<N; ++i){
    if (m[i] < minG) minG = m[i];
  }
  
  int r = XAd / minG;
  int ans = r + N;
  
  cout << ans << endl;
  return 0;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> c(n),s(n),f(n);
  REP(i,n-1){
    cin>>c[i+1]>>s[i+1]>>f[i+1];
  }
  
  vector<int> ans(n+1,0);
  int t=0;
  for(int i=1;i<=n-1;i++){
    for(int j=i;j<=n-1;j++){
      if(t>=s[j]){
        t += (f[j]-t%f[j])%f[j];
      }else{
        t = s[j];
      }
      t += c[j];
    }
    ans[i]=t;
    t=0;
  }
  
  for(int i=1;i<=n;i++){
    cout<<ans[i]<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;
const int INF = 1e9;

int N, M;
char A[55][55], B[55][55];

signed main()
{
    cin >> N >> M;
    REP(i,N) REP(j,N) cin >> A[i][j];
    REP(i,M) REP(j,M) cin >> B[i][j];

    REP(i,N-M+1) REP(j,N-M+1) {
        bool ok = true;
        REP(ii,M) REP(jj,M) {
            if (A[i+ii][j+jj] != B[ii][jj]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
}


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

int main() {
  string s;
  cin >> s;
  
  int a = 0, z = 0;
  for (int i = 0; i < (int)s.size(); i++) {
    if (s.at(i) == 'A') {
      a = i;
      break;
    }
  }
    
  for (int i = (int)s.size() - 1; i >= 0; i--) {
    if (s.at(i) == 'Z') {
      z = i;
      break;
    }
  }
  
  cout << z - a + 1 << endl;
  
  return 0;
}
    

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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> v[n+1];
    int a[n+1] = {0};
    for(int i=0;i<m;i++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        a[y]=1;
    }
    vector<int> so;
    int visited[n+1] ={0};
    stack<int> ss;
    stack<int> ans;
    int total=0;
    int donetil = 1;
    while(total < n)
    {
        if(ss.empty())
        {
            for(int i = donetil; i<=n;i++)
            if(visited[i]==0)
            {
                //visited[i] = 1;
                donetil=i;
                ss.push(i);
            }
        }
        while(!ss.empty())
        {
            int t= ss.top();
            if(visited[t])
            {
                ss.pop();
                continue;
            }
            int len= v[t].size();
            int vis =0;
            for(int i = 0; i< len; i++)
            {
                if(visited[v[t][i]] == 1)
                vis++;
                else{
                ss.push(v[t][i]);
                 //visited[v[t][i]] = 1;
                }
            }
            if(vis == len)
            {
                ans.push(ss.top());
                visited[ss.top()]=1;
                ss.pop();
                total++;
            }
        }
    }

    int dis[n+1] = {0};
    for(int i=1;i<=n;i++){
    int t= ans.top();
    int len= v[t].size();
    for(int j=0;j<len;j++)
    {
        int p= v[t][j];
        dis[p]= max(dis[p], 1 + dis[t]);
    }
    ans.pop();
    }

    cout << *max_element(dis, dis+n+1);
}

Measured memory_bytes: 7680
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
// ぜったいあきらめない
#include<bits/stdc++.h>
using namespace std;

#if defined(DAIJOBU)
#include "/home/ichigo/debug.hpp"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}


int main(){
	FIO
	
	int a, b;cin >> a >> b;
	if(a < b)cout << "a < b\n";
	else if(a > b)cout << "a > b\n";
	else cout << "a == b\n";
	return 0;
}



Measured memory_bytes: 3132
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

const int M=18;
int n,a[M+1][M+1];

int main(){
	cin>>n;
	ll res=0;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		int m=s.size(),tmp=9;
		for(int j=0;j<m;j++) if(s[j]=='.') tmp=9-(m-j-1);
		s+=string(tmp,'0');
		ll t=0;
		for(auto c:s) if(isdigit(c)){
			t*=10;
			t+=c-'0';
		}
//		cout<<tmp<<' '<<s<<' '<<t<<endl;
		int x=0,y=0;
		while(t%2==0) t/=2,x++;
		while(t%5==0) t/=5,y++;
		x=min(x,M);
		y=min(y,M);
		for(int j=0;j<=M;j++) for(int k=0;k<=M;k++) if(j+x>=M&&k+y>=M) res+=a[j][k];
		a[x][y]++;
	}
	cout<<res<<endl;
}

Measured memory_bytes: 3600
#include<stdio.h>
int main()
{
    int i;
    int a, b;
    int p[4] = {};
    for (i = 0; i < 3; i++)
    {
        scanf("%d %d", &a, &b);
        a--;
        b--;
        p[a]++;
        p[b]++;
    }
    int q = 0;
    for (i = 0; i < 4; i++)
        if (p[i] % 2 == 1)
            q++;
    if (q < 3)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

Measured memory_bytes: 128
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS

readInt = fst . fromJust . BS.readInt
getInt = readInt <$> BS.getLine

main = do
    x <- getInt
    print $ solve x

isPeime 1 = True
isPrime 2 = True
isPrime n = and $ map (prime n) [2..(n-1)]

prime n m = (n `mod` m) /= 0

solve x = head [y | y <- [x..], isPrime y]

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

ll MOD = 1e9 + 7;
// ll MOD = 998244353;

// g = eGCD(a, b, s, t)  --->  sa + tb = g
constexpr ll eGCD(ll a, ll b, ll& s, ll& t) {
  if (a == 0) {
    s = 0;
    t = 1;
    return b;
  }
  ll u = 0;
  ll g = eGCD(b % a, a, t, u);
  s = u - (b / a) * t;
  return g;
}

constexpr ll gcd(ll a, ll b) {
  ll dummy1 = 0;
  ll dummy2 = 0;
  return eGCD(a, b, dummy1, dummy2);
}

struct Fp {
  ll val;

  Fp(ll t = 0) :
    val(t < 0 ? MOD + t % MOD : t >= MOD ? t % MOD : t) {}

  Fp& operator +=(const Fp& t) {
    val += t.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }

  Fp& operator -=(const Fp& t) {
    val -= t.val;
    if (val < 0) val += MOD;
    return *this;
  }

  Fp& operator *=(const Fp& t) {
    val = (val * t.val) % MOD;
    return *this;
  }

  Fp inv() const {
    if (val == 0) {
      cerr << "inv() is called for zero." << endl;
      exit(1);
    }
    ll u = 0;
    ll v = 0;
    eGCD(val, MOD, u, v);
    return Fp(u);
  }

  Fp& operator /=(const Fp& t) {
    return (*this) *= t.inv();
  }

  Fp operator +(const Fp& t) const { return Fp(val) += t; }
  Fp operator -(const Fp& t) const { return Fp(val) -= t; }
  Fp operator *(const Fp& t) const { return Fp(val) *= t; }
  Fp operator /(const Fp& t) const { return Fp(val) /= t; }
  Fp operator -() const { return Fp(-val); }

  bool operator ==(const Fp& t) const { return val == t.val; }
  bool operator !=(const Fp& t) const { return val != t.val; }
  
  operator ll() const { return val; }

};

class Comb {
  int nMax;
  vector<Fp> vFact;
  vector<Fp> vInvFact;
public:
  Comb(int nm) : nMax(nm), vFact(nm+1), vInvFact(nm+1) {
    vFact.at(0) = 1;
    for (int i = 1; i <= nMax; i++) vFact.at(i) = i * vFact.at(i-1);
    vInvFact.at(nMax) = vFact.at(nMax).inv();
    for (int i = nMax; i >= 1; i--) vInvFact.at(i-1) = i * vInvFact.at(i);
  }
  Fp fact(int n) { return vFact.at(n); }
  Fp comb(int n, int r) {
    return vFact.at(n) * vInvFact.at(r) * vInvFact.at(n-r);
  }
  // The number of permutation extracting r from n.
  Fp perm(int n, int r) {
    return vFact.at(n) * vInvFact.at(n-r);
  }
};

/* 
   Power function    power(a, b) == a^b
   Speed is O(log b).
   The same source code can be used for integers by replacing
   Fp with int etc.  Unfortunately, replacing Fp with auto does not
   make the function generic for int and Fp.
 */
Fp power(Fp a, int b) {
  Fp twoPow = a;
  Fp rv = 1;
  while (b > 0) {
    if (b & 1) rv *= twoPow;
    twoPow *= twoPow;
    b >>= 1;
  }
  return rv;
}

Fp solve1(int yh, int xw) {
  Fp cat1 = power(2, yh) + power(2, xw) - (Fp)1;
  int g = gcd(yh, xw);
  Fp cat2 = power(2, g) - (Fp)2;
  return cat1 + cat2;
}

int main(int argc, char *argv[]) {
  // C-style stdio functions should not be used.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  int H, W, T;
  cin >> H >> W >> T;

  int gh = gcd(H, T);
  int gw = gcd(W, T);
  int yh = H / gh;
  int xw = W / gw;

  Fp ans = power(power(solve1(yh, xw), gh), gw);
  cout << (int)ans << endl;

  return 0;
}



Measured memory_bytes: 256
package main

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

func main() {
	log.SetFlags(log.Lshortfile)
	s := nextString()
	// cnt := 0
	// bs := []byte(s)
	// for {
	// 	tcnt := 0
	// 	for i := 0; i < len(bs)-1; i++ {
	// 		if bs[i] == 'B' && bs[i+1] == 'W' {
	// 			bs[i] = 'W'
	// 			bs[i+1] = 'B'
	// 			tcnt++
	// 			cnt++
	// 		}
	// 	}
	// 	if tcnt == 0 {
	// 		break
	// 	}
	// }
	// log.Println(string(bs))
	// fmt.Println(cnt)
	b := []byte(s)
	ans := 0
	numW := 0
	for i := 0; i < len(b); i++ {
		if b[i] == 'W' {
			// log.Println(i, numW)
			ans += (i - numW)
			numW++
		}
	}
	fmt.Println(ans)
}
func Max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func Min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func Sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func Abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type Pair struct {
	a, b int
}

type Pairs []Pair

func (p Pairs) Len() int {
	return len(p)
}
func (p Pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Pairs) Less(i, j int) bool {
	return p[i].b < p[j].b
}

var nextReader func() string

func init() {
	nextReader = NewScanner()
}

func NewScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() string {
		r.Scan()
		return r.Text()
	}
}
func nextString() string {
	return nextReader()
}
func nextInt64() int64 {
	v, _ := strconv.ParseInt(nextReader(), 10, 64)
	return v
}
func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}
func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}
func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(nextReader(), 64)
	return f
}


Measured memory_bytes: 1536
#include <bits/stdc++.h> 
using namespace std; 
int a[200014];
map<int, int> bs;
int main() {
    int n;
    scanf("%d", &n);
    int mx = -1;
    for (int i = 0; i < n; i++) {
        scanf("%d", a+i);
        bs[a[i]]++;
        mx = max(mx, a[i]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = a[i] * 2; j <= mx; j += a[i]) {
            bs[j] = 0;
        }
    }
    memset(a, 0, sizeof(a));
    int cnt = 0;
    for (auto ite = bs.begin(); ite != bs.end(); ite++) {
        if (ite -> second == 1) {
            a[cnt++] = ite -> first;
        }
    }
    int ans = cnt;
    for (int i = 0; i < cnt; i++) {
        if (bs[a[i]] > 1) {
            ans--;
            continue;
        }
        for (int j = a[i]; j <= a[cnt-1]; j += a[i]) {
            bs[j]+=1;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<vector<int>> d(n,vector<int>(3));
  for(int i=0;i<n;i++){
    for(int j=0;j<2;j++){
      cin >> d.at(i).at(j);
    }
    if(d.at(i).at(0)==d.at(i).at(1)){
      d.at(i).at(2)=0;
    }else{
      d.at(i).at(2)=-1;
    }
  }
  bool frag=false;
  for(int k=2;k<n;k++){
    if(d.at(k-2).at(2)==0&&d.at(k-1).at(2)==0&&d.at(k).at(2)==0){
      frag=true;
    }
  }
  if(frag==true){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N) cin >> A[i];

  ll ans = 0;
  map<int, int> m;
  rep(i, N) {
    ans += m[A[i]];
    m[A[i]]++;
  }

  rep(i, N) { cout << ans - m[A[i]] + 1 << endl; }
}

Measured memory_bytes: 9916
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for i in range(q)]
ans=0
for A in combinations_with_replacement(range(m),n):
  p=0
  for i in range(q):
    a,b,c,d=abcd[i]
    if A[b-1]-A[a-1]==c:
      p+=d
  ans=max(ans,p)
print(ans)

Measured memory_bytes: 9236
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n, k, c = nm()
a = ns()

ans = []
al = []
count = 0
dey = 1
for i in a:
    if i is "o" and count <= 0:
        al.append(dey)
        count = c + 1
    dey += 1
    count -= 1
ar = []
count = 0
dey = n
for i in reversed(a):
    if i is "o" and count <= 0:
        ar.append(dey)
        count = c + 1
    dey -= 1
    count -= 1


al = al[:k]
ar = ar[:k]
for i in al:
    j = ar.pop(-1)
    if i == j:
        ans.append(i)
for i in ans:
    print(i)


Measured memory_bytes: 20840
N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
  A[i],B[i]=map(int,input().split())
C=[a+b for a,b in zip(A,B)]
D=[a-b for a,b in zip(A,B)]
print(max((max(C)-min(C)),(max(D)-min(D))))

Measured memory_bytes: 100292
// inputに入力データ全体が入る
function Main(input) {
  input = input.split(" ");
  let S = parseInt(input[0], 10);
  let W = parseInt(input[1], 10);
  console.log(W >= S ? "unsafe" : "safe");
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

#define N 8
#define FREE -1
#define NOT_FREE 1

int row[N], col[N], dpos[2 * N - 1],dneg[2*N-1];

bool X[N][N];

void initialize() {
	for (int i = 0; i < N; i++) { row[i] = FREE, col[i] = FREE; }
	for (int i = 0; i < 2 * N - 1; i++) { dpos[i] = FREE; dneg[i] = FREE; }
}

void printBoard() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (X[i][j]) {
				if (row[i] != j)return;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << ((row[i] == j) ? "Q" : ".");
		}
		cout << endl;
	}
}

void recursive(int i) {
	if (i == N) {
		printBoard(); 
		return;
	}

	for (int j = 0; j < N; j++) {
		if (NOT_FREE == col[j] ||
			NOT_FREE == dpos[i + j] ||
			NOT_FREE == dneg[i - j + N - 1])continue;
		row[i] = j;
		col[j] = dpos[i + j] = dneg[i - j + N - 1] = NOT_FREE;
		recursive(i + 1);
		row[i] = col[j] = dpos[i + j] = dneg[i - j + N - 1] = FREE;
	}
}

int main() {
	initialize();

	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)X[i][j]=false;
	int k;
	cin >> k;
	for (int i = 0; i < k; i++) {
		int r, c;
		cin >> r >> c;
		X[r][c] = true;
	}

	recursive(0);

	return 0;
}


Measured memory_bytes: 3116
n = gets.to_i
arr = gets.split(" ").map(&:to_i)

sum = 0
mod = 10 ** 9 + 7
ssum = arr.sum % mod

n.times do |i|
  ssum -= arr[i]
  ssum = (ssum + mod) % mod
  sum += (arr[i] * ssum) % mod
end

puts sum % mod


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

using namespace std;

const int N = 1234567;

int n, que[N];
char s[N], w[N];

int main() {
  scanf("%d %s %s", &n, s, w);
  if (strcmp(s, w) == 0) {
    puts("0");
    return 0;
  }
  int ans = 1;
  int qh = 0, qt = 0;
  int j = n - 1;
  for (int i = n - 1; i >= 0; i--) {
    if (i == 0 || w[i] != w[i - 1]) {
      j = min(i, j);
      while (j >= 0 && s[j] != w[i]) {
        j--;
      }
      if (j < 0) {
        puts("-1");
        return 0;
      }
      while (qh < qt && que[qh] - (qt - qh - 1) > i) {
        qh++;
      }
      if (i != j) {
        que[qt++] = j;
        ans = max(ans, qt - qh + 1);
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}

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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string S; cin >> S;
	int N = S.size();
	if (S[0] == '0' || S[N-1] == '1') {
		print(-1); return 0;
	}

	F0R(i, N-1) if (S[i] != S[N-i-2]) {
		print(-1);
		return 0;
	}
	int j = 2;
	for (int i = 1; i <= N/2; ++i) {
		while (S[j-1] == '0' || j <= i) ++j;
		print(i, j);
	}
	for (int k = N/2+1; k < j; ++k) print(j, k);
	for (int k = j + 1; k <= N; ++k) print(j, k);
	return 0;
}

Measured memory_bytes: 3756
#include<iostream>
#include<string>
#include<cmath>

using namespace std;

int main(){
  int n;
  int a[2][100];
  cin>>n;
  for(int i=0;i<2;i++){
    for(int j=0;j<n;j++){
      cin>>a[i][j];
    }
  }
  int ans = 0;
  for(int i=0;i<n;i++){
    int tmp = 0;
    for(int j=0;j<n;j++){
      if(j < i){
        tmp += a[0][j];
      } else if(j == i){
        tmp += a[0][j];
        tmp += a[1][j];
      } else {
        tmp += a[1][j];
      }
    }
    ans = max(ans, tmp);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N,M;
    scanf("%d%d",&N,&M);
    int ans=0;
    ans=(N-M)*100+M*1900;
    for(int i=0;i<M;i++){
        ans*=2;
    }
    cout<<ans<<endl;
    return 0;
}


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

using namespace std;

int main() {
	string a, b, c;
	cin >> a >> b;
	int n = (int)a.size();
	int m = (int)b.size();
	if (n > m) {
		puts("GREATER");
	} else if (m > n) {
		puts("LESS");	
	} else {
		for (int i = 0; i < n; i++) {
			if (a[i] > b[i]) {
				puts("GREATER");
				return 0;
			}
			if (b[i] > a[i]) {
				puts("LESS");
				return 0;
			}
		}
		puts("EQUAL");
	}
	return 0;
}

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

vector<pair<int, pii>> edge[200000];
ll yenCost[200000], snuukCost[200000];

void bfs1(int start) {
  priority_queue<pll, vector<pll>, greater<pll>> pq;
  pq.push(mp(start, 0));

  while (!pq.empty()) {
    int cur = pq.top().F;
    ll cost = pq.top().S;
    pq.pop();

    rep(i, edge[cur].size()) {
      int next = edge[cur][i].F;
      ll nextCost = edge[cur][i].S.F;
      if (yenCost[next] <= yenCost[cur] + nextCost) continue;
      yenCost[next] = yenCost[cur] + nextCost;
      pq.push(mp(next, yenCost[next]));
    }
  }
}

void bfs2(int start) {
  priority_queue<pll, vector<pll>, greater<pll>> pq;
  pq.push(mp(start, 0));

  while (!pq.empty()) {
    int cur = pq.top().F;
    ll cost = pq.top().S;
    pq.pop();

    rep(i, edge[cur].size()) {
      int next = edge[cur][i].F;
      ll nextCost = edge[cur][i].S.S;
      if (snuukCost[next] <= snuukCost[cur] + nextCost) continue;
      snuukCost[next] = snuukCost[cur] + nextCost;
      pq.push(mp(next, snuukCost[next]));
    }
  }
}

int main() {
  int n, m, s, t;
  cin >> n >> m >> s >> t;
  s--;
  t--;
  rep(i, m) {
    int u, v, a, b;
    cin >> u >> v >> a >> b;
    u--;
    v--;
    edge[u].eb(mp(v, mp(a, b)));
    edge[v].eb(mp(u, mp(a, b)));
  }

  rep(i, n) yenCost[i] = snuukCost[i] = INF;

  yenCost[s] = 0;
  bfs1(s);

  snuukCost[t] = 0;
  bfs2(t);

  const ll ini = 1000000000000000;
  vector<ll> ans(n, 0);
  for (int i = n - 1; i >= 0; i--) {
    ans[i] = max(ans[i], ini - yenCost[i] - snuukCost[i]);
    if (i) ans[i - 1] = ans[i];
  }

  rep(i, n) cout << ans[i] << endl;
}


Measured memory_bytes: 19012
#include<bits/stdc++.h>
using namespace std;
static const int MAX=100000;
static const int INFTY=(1<<29);

vector<int> G[MAX];
list<int> out;
bool V[MAX];
int N;
int indeg[MAX];

void bfs(int s){
	queue<int> q;
	q.push(s);
	V[s]=true;
	while(!q.empty()){
		int u=q.front();q.pop();
		//??\?¬???°???0??????????????????????????\?????????
		out.push_back(u);
		for (int i = 0; i < G[u].size(); ++i) {
			int v=G[u][i];
			//???????¶?????????¨??????????????????
			indeg[v]--;
			if(indeg[v]==0&&!V[v]){
				V[v]=true;
				q.push(v);
			}
		}
	}
}

void tsort(){
	for (int i = 0; i < N; ++i) {
		indeg[i]=0;
	}
	for (int u = 0; u < N; ++u) {
		for (int i = 0; i < G[u].size(); ++i) {
			int v=G[u][i];
			indeg[v]++;
		}
	}
	for (int u = 0; u < N; ++u) {
		if(indeg[u]==0&&!V[u])bfs(u);}
	for (list<int>::iterator it=out.begin();it !=out.end();it++) {
		cout<<*it<<endl;
	}
}

int main(){
	int s,t,M;
	cin>>N>>M;
	for (int i = 0; i < N; ++i) {V[i]=false;}
	for (int i = 0; i < M; ++i) {
		cin>>s>>t;
		G[s].push_back(t);
	}
	tsort();
	return 0;
}

Measured memory_bytes: 6152
#include<stdio.h>
int main(){  

 int  x, y, tmp;
 

 while(1){
  scanf("%d%d", &x, &y);
  if(x == 0 && y == 0){
     break;
  }
  if(x > y){
     tmp = x; x = y; y = tmp;
  }


    printf( "%d %d\n", x, y);
    
  }

  return 0;
}




Measured memory_bytes: 1992
from collections import defaultdict

MAX = 40001


def main():
    N, Ma, Mb = [int(a) for a in input().split()]

    abc = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    dp = [
        [
            [MAX for b in range(10 * N + 1)]
            for a in range(10 * N + 1)
        ]
        for i in range(N)
    ]  # dp[i][a][b] = i番目までを使ってaグラムbグラムを作る最小コスト

    A, B, C = abc[0]
    # dp[0][a][b] = c
    # dp[0][0][0] = 0

    mem = {(0, A, B): C, (0, 0, 0): 0}

    def solve(i, a, b):
        if (i, a, b) in mem:
            return mem[(i, a, b)]
        if i == 0:
            return MAX
        ai, bi, ci = abc[i]
        tukawanai = solve(i - 1, a, b)
        if a - ai >= 0 and b - bi >= 0:
            pre = solve(i - 1, a - ai, b - bi)
            if pre != MAX:
                mem[(i, a, b)] = min(tukawanai, pre + ci)
                return mem[(i, a, b)]
        mem[(i, a, b)] = tukawanai
        return mem[(i, a, b)]

    res = MAX
    for a in range(1, 10 * N + 1):
        aa = a * Mb
        if aa % Ma != 0:
            continue
        b = aa // Ma
        if b >= 10 * N + 1:
            continue
        c = solve(N - 1, a, b)
        res = min(res, c)

    if res == MAX:
        res = -1
    print(res)


if __name__ == '__main__':
    main()


Measured memory_bytes: 182224
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ROP(i,n) for(int i=0;i<n;i++)
using namespace std;
int A[2017];
int N,Z,W,i;
int main(){
  scanf("%d %d %d",&N,&Z,&W);
  ROP(i,N) scanf("%d",&A[i]);
  if(N==1) printf("%d\n",abs(A[N-1]-W));
  else printf("%d\n",max(abs(A[N-1]-W),abs(A[N-2]-A[N-1])));
  return 0;
}


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

#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);

typedef long long int lli;

int main()
{
	fio;
	int n,i;
	cin>>n>>i;
	n++;
	cout<<n-i<<endl;
	cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100000

int A[MAX],n;
int partition(int,int);

int main(){
  int i,q;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);

  q=partition(0,n-1);

  for(i=0;i<n;i++){
    if(i)printf(" ");
    if(i==q)printf("[");
    printf("%d",A[i]);
    if(i==q)printf("]");
  }
  printf("\n");

  return 0;
}

int partition(int p,int r){
  int x, i, j, tmp;
  x = A[r];
  i = p - 1;
  for(j=p;j<r;j++){
    if(A[j] <= x){
      i++;
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }
  }
  tmp = A[i+1];
  A[i+1] = A[r];
  A[r] = tmp;

  return i+1;
}

Measured memory_bytes: 992
# -*- coding: utf-8 -*-
# 標準入力の取得
X = int(input())


def main() -> None:
    """Entry point
    """
    # 求解処理
    # 1年毎に預金額を計算し、Xと比較する
    deposit = 100
    year = 0
    while deposit < X:
        deposit += deposit // 100
        year += 1

    # 結果出力
    print(year)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9016
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1LL<<60;
const double EPS = 1e-10;
const ll mod=1000000007;
//const ll mod=998244353;

int main(void){
  ll n,x,t;
  cin>>n>>x>>t;
  ll a=ceil(double(n)/double(x))*t;
  cout<<a<<endl;
}

Measured memory_bytes: 3604
n = int(input())
S_cards = []
H_cards = []
C_cards = []
D_cards = []

for _ in range(n):
    card = input()
    if card[0] == "S":
        S_cards.append(card[2:])
    elif card[0] == "H":
        H_cards.append(card[2:])
    elif card[0] == "C":
        C_cards.append(card[2:])
    else:
        D_cards.append(card[2:])

for j in range(1,14):
    if str(j) not in S_cards:
        print("{} {}".format("S",j))
        
for j in range(1,14):
    if str(j) not in H_cards:
        print("{} {}".format("H",j))
        
for j in range(1,14):
    if str(j) not in C_cards:
        print("{} {}".format("C",j))
        
for j in range(1,14):
    if str(j) not in D_cards:
        print("{} {}".format("D",j))


Measured memory_bytes: 5608
N = int(input())
h = [int(x) for x in input().split()]
count = 0
con = 0
while True:
    for i in range(N):
        if h[i] > 0:
            h[i] -= 1
            con = 1
        elif h[i] <= 0:
            if con == 1:
                count += 1
            con = 0
    if con == 1:
        count += 1
    con = 0
    if not any(h):
        break

print(count)


Measured memory_bytes: 65616
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
using namespace std;
typedef long double ld;
typedef long long lli;
typedef pair<lli,lli> ii;
typedef vector<lli> vi;
#define deb(x) cout << #x": " << (x) << endl;

int main(){ _
  ld d, t, s;
  cin >> d >> t >> s;
  ld a = d / s;
  if (a <= t){
    cout << "Yes" << ENDL;
  }
  else{
    cout << "No" << ENDL;
  }
  return 0;
}


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

using namespace std;

int n;
const int maxn = 1e5 + 5;
vector<int> G[maxn];

int dp[maxn][2];
const int mod = 1e9 + 7;

void add(int &a, int b){
    a += b;
    if(a >= mod){
        a -= mod;
    }
}

void dfs(int u, int fa){
    dp[u][1] = 1;
    dp[u][0] = 1;
    for(auto v : G[u]){
        if(v == fa)
            continue;
        dfs(v, u);
        dp[u][1] = 1LL * dp[u][1] * dp[v][0] % mod;
        dp[u][0] = 1LL * dp[u][0] * (dp[v][0] + dp[v][1]) % mod; 
    }
}

int main(){
    cin >> n;
    for(int i = 1;i < n;i++){
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 1);
    cout << (dp[1][1] + dp[1][0]) % mod << endl;
    return 0;
}


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

int main(){
    LL N;
    cin >> N;
    vector<LL> a(N+1);
    for(LL i = 1;i < N+1;i++)    cin >> a[i];
    vector<LL> sum(N+1), Xor(N+1);
    for(LL i = 1;i < N+1;i++)  sum[i] = sum[i-1]+a[i];
    for(LL i = 1;i < N+1;i++)  Xor[i] = Xor[i-1]^a[i];
    LL ans = 0;
    for(LL l = 1;l < N+1;l++){
        LL min = l;
        LL max = N+1;
        for(int i = 0;i < 20;i++){
            LL mid = (max+min)/2;
            LL s = sum[mid]-sum[l-1];
            LL x = Xor[mid]^Xor[l-1];
            if(s == x)  min = mid;
            else    max = mid;
        }
        ans += max-l;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
vector <int> vec(N);
for (int i=0; i<N; ++i){
    cin >> vec.at(i);
}
// 入力終わり
int sum_a=0, sum_b=0;
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());

for(int i=0; i<N; i+=2){
    sum_a+=vec.at(i);
}
for(int i=1; i<N; i+=2){
    sum_b+=vec.at(i);
}
cout << sum_a - sum_b << endl;

/*
for(int i=0; i<N+10; i++){
    cout << vec.at(i) << endl;
}
*/
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
using namespace std;
typedef long long ll;

int main(){
    int n, ans = 0;
    cin >> n;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    vector<int> minp(n);
    minp[0] = p[0];
    rep(i,n-1){
        minp[i+1] = min(minp[i], p[i+1]);
    }
    rep(i,n){
        if(minp[i] == p[i]) ++ans;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
import bisect
N, Q = map(int, input().split())
S = input()
minians = []
for i in range(N-1):
    if S[i:i + 2] == "AC":
        minians.append(i)
ans = [0]*Q
for i in range(Q):
    left, right = map(int, input().split())
    left -= 1
    right -= 1
    ans[i] = bisect.bisect_left(minians, right) - \
        bisect.bisect_left(minians, left)
print('\n'.join(map(str, ans)))


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

int main() 
{
  int n, a, b;
  cin >> n >> a >> b;
  int answer = 0;
  for(int i = 1; i <= n; i++)
  {
    int calcu = i;
    int data = 0;
    while(calcu > 0)
    {
      data += calcu % 10;
      calcu /= 10;
    }
    if(data >= a && data <= b)
    {
      answer += i;
    }
  }
  cout << answer << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define FOR(i,a,n) for(int i=a,i##_len=(int)(n);i<i##_len;++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i=(int)(n);i>=0;--i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)   // c++14
#define SZ(c) ((int)c.size())
#define EXIST(c,x) (c.find(x)!=end(c))
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
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;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
    }
} before_main_function;
//------------------------------------------------------------------------------

signed main() {
    int N,C,K;
    cin>>N>>C>>K;
    vi T(N);
    cin>>T;
    sort(ALL(T));
    int beg=0;
    int ans=0;
    int acc=C;
    REP(i,N) {
        acc-=1;
        if(i==N-1 || acc==0 || T[i+1]>T[beg]+K) {
            acc=C;
            ans++;
            dump(i,acc,ans,beg);
            beg=i+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
long long int n=0,m=0,i=0,y=0,count=0,z=0;
cin >> n >> m;
long long int arr[n+1],out[n+1];
for(i=0;i<=n;i++){out[i] = 1;}
arr[0] = 0;
for(i=1;i<=n;i++){
  cin >> arr[i];
}
vector<pair<long long int,long long int>> vect;
for(i=0;i<m;i++){
cin >> y >> z;
vect.push_back(make_pair(y,z));
}
for(i=0;i<m;i++){
if(arr[vect[i].first]>arr[vect[i].second]){out[vect[i].second]=0;}
else if(arr[vect[i].first]<arr[vect[i].second]){out[vect[i].first]=0;}
else{
out[vect[i].second]=0;
out[vect[i].first]=0;
}
}
for(i=1;i<=n;i++){
	if(out[i]==1){count++;}
}
  cout << count << endl;
}

Measured memory_bytes: 6840
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void command(string &str, const string& cmd, const int a, const int b, const string& p){
  if(cmd == "print"){
    cout << str.substr(a, b-a+1) << endl;
  }
  else if(cmd == "reverse"){
    reverse(str.begin() + a, str.begin() + b + 1);
  }
  // replace
  else{
    str.replace(a, b-a+1, p);
  }
}

int main(void){
  string input;
  string cmd;
  int commandNum;
  int a, b;
  string p = "";
  cin >> input;
  cin >> commandNum;
  for(int i = 0; i < commandNum; i++){
    cin >> cmd >> a >> b;
    if(cmd == "replace") cin >> p;
    command(input, cmd, a, b, p);
  }
  return 0;
}



Measured memory_bytes: 3224
/*** I came, I saw, I conquered. ***/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;typedef unsigned long long ull;
#define sc(a) cin >> a
#define pf(a) cout << a << endl
#define forIn(arr, num) for(ll i = 0; i < num; i++) cin >> arr[i];
#define vpnt(ans) for(ll i = 0; i < ans.size(); i++) cout << ans[i] << (i + 1 < ans.size() ? ' ' : '\n');
#define mod 1000000007
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define GET_SET_BITS(a) (__builtin_popcount(a))
#define GET_SET_BITSLL(a) ( __builtin_popcountll(a))
#define GET_TRAIL_ZERO(a) (__builtin_ctz(a))
#define GET_LEAD_ZERO(a) (__builtin_clz(a))
#define GET_PARITY(a) (__builtin_parity(a))
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
void go() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
/*----------------------------------------------------------------*/
void solve() {
    string str;
    sc(str);

    if(str.back() == 's') {
        str += "es";
    } else {
        str += "s";
    }

    pf(str);
}

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

Measured memory_bytes: 3660
using System;

namespace AOJ.Volume0
{
    public class CirclesIntersection
    {
        public static void Main()
        {
            int cnt = int.Parse(Console.ReadLine());
            for (int i = 0; i < cnt; i++)
            {
                var input = Console.ReadLine().Split(' ');
                double ax = double.Parse(input[0]);
                double ay = double.Parse(input[1]);
                double ar = double.Parse(input[2]);
                double bx = double.Parse(input[3]);
                double by = double.Parse(input[4]);
                double br = double.Parse(input[5]);
                // A、B2つの円の関係を調査
                double dis = Math.Sqrt(Math.Pow(ax - bx, 2) + Math.Pow(ay - by, 2));
                // 中心の距離 > 半径の和→重なっていない
                if (dis > ar + br)
                {
                    Console.WriteLine("0");
                    continue;
                }
                // 中心の距離 + Bの半径 <= Aの半径→Aの中にBが含まれる
                if (dis + br < ar)
                {
                    Console.WriteLine("2");
                    continue;
                }
                // 中心の距離 + Aの半径 <= Bの半径→Bの中にAが含まれる
                if (dis + ar < br)
                {
                    Console.WriteLine("-2");
                    continue;
                }
                // 上記以外は重なっている
                Console.WriteLine("1");
            }
        }
    }
}

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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while (true) {
        c -= b;
        if (c <= 0) {
            cout << "Yes" << endl;
            return 0;
        }
        a -= d;
        if (a <= 0) {
            cout << "No" << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 3636