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

#define lson l, m, rt*2
#define rson m + 1, r, rt*2+1
#define xx first
#define yy second

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;

int n, t[100010];
string s;

bool check(int x, int y) {
  t[0] = x;
  t[1] = y;
  for (int i = 2; i < n; i++) {
    if (t[i - 1] == 0) {
      //sheep
      if (s[i - 1] == 'o') t[i] = t[i - 2]; else t[i] = t[i - 2] ^ 1;
    }
    else {
      //wolf
      if (s[i - 1] == 'x') t[i] = t[i - 2]; else t[i] = t[i - 2] ^ 1;
    }
  }
  for (int i = 0; i < n; i++) {
    int t1 = (i + n - 1) % n;
    int t2 = (i + 1) % n;
    if (t[i] == 0) {
      if (s[i] == 'o' && t[t1] != t[t2]) return false;
      if (s[i] == 'x' && t[t1] == t[t2]) return false;
    }
    else {
      if (s[i] == 'x' && t[t1] != t[t2]) return false;
      if (s[i] == 'o' && t[t1] == t[t2]) return false;
    }
  }
  return true;
}

int main() {
#ifdef JUDGE
  freopen("case.in", "r", stdin);
#endif
  cin >> n >> s;
  for (int i = 0; i < 4; i++) {
    int t1 = i % 2, t2 = (i / 2) % 2;
    if (check(t1, t2)) {
      for (int j = 0; j < n; j++) if (!t[j]) putchar('S'); else putchar('W');
      return 0;
    }
  }
  puts("-1");
  return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, X;
  cin>>N>>X;

  vector<int> L(N);
  cin>>L;
  
  int d = 0;
  int ans = d <= X;
  for(int i=0;i<N;i++){
    d = d + L[i];
    ans += d <= X;
  }

  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int i = a; i < b; i++)
using pii = pair<int,int>;

int main(){
    int a, b, c, n;
    int ans = 0;
    int v[10];
    string vs[10];
    string S;
    
    cin >> a >> b >> n;

    a = max(a, b);
    cout << (n -1 + a) / a << endl;
}

Measured memory_bytes: 764
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author apurba_debnath
 */

#include <bits/stdc++.h>

#define ll long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl

using namespace std;

class BMultiplication2 {
public:
    void solve(std::istream &in, std::ostream &out) {
        int n;
        in >> n;
        ll a[101010];
        ll zero = 0;
        for (int i = 0; i < n; ++i) {
            in >> a[i];
            if (a[i] == 0)
                zero++;
        }
        if (zero)
            out << 0;
        else {
            ll p = 1;
            for (int i = 0; i < n; ++i) {
                if (a[i] <= 1000000000000000000 / p)
                    p *= a[i];
                else {
                    out << "-1";
                    return;
                }
            }
            out << p;
        }
    }
};


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

    BMultiplication2 solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);

    return 0;
}


Measured memory_bytes: 4440
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

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

  if(((N[0] == N[1]) && (N[1] == N[2])) || ((N[1] == N[2]) && (N[2] == N[3]))){
    cout << "Yes" << endl;
  } else{
    cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "OK" : "NG")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define Return(expr) { Cout(expr); return 0; }
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, k, a, b);
    for(int i = a; i <= b; i ++){
    	if(i % k == 0) Return("OK");
    }
    Cout("NG");
}

Measured memory_bytes: 3632
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort
#include <math.h> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

int main(){
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    string s1,s2;
    cin >> s1;
    cin >> s2;

    reverse(s1.begin(),s1.end());
    string res;
    if(s1 == s2)
    {
        res = "YES";
    }
    else
    {
        res = "NO";
    }


    cout << res << endl;
    return 0;    

}



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

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	const int b_all = count(s.begin(), s.end(), '#');
	const int w_all = count(s.begin(), s.end(), '.');
	int b_cur = 0, w_cur = 0, answer = min(b_all, w_all);
	for(int i = 0; i < n; ++i){
		const int b_left = b_cur, w_right = w_all - w_cur;
		answer = min(answer, b_left + w_right);
		if(s[i] == '#'){
			++b_cur;
		}else{
			++w_cur;
		}
	}
	cout << answer << endl;
	return 0;
}



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

int fn[500001], fc[500001], x[500001], md = 1e9 + 7, n, mis[500001];
bool p[500001];

inline int gt(int i) { int an = 0; while (i)an += fn[i], i ^= i & -i; return an; }
inline void ad(int i) { while (i <= n)++fn[i], i += i & -i; }

int main(){
	scanf("%d", &n);
	f(i, 1, n + 1)scanf("%d", x + i), p[x[i]] = true;
	int missum = 0, z = 0;
	f(i, 1, n + 1)if (!p[i]){
		mis[z++] = i, missum += i - 1;
		if (missum >= md)missum -= md;
	}
	fc[0] = 1;
	f(i, 1, n + 1)fc[i] = (ll)fc[i - 1] * i % md;
	int an = fc[z], beh = 0, k = 0, zsum = (ll)z * (z - 1) / 2 % md;
	f(i, 1, n + 1){
		if (x[i]){
			int sm = upper_bound(mis, mis + z, x[i]) - mis;
			int t = (ll)gt(x[i]) * fc[z] % md + (ll)sm * beh % md * fc[z - 1] % md;
			an += (ll)fc[n - i] * ((ll)fc[z] * (x[i] - 1) % md - t) % md;
			if (an >= md)an -= md;
			else if (an < 0)an += md;
			k += z - sm;
			if (k >= md)k -= md;
			ad(x[i]);
		}else {
			int t = (ll)fc[z - 1] * k % md + (ll)beh * zsum % md * fc[z - 2] % md;
			an += (ll)fc[n - i] * ((ll)missum * fc[z - 1] % md - t) % md;
			if (an >= md)an -= md;
			else if (an < 0)an += md;
			++beh;
		}
	}
	printf("%d\n", an);
}


Measured memory_bytes: 8320
import Control.Applicative
import Data.List

main :: IO ()
main = do  
  x <- getInts
  let lectW = x !! 0
      lectH = x !! 1
      circleX = x !! 2
      circleY = x !! 3
      radius = x !! 4
      bottom = circleY - radius >= 0
      top = circleY + radius <= lectH
      leftEdge = circleX - radius >=0
      rightEdge = circleX + radius <=lectW
      answer = if bottom && top && leftEdge && rightEdge then "Yes" else "No"
  putStrLn answer




getInts = do 
  x <- getLine 
  let y = (map$toInt)$words x
  return y

toInt :: (String -> Int)
toInt x = read x :: Int



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

const long long INF = 1LL << 60;

int main() {
    ll N; cin >> N;
    vector<ll> H(N, 0);
    for(ll i=0; i<N; i++){
        cin >> H.at(i);
    }

    ll low=H.at(0);
    for(ll i=0; i<N-1; i++){
        if(H.at(i)-1>H.at(i+1)){
            cout << "No" << endl;
            return 0;
        }

        if(H.at(i)-1 == H.at(i+1)){
            if(low > H.at(i+1)){
                cout << "No" << endl;
                return 0;
            }

            low = H.at(i+1);
        }
    }

    cout << "Yes" << endl;

}


Measured memory_bytes: 1024
# 最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


L = [0 for _ in range(N)]
R = [0 for _ in range(N)]

L[0] = A[0]
R[N-1] = A[N-1]

for i in range(1, N):
    L[i] = gcd(L[i-1], A[i])

for i in reversed(range(N-1)):
    R[i] = gcd(R[i+1], A[i])

ans = 0
for i in range(N):
    if i == 0:
        ans = max(ans, R[i+1])
    elif i == N-1:
        ans = max(ans, L[i-1])
    else:
        ans = max(ans, gcd(L[i-1], R[i+1]))

print(ans)

Measured memory_bytes: 65124
($H,$W)=glob<>;
$N=<>;
@A=glob<>;chomp(@A);
for (my$i=0;$i<$N;$i++){
    push(@C,$i+1) for(1..$A[$i]);    
}
$d=1;
$,=" ";
for(my$i=0;$i<$H;$i++){
    @o=@C[$i*$W..$i*$W+$W-1];
    @o=reverse(@o) if($d<0);
    print @o;
    print "\n";
    $d*=-1;
}

Measured memory_bytes: 3328
#include<stdio.h>

int main()
{
	int i,ii,ru=0,rare=0;

	for(i=1;i<10;i++){
		rare++;
		for(ii=1;ii<10;ii++){
			ru++;
			printf("%dx%d=%d\n",rare,ru,rare*ru);
		}
		ru=0;
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;

int main()
{
    string S;
    cin >> S;
    ll k;
    cin >> k;
    int len = S.size();
    ll ans = 0, add = 0, fnum = 1, bnum = 1;
    if (S.front() != S.back())
    {
        rep(i, len - 1)
        {
            if (S[i] == S[i + 1])
            {
                ans++;
                if (i + 2 < len)
                {
                    rep(j, 3)
                    {
                        if (S[i] != i and S[i + 2] != i)
                        {
                            S[i + 1] = i;
                            break;
                        }
                    }
                }
            }
        }
    }
    else
    {
        for (int i = 0; S[i] == S[i + 1]; i++)
        {
            fnum++;
        }
        for (int i = len - 1; S[i - 1] == S[i] and i >= fnum; i--)
        {
            bnum++;
        }
        if (fnum == len)
        {
            ans = (len * k) / 2;
            goto L;
        }
        add = (k - 1) * ((fnum + bnum) / 2);
        for (int i = fnum; i < len - bnum; i++)
        {
            if (S[i] == S[i + 1])
            {
                ans++;
                if (i + 1 < len - bnum)
                {
                    rep(j, 3)
                    {
                        if (S[i] != i and S[i + 2] != i)
                        {
                            S[i + 1] = i;
                            break;
                        }
                    }
                }
            }
        }
    }

    ans *= k;
    ans += add + fnum / 2 + bnum / 2;
    //   ans+=
L:
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int n[100000],q[100000][3],n1, q1,minx,i,a=2147483647;
int main() {
	for (int i = 0; i < 100000; i++) {n[i]=a;}
	cin >> n1 >> q1;
	for (i = 0; i < q1; i++) {
		cin >> q[i][0] >> q[i][1] >> q[i][2];
		if (q[i][0]==1) {
			minx=a;
			for (int j = q[i][1]; j <= q[i][2]; j++) {
				minx=min(minx, n[j]);
			}
			cout<<minx<<endl;
		}
		else {n[q[i][1]] = q[i][2];}
	}
	return 0;
}

Measured memory_bytes: 4684
MOD = 10 ** 9 + 7

N, M = map(int, input().split())
A = set([])
for i in range(M):
    A.add(int(input()))

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
    if i-2 not in A:
        dp[i] += dp[i-2]
    if i-1 not in A:
        dp[i] += dp[i-1]
    
    dp[i] %= MOD

print(dp[N])

Measured memory_bytes: 11884
#include<iostream>
using namespace std;
 
int main() {
	int a, b, c;
 
	cin >> a >> b >> c;
	if (a + b + c == 17) {
		if (a == b&&c == 7) {
			cout << "YES";
		}
		if (c == b&&a == 7) {
			cout << "YES";
		}
		if (a == c&&b == 7) {
			cout << "YES";
		}
	}
	else
	{
		cout << "NO";
 
	}
	
		return 0;
	}

Measured memory_bytes: 256
#include<stdio.h>
#define N 100000
typedef struct{
  char Gara[2];
  int su;
}cade;

void quicksort(cade *,int,int);
int partition(cade *,int,int);
int isStable(cade *,cade *,int);

int main(){
  int n,i,a,f,flag=0,j,p;
  cade A[N],E[N];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s %d",A[i].Gara,&A[i].su);
    E[i]=A[i];
  }
  quicksort(A,0,n-1);
  
  for(i=0;i<n;i++){
    f=0;
    for(j=0;j<n;j++){
      if(E[i].su==A[j].su){
        f=1;
        p=0;
        if(E[i].Gara[0]!=A[j].Gara[0]){
          for(a=i-1;a>=0;a--)
            if(A[j].Gara[0]==E[a].Gara[0] && A[j].su==E[a].su)p=1;
          if(p==0)
            flag=1;
        }
      }
      if(f==1)break;
    }
    if(flag==1)break;
  }
  if(isStable(E,A,n))printf("Stable\n");
  else printf("Not stable\n");
  
  for(i=0;i<n;i++)
    printf("%s %d\n",A[i].Gara,A[i].su);
  
  return 0;
}

int partition(cade *A,int p,int r){
  int i,j;
  cade x,a;
  x=A[r];
  i=p-1;
  for(j=p;j<r;j++){
    if(A[j].su<=x.su){
      i++;
      a=A[i];
      A[i]=A[j];
      A[j]=a;
    }
  }
  a=A[i+1];
  A[i+1]=A[r];
  A[r]=a;
  return i+1;
}

void quicksort(cade *A,int p,int r){
  int q;
  if(p<r){
    q=partition(A,p,r);
    quicksort(A,p,q-1);
    quicksort(A,q+1,r);
  }  
}

int isStable(cade in[],cade out[],int n){
  int i,j,a,f,p,flag=0;
  for(i=0;i<n;i++){
    f=0;
    for(j=0;j<n;j++){
      if(in[i].su==out[j].su){
        f=1;
        p=0;
        if(in[i].Gara[0]!=out[j].Gara[0]){
          for(a=i-1;a>=0;a--)
            if(in[a].Gara[0]==out[j].Gara[0] && in[a].su==out[j].su)p=1;
          if(p==0)
            flag=1;
        }
      }
      if(f==1)break;
    }
    if(flag==1)return 0;
  }
  return 1;
}



Measured memory_bytes: 3300
import math
import sys
readline = sys.stdin.buffer.readline
s =int(readline().rstrip().decode())
def gcdsp(x,y,z):
    t =math.gcd(x,y)
    return math.gcd(t,z)
res = 0
for i in range(s):
    for j  in range(s):
        for k  in range(s):
            if i < j and j <= k:
                res += gcdsp(i+1, j+1, k+1)
res1 = int((s + 1)*s/2)
print(6*res+res1)


Measured memory_bytes: 9132
#include <algorithm>
#include <functional>
#include <ios>
#include <iostream>
#include <vector>
#include <numeric>
#include <iomanip>

using namespace std;

int main(int argc, const char *argv[])
{
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  sort(a.begin(), a.end(), greater<int>());
  int sum = accumulate(a.begin(), a.end(), 0);
  double threshold = sum / (4. * m);
  bool ans = true;
  for (int i = 0; i < m; i++) {
    if (a[i] < threshold) {
      ans = false;
      break;
    }
  }

  cout << (ans ? "Yes" : "No") << "\n";
  
  return 0;
}

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

using namespace std;

using ll = long long;

template <typename T>
using matrix = std::vector<std::vector<T>>;

constexpr long long mod = 1e9 + 7;

template <typename T>
matrix<T> modmul(const matrix<T> &l, const matrix<T> &r)
{
    matrix<T> ret(l.size(), std::vector<T>(r[0].size()));
    for (int i = 0; i < (int)l.size(); i++)
    {
        for (int k = 0; k < (int)r.size(); k++)
        {
            for (int j = 0; j < (int)r[0].size(); j++)
            {
                ret[i][j] += l[i][k] * r[k][j] % mod;
                ret[i][j] %= mod;
            }
        }
    }
    return ret;
}

template <typename T>
std::vector<T> modmul(const matrix<T> &a, const std::vector<T> &x)
{
    const int n = a.size();
    const int m = x.size();
    std::vector<T> ret(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            ret[i] += a[i][j] * x[j] % mod;
            ret[i] %= mod;
        }
    }
    return ret;
}

template <typename T>
matrix<T> eye(const int n)
{
    matrix<T> ret(n, std::vector<T>(n));
    for (int i = 0; i < n; i++)
        ret[i][i] = 1;
    return ret;
}

template <typename T>
matrix<T> modpow(matrix<T> x, long long n)
{
    auto ret = eye<T>(x.size());
    while (n)
    {
        if (n & 1)
            ret = modmul(ret, x);
        x = modmul(x, x);
        n /= 2;
    }
    return ret;
}

long long fib(long long n)
{
    if (n <= 1)
        return 1;
    matrix<ll> mat(2, vector<ll>(2, 1));
    mat[1][1] = 0;
    vector<ll> v(2, 1);
    auto ret = modmul(modpow(mat, n - 1), v);
    return ret[0];
}

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

    ll k;
    cin >> k;
    vector<ll> v = {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 13, 15, 16};
    if (k < 10)
    {
        cout << v[k] << endl;
        return 0;
    }
    auto f = [](ll m) {
        return (m % 2 ? (m - 1) / 2 * (m + 1) / 2 + (m + 1) / 2 : m / 2 * (m + 2) / 2);
    };
    // 1,1,2,2,...,n,n,..の何番目か
    ll lb = 1, ub = 3e9;
    while (ub - lb > 1)
    {
        //cout << lb << " " << ub << endl;
        ll m = (lb + ub) / 2;
        if (f(m) >= k)
        {
            ub = m;
        }
        else
        {
            lb = m;
        }
        assert(f(lb) < k && k <= f(ub));
    }
    //cout << lb << " " << ub << endl;
    ll r = k - f(lb);
    // f[ub]の線上, (ub+1)/2個中r個目
    ll cnt = (ub + 1) / 2;
    assert(1 <= r && r <= cnt);
    ll index, i, j;
    if (cnt % 2)
    {
        // 奇数個
        if (r <= (cnt + 1) / 2)
        {
            index = 2 * (r - 1);
        }
        else
        {
            index = cnt - 2 - 2 * (r - (cnt + 1) / 2 - 1);
        }
    }
    else
    {
        // 偶数個
        if (r <= cnt / 2)
        {
            index = 2 * (r - 1);
        }
        else
        {
            index = cnt - 1 - 2 * (r - cnt / 2 - 1);
        }
    }
    i = ub - index;
    j = 1 + index;
    cout << fib(i) * fib(j) % mod << endl;
}



Measured memory_bytes: 3212
import math
n,m = map(int,input().split())
mod = 10**9+7
fact_n = math.factorial(n) % mod
fact_m = math.factorial(m) % mod

if abs(n-m) >= 2:
  print(0)
  exit()
elif n == m:
  print((fact_n * fact_m * 2) % mod)
else:
  print((fact_n * fact_m) % mod)

Measured memory_bytes: 10164
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#define int long 
using namespace std;

signed main() {
	int N;
	cin >> N;
	vector<string> vec(N);
	for(int i = 0;i < N;i++) {
		cin >> vec.at(i);
	}
	bool answer = true;
	for(int i = 0;i < N - 1;i++) {
		for(int j = i + 1;j < N;j++) {
			if(vec.at(i) == vec.at(j)) {
				answer = false;
			}
		}
	}
	for(int i = 0;i < N - 1;i++) {
		if(vec.at(i).at(vec.at(i).size() - 1) != vec.at(i + 1).at(0)) {
			answer = false;
		}
	}
	if(answer == true) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define endl "\n"
#define pii pair<int,int> 
#define ff first
#define ss second
#define mii map<int,int>
#define si set<int>
#define sti stack<int>
#define qi queue<int>
#define vi vector<int>
#define pq priority_queue<int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int M=1e9+7;

int32_t main(){
	IOS;
	int arr[3]={0};
	int a,b; cin>>a>>b;
	a--,b--;
	arr[a]=1;arr[b]=1;
	if(arr[0]==0) cout<<1<<endl;
	else if(arr[1]==0) cout<<2<<endl;
	else cout<<3<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 654321
using namespace std;
int n,rt,size[N],fa[N],cnt=0,sum1,sum2;
int TOT,EN[N],LA[N],NE[N];
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void DFS(int u,int f)
{
	int i,v;
	fa[u]=f;
	size[u]=1;
	for(i=LA[u];i;i=NE[i])
	{
		v=EN[i];
		if(v!=f)
		{
			DFS(v,u);
			size[u]+=size[v];
		}
	}
}
int main()
{
	int i,x,y;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		ADD(x,y);ADD(y,x);
	}
	DFS(1,0);i=n;
	while(i!=1)i=fa[i],cnt++;
	cnt--;i=0;x=n;
	while(i<cnt/2)x=fa[x],i++;
	y=fa[x];
	DFS(x,0);
	sum1=size[y];sum2=n-sum1;
	if(sum1>sum2)cout<<"Fennec";
	else cout<<"Snuke";
}

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

int main(){
    int A, B, K;
    cin >> A >> B >> K;
    int x = B-A +1;
    int y = x-K;

    if(x <= K*2){
        for(int i = 0;i < x;i++)
            cout << i+A << endl;
    }
    else{
        for(int i =0;i < K;i++){
            cout << i+A << endl;
        }
        for(int j = y;j-y < K;j++){
            cout << A+j << endl;
        }
    }
    
}

Measured memory_bytes: 256
l,r = map(int, input().split())
gap = r-l
 
vlist = []
mini = 2019
 
for x in range(gap+1):
    v = (l+x) % 2019
    vlist.append(v)
    if v == 0:
        print(0)
        exit()
 
vlist.sort()

mini = 2019

for i in vlist:
    for j in vlist:
        if i==j:
            pass
        else:
            temp = (i*j) %2019
            mini = min(temp, mini)
            if mini == 0:
                print(0)
                exit()

print(mini)
    
#print((vlist[0]*vlist[1])%2019)
#print((vlist[0]*vlist[1])%2019)

Measured memory_bytes: 3064
function Scanner(input) {
	var self = this;
	self.itemNo = 0;
	self.orgStr = input;
	self.splitedStrs = (function(target) {
		var result = [];
		var target = target.replace(/[\n \t]+/g, " ");
		var strs = target.split(" ");
		for (var i = 0, len = strs.length; i < len; i++) {
			result.push(strs[i]);
		}
		return result;
	}(input));

	self.next = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? result : null;
	}

	self.nextInt = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? parseInt(result) : null;
	}

	self.nextBigDecimal = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? parseFloat(result) : null;
	}
	
	self.nextByte = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? new Int8Array(result) : null;
	}

}

function Main(sc) {

	var A = sc.nextInt();
	var B = sc.nextInt();
	var N = sc.nextInt();
	var max = 0;
	
	var x = (N >= B) ? B - 1 : N;
	max = Math.floor((A * x)/ B) - A * Math.floor(x / B);
	
	console.log(max);
}
Main(new Scanner(require("fs").readFileSync("/dev/stdin", "utf8")));
// Main(new Scanner("33"));

// var str1 = sc.next(); // Stringで取得
// var int1 = sc.nextInt(); // intで取得
// var bd1 = sc.nextBigDecimal(); // BigDecimalで取得
// var byte1 = sc.nextByte(); // byteで取得
// for (var i = 0; i < 1000000000; i++) var toDelay = "aaa"; // 1000msくらいの遅延


Measured memory_bytes: 29548
#include <bits/stdc++.h>
using namespace std;
int main(){
  int h,w,H,W;
  string s,t="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  cin >> h >> w;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> s;
      if(s=="snuke"){
        H=i+1;W=j;
      }
    }
  }
  cout << t[W] << H << endl;
  return 0;
}

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

def check(n):
  cnt = 0
  while n < K:
    n *= 2
    cnt += 1
  return cnt

import decimal

dec = decimal.Decimal

ind = 1
point = 0
x = 1 / N
y = 1 / 2
for i in range(ind, N+1):
  res = check(i)
  point += x * (y**res)
print(point)

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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if (c > a && c < b){
    cout << "Yes" << endl;
  }
  else if (c > b && c < a){
    cout << "Yes" << endl;
  }
  else
    cout << "No" << endl; 
}

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

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

int main()
{
    ll N;
    cin >> N;
    multiset<char> S;
    rep(i,N)
    {
        string tmp;
        cin >> tmp;
        S.insert(tmp[0]);
    }
    /*
    for(multiset<char>::iterator itr = S.begin(); itr != S.end(); ++itr)
    {
        cout << *itr << endl;
    }
    */

    size_t m_count = S.count('M');
    size_t a_count = S.count('A');
    size_t r_count = S.count('R');
    size_t c_count = S.count('C');
    size_t h_count = S.count('H');
    //cout << m_count << " " << a_count << " " << r_count << " " << c_count << " " << h_count << endl;
    
    vector<ll> tmp;
    if( m_count != 0 ) tmp.push_back(m_count);
    if( a_count != 0 ) tmp.push_back(a_count);
    if( r_count != 0 ) tmp.push_back(r_count);
    if( c_count != 0 ) tmp.push_back(c_count);
    if( h_count != 0 ) tmp.push_back(h_count);

    if( tmp.size() < 3 ) cout << 0 << endl;
    else if(tmp.size() == 3)
    {
        ll ans = 1;
        ll TMP = 0;
        rep(i,tmp.size())
        {
            ans *= tmp[i];
            TMP += tmp[i];
        }
        if( ans > TMP )  cout << TMP << endl;
        else  cout << ans << endl;
    }
    else if(tmp.size() == 4)
    {
        ll ans = 0;
        ans += tmp[0] * ( tmp[1] * tmp[2] + tmp[1] * tmp[3] + tmp[2] * tmp[3] );
        ans += tmp[1] * tmp[2] * tmp[3];
        cout << ans << endl;
    }
    else
    {
        ll ans = 0;
        ans += tmp[0] * ( tmp[1] * tmp[2] + tmp[1] * tmp[3] + tmp[1] * tmp[4] +
                          tmp[2] * tmp[3] + tmp[2] * tmp[4] + tmp[3] * tmp[4]);

        ans += tmp[1] * ( tmp[2] * tmp[3] + tmp[2] * tmp[4] + tmp[3] * tmp[4] );
        ans += tmp[2] * tmp[3] * tmp[4];

        cout << ans << endl;
    }
}


Measured memory_bytes: 4992
import math
N,H = list(map(int,input().split()))
data=[]
for i in range(N):
    a,b = list(map(int,input().split()))
    data.append([a,b,i])

s1 = sorted(data,key = lambda x:(-x[1],x[0]))
s2 = sorted(data,key = lambda x:(-x[0],x[1]))
cnt = 0
maxNum = s2[0][2]

for i in range(N):
    if H > 0:
        if s1[i][1] > s2[0][0]:
            if s1[i][2] == maxNum:
                continue
            else:
                H -= s1[i][1]
                cnt += 1
        else:
            H -= s2[0][1]
            cnt += 1
            break
        
    else:
        print(cnt)
        exit()
else:
    H -= s2[0][1]
    cnt += 1
    


if H > 0:
    print(cnt + math.ceil(H/s2[0][0]))
else:
    print(cnt)

Measured memory_bytes: 35768
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(int)(m);(i)<(int)(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int X, Y, A, B, C; cin >> X >> Y >> A >> B >> C;
	vector<ll>p(A), q(B);
	priority_queue<ll, vector<ll>, greater<ll>>r;
	rep(i, 0, A)cin >> p[i];
	rep(i, 0, B)cin >> q[i];
	rep(i, 0, C) {
		ll a; cin >> a;
		r.push(a);
	}
	priority_queue<ll, vector<ll>, greater<ll>>cnt;
	sort(all(p),greater<ll>());
	sort(all(q), greater<ll>());
	rep(i, 0, X) {
		cnt.push(p[i]);
	}
	rep(i, 0, Y) {
		cnt.push(q[i]);
	}
	rep(i, 0, C) {
		ll x = r.top();
		r.pop();
		if (cnt.top() < x) {
			cnt.pop();
			cnt.push(x);
		}
	}
	ll ans = 0;
	rep(i, 0, X + Y) {
		ans += cnt.top();
		cnt.pop();
	}
	cout << ans << "\n";

	return 0;
}

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

public class Main {
    static final int MAX = 1000 * 1000;

    public static void main(String[] args) throws java.io.IOException {
        boolean[] prime = new boolean[MAX + 1];
        Scanner sc = new Scanner(System.in);
        prime[1] = true;
        prime[2] = true;
        prime[3] = true;
        prime[5] = true;
        for (int i = 2; i <= 5; i++) {
            if (prime[i]) {
                for (int j = 2; j <= MAX / i; j++) {
                    if (prime[j]) {
                        prime[i * j] = true;
                    }
                }
            }
        }
        while (true) {
            int m = sc.nextInt();
            if (m == 0)
                break;
            int n = sc.nextInt();
            int ans = 0;
            for (int i = m; i <= n; i++) {
                if (prime[i])
                    ans++;
            }
            System.out.println(ans);
        }

    }
}

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

using namespace std;

class DisjointSet 
{
    unordered_map<int, int> parent;
    unordered_map<int, int> rank;
    
    public:
        void makeSet(vector<int> const &universe)
        {
            for(int i : universe)
            {
                parent[i] = i;
                rank[i] = 0;
            }
        }
        
        int find(int k)
        {
            return (parent[k] == k) ? k : parent[k] = find(parent[k]);
        }
        
        bool isSameSet(int x, int y)
        {
            return find(x) == find(y);
        }
        
        void unionSet(int a, int b)
        {
            int x = find(a);
            int y = find(b);
            
            if(x == y)
            {
                return;
            }
            if(rank[x] > rank[y])
            {
                parent[y] = x;
            } 
            else if(rank[x] < rank[y])
            {
                parent[x] = y;
            }
            else
            {
                parent[x] = y;
                rank[y]++;
            }
        }
};

int main() 
{
    int n, q, c, x, y;
    scanf("%d %d", &n, &q);
    
    vector<int> universe;
    
    for(int i = 0; i < n; i++)
    {
        universe.emplace_back(i);
    }
    
    DisjointSet ds;
    ds.makeSet(universe);
    
    for(int i = 0; i < q; i++)
    {
        scanf("%d %d %d", &c, &x, &y);
        
        if(c == 0)
        {
            ds.unionSet(x, y);
        }
        else if(c == 1)
        {
            printf("%d\n", ds.isSameSet(x, y) ? 1 : 0);
        }
    }
    
    return 0;
}


Measured memory_bytes: 3688
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define loop(i,n) rep(i,0,n)
using namespace std;
using ll = long long;
int main(){
    int n,k,cnt=0;
    cin >> n >> k;
    loop(i,n){
        int h;
        cin >> h;
        if(h>=k)++cnt;
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>

int main(void){
int w,h;
int j,i;

while(1){
  scanf("%d %d",&h,&w);
  if(w == 0 && h == 0 )break;
  for(i=0;i<h;i++){
  for(j=0;j<w;j++){
    if(i==0 || i==(h-1) || j==0 || j==(w-1)){
      printf("#");
    }else {
      printf(".");
    }
  }
  printf("\n");
  }
  printf("\n");
}

return 0;
}

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

int main(){
	int h,w;
	while(cin >> h >> w,h*w){
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(i == 0 || j == 0 || i == h-1 || j == w-1) cout << "#";
				else cout << ".";
			}
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define inf 2e18
using namespace std;
typedef long long ll;
ll arr[2000005];
int main()
{
    //freopen("in.txt", "r", stdin);
    ll n;
    cin>>n;
    double x=n/1.08;
    ll k=ceil(x);
    double p=(double)k*1.08;
    if(floor(p)==n){
        cout<<k<<endl;
    }
    else{
        cout<<":("<<endl;
    }
}



Measured memory_bytes: 256
import math

n=int(input())
s=input()

l=[]
for i in range(26):
	l.append(0)

for i in range(n):
	l[ord(s[i])-97]+=1

p=1000000007
ans=1
for i in range(26):
	ans*=(l[i]+1)%p

ans=ans%p

ans-=1

print(ans)

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

const int mod = 1000000007;
const int inv3 = (mod + 1) / 3;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
int fastpow(int a, int b, int res = 1) {
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);
	return res;
}

const int MAXN = 1000010;
int inv[MAXN], n;
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n;
	*inv = inv[1] = 1;
	for (int i = 2; i <= n; ++i)
		inv[i] = mul(inv[mod % i], mod - mod / i);
	int ans = 0, now = 1;
	for (int i = 1; i <= n; ++i) {
		now = mul(now, inv3);
		reduce(ans += mul(inv[n - i + 1], now) - mod);
	}
	std::cout << fastpow(n, mod - 2, ans) << '\n';
	return 0;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(container) container.begin(),container.end()
#define fast ios::sync_with_stdio(0); cin.tie(0)
// #ifndef ONLINE_JUDGE
// #include "debug.cpp"
// #endif
#define int long long
const int mod = 1e9+7;  
int power(int a,int b) { if(b==0) return 1; int res = power(a,b/2); if(b&1) return res * res * a; else return res * res; }


int32_t main(){
    
  fast;
  int n,k; cin >> n >> k;
  int ar[n+1] = {0};

  for(int i=1;i<=n;i++) cin >> ar[i], ar[i]+=ar[i-1];
  int maxx = -1e18;
  for(int i=k;i<=n;i++) maxx = max(maxx,ar[i]-ar[i-k]);

  cout <<  fixed << setprecision(10) <<  (maxx+k)/2.0;

  return 0;
}

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

int main(){
	string s;
	cin >> s;
	static int dp[200010][3] = {};
	for(int i = 1 ; i <= s.size() ; i ++){
		if(i == 1 || s[i-2] != s[i-1]){
			dp[i][1] = max ( dp[i][1] , dp[i-1][1]+1 );
		}
		dp[i][1] = max ( dp[i][1] , dp[i-1][2]+1 );
		if(i >= 2)dp[i][2] = max ( dp[i][2] , dp[i-2][1]+1 );
		if(i >= 4 && (s[i-4] != s[i-2] || s[i-3] != s[i-1])){
			dp[i][2] = max ( dp[i][2] , dp[i-2][2]+1 );
		}
	}
	cout << max ( dp[s.size()][1] , dp[s.size()][2] ) << endl;
}

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

typedef long long int ll;

int main(){
	int n;cin >> n;
	vector<int> v(n);
	int maxx = INT_MIN;
	for(int i = 0;i < n;i++){
		cin >> v[i];
		if(v[i] > maxx)maxx = v[i];
	}
	int ans = 0;
	for(int i = maxx;i > 0;i--){
		bool last = false;
		for(int j = 0;j < n;j++){
			if(v[j] == i && last == false){
				ans++;
				v[j]--;
				last = true;
			}
			else if(v[j] == i && last)v[j]--;
			else if(v[j] != i)last = false;
		}
	}
	cout << ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <cctype>
#include <queue>
#include <set>
#include <list>
#define PI 3.141592653
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;

int main() {
	string s;
	int q;
	cin >> s >> q;
	deque<char> qe;
	for (char c : s)qe.push_back(c);
	bool flip = false;
	rep(i, 0, q) {
		int in;
		cin >> in;
		if (in == 1) {
			flip = !flip;
		}
		else {
			int F;char C;
			cin >> F >> C;
			if (flip) F = 3 - F;
			if (F == 1) qe.push_front(C);
			else qe.push_back(C);
		}
	}
	if (flip) reverse(qe.begin(), qe.end());
	string ans;
	for (char c : qe)ans += c;
	cout << ans << endl;
}

Measured memory_bytes: 1412
n = int(input())
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
c = a1[0] + sum(a2)
ans = c
for i in range(1, n):
    c = c + a1[i] - a2[i - 1]
    ans = max(ans, c)
print(ans)

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

struct StronglyConnectedComponent {
	const int V;
	vector<vector<int>> G, revG;
	vector<int> id;
	StronglyConnectedComponent(const int V) :
		V(V),
		G(vector<vector<int>>(V, vector<int>())),
		revG(vector<vector<int>>(V, vector<int>())),
		id(vector<int>(V))
		{}
	void addEdge(int from, int to) {
		G[from].push_back(to);
		revG[to].push_back(from);
	}
	void build() {
		vector<bool> used(V, false);
		stack<int> st;
		for(int from = 0; from < V; ++from) {
			if(not used[from]) {
				dfs(from, used, st);
			}
		}
		int num = 0;
		while(st.size()) {
			int from = st.top();
			st.pop();
			if(used[from]) {
				revdfs(from, num, used);
				++num;
			}
		}
	}
	void dfs(int from, vector<bool> &used, stack<int> &st) {
		used[from] = true;
		for(int to : G[from]) {
			if(not used[to]) {
				dfs(to, used, st);
			}
		}
		st.push(from);
	}
	void revdfs(int from, int num, vector<bool> &used) {
		used[from] = false;
		id[from] = num;
		for(int to : revG[from]) {
			if(used[to]) {
				revdfs(to, num, used);
			}
		}
	}
	int get(int x) {
		return id[x];
	}
};

int main() {
	int V, E; cin >> V >> E;
	StronglyConnectedComponent scc(V);
	while(E--) {
		int s, t; cin >> s >> t;
		scc.addEdge(s, t);
	}
	scc.build();
	int Q; cin >> Q;
	while(Q--) {
		int u, v; cin >> u >> v;
		if(scc.get(u) == scc.get(v)) {
			cout << 1 << '\n';
		} else {
			cout << 0 << '\n';
		}
	}
}



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

void ink(int,int,int);
void change(int,int,int);

char paper[10][10]={0};

int main(void){
	int white=0,max_ink=0;

	for(int x,y,size;scanf("%d,%d,%d",&x,&y,&size)!=EOF;)
		ink(x,y,size);

	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			if(!paper[i][j])
				white++;
			else
				max_ink=std::max(max_ink,int(paper[i][j]));

	printf("%d\n%d\n",white,max_ink);
	return 0;
}

void ink(int x,int y,int size){
	switch(size){
		case 1:
			ink(x,y,2);
			for(int i=-1;i<=1;i+=2)
				for(int j=-1;j<=1;j+=2)
					change(x+i,y+j,-1);
			break;
		case 2:
			for(int i=-1;i<=1;i++)
				for(int j=-1;j<=1;j++)
					change(x+i,y+j,1);
			break;
		case 3:
			ink(x,y,2);
			change(x-2,y,1);
			change(x+2,y,1);
			change(x,y-2,1);
			change(x,y+2,1);
			break;
	}
}

void change(int x,int y,int inc){
	if(x>=0&&x<10&&y>=0&&y<10)
		paper[x][y]+=inc;
}

Measured memory_bytes: 1032
#include <bits/stdc++.h>
using namespace std ;
using ll=long long ;
int main(){
 string a , b;
   cin >> a >> b;
 
   int ans=0 ;
   for(int i=0 ;i<a.size() ;i++)
   {
       if(a[i] != b[i]) ans++ ;
   }
 
      cout << ans ;
 return 0 ;
}


Measured memory_bytes: 3860
def resolve():
	n = int(input())
	dp = [[0]*3 for _ in range(n+1)]
	for i in range(1, n+1):
		nums = list(map(int, input().split()))
		for j in range(3):
			for k in range(3):
				if j == k:
					continue
				dp[i][j] = max(dp[i][j], nums[j] + dp[i-1][k])
	print(max(dp[-1]))
resolve()

Measured memory_bytes: 58932
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define mpr make_pair
#define fi first
#define se second
using ll=long long int;
static const ll mod = 1e9 + 7;
static const ll INF = 1LL << 50;
using namespace std;

int main(){
	string s;
	cin>>s;
	char key=s[0],key2=s[1];
	bool judge=true;
	for(int i=0;i<s.size();i+=2){
		if(s[i]!=key)judge=false;
	}
	if(judge){
		for(int i=1;i<s.size();i+=2){
			if(s[i]!=key2)judge=false;
		}
	}
	int cnt=0;
	if(!judge)cnt=s.size()-2-(s[0]==s[s.size()-1]);
	else cnt=0;
	if(cnt%2==0)cout<<"Second"<<endl;
	else cout<<"First"<<endl;
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define local
//if you find any bug in my code, please tell me.
const int N=100010;
int a[N];
int main()
{
#ifdef local
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
#endif
    int n,i,maxa,ans,d,mind;
    maxa=-1,ans=mind=0x3f3f3f3f;
    cin>>n;
    for(i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        if(maxa<a[i]) maxa=a[i];
    }
    for(i=1; i<=n; i++)
    {
        d=abs(maxa-2*a[i]);
        if(d<=mind)
        {
            mind=d;
            ans=a[i];
        }
    }
    printf("%d %d",maxa,ans);
    return 0;
}

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

int main(){

    int N;
    cin>> N;

    string T,S;
    cin >> T >> S;

    string ans;

    for (size_t i = 0; i < N; i++)
    {
        ans+=T[i];
        ans+=S[i];
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
from collections import deque
n,q=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a].append(b)
  edge[b].append(a)

x_list=[0]*(n+1)
for i in range(q):
  p,x1=map(int,input().split())
  x_list[p]+=x1

def bfs(x,x_list):
  qu=deque([])
  qu.append(0)
  qu.append(x)
  node_number=1
  while qu:
    pre=qu.popleft()
    node_number = qu.popleft()
    nodes = edge[node_number]
    for i in nodes:
      if pre != i:
        qu.append(node_number)
        qu.append(i)
        x_list[i]+=x_list[node_number]
      else:continue
  return x_list
answer=bfs(1,x_list)[1:]
print(*answer)

Measured memory_bytes: 56172
// ConsoleApplication7.cpp : ??????????????? ??¢????????±????????§????????¨????????? ?????????????????????????????????
//

#include <stdio.h>


int main(int argc, char* argv[])
{
	int i;
	int a, b;
	double af, bf;
	char temp[22];

	fgets(temp, sizeof(temp), stdin);
	sscanf(temp, "%d %d", &a, &b);

	af = (double)a;
	bf = (double)b;
	
	printf("%d %d %.5f\n", a / b, a % b, af / bf);
	
	return 0;
}

Measured memory_bytes: 2708
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

bool areSameArray(int *A, int *B, int n) {
	bool answer = true;
	for (int i = 0; i < n; i++) {
		if (A[i] != B[i]) {
			answer = false;
			break;
		}
	}
	return answer;
}

int main()
{
	int n;
	cin >> n;
	int *numArray = new int[n];
	for (int i = 0; i < n; i++) {
		numArray[i] = i + 1;
	}
	int *P = new int[n];
	int *Q = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> P[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> Q[i];
	}

	int countP = 0;
	int countQ = 0;
	int count = 0;
	do {
		if (areSameArray(numArray, P, n) == true) {
			countP = count;
		}
		if (areSameArray(numArray, Q, n) == true) {
			countQ = count;
		}
		count++;
	} while (next_permutation(numArray, numArray + n));
	cout << abs(countP - countQ) << endl;
	return 0;
}

Measured memory_bytes: 256
sx,sy,tx,ty  = list(map(int,input().split()))
string = ""  
if sy == ty:
  string += "R"*(tx-sx)
  string += "D"+"L"*(tx-sx)+"U"
  string += "U"+"R"*(tx-sx)+"D"
  string += "RUU"+"L"*(tx-sx+2)+"DDR"
  if sx > tx:
    string.replace("R","X").replace("L","R").replace("X","L")
elif sy == ty:
  string += "U"*(tx-sx)
  string += "R"+"D"*(tx-sx)+"L"
  string += "L"+"U"*(tx-sx)+"R"
  string += "ULL"+"D"*(tx-sx+2)+"RRU"
  if sy > ty:
    string.replace("D","X").replace("U","D").replace("X","U")
else:
  g = []
  if sx<tx:
    g += ["R","L"]
  else:
    g += ["L","R"]
  
  if sy<ty:
    g += ["U","D"]
  else:
    g += ["D","U"]
  
  dx,dy = abs(tx-sx),abs(ty-sy)
  
  string += g[0]*dx+g[2]*dy
  string += g[1]*dx+g[3]*dy
  string += g[3]+g[0]+g[0]*dx+g[2]*dy+g[2]+g[1]
  string += g[2]+g[1]+g[1]*dx+g[3]*dy+g[3]+g[0]
  
print(string)


Measured memory_bytes: 3064
while 1:
    n = int(raw_input())
    if not n: break
    c = [0 for i in xrange(7)]
    for i in xrange(n):
        age = int(raw_input())
        if age < 10: c[0] += 1
        elif 10 <= age < 20: c[1] += 1
        elif 20 <= age < 30: c[2] += 1
        elif 30 <= age < 40: c[3] += 1
        elif 40 <= age < 50: c[4] += 1
        elif 50 <= age < 60: c[5] += 1
        else: c[6] += 1
    for i in xrange(len(c)):
        print c[i]

Measured memory_bytes: 5000
#include<iostream>
int main()
{
	char s[3][101];
	for(int i = 0; i < 3; i++)
	{
		std::cin >> s[i];
	}
	int end[3];
	for(int i = 0; i < 3; i++)
	{
		for(int j = 0;; j++)
		{
			if(s[i][j] == '\0')
			{
				end[i] = j;
				break;
			}
		}
	}
	int num[3] {0, 0, 0};
	while(true)
	{
		static int turn = 0;
		switch(s[turn][num[turn]])
		{
			case 'a':
				num[turn]++;
				turn = 0;
				break;
			case 'b':
				num[turn]++;
				turn = 1;
				break;
			case 'c':
				num[turn]++;
				turn = 2;
				break;
		}
		if(num[turn] == end[turn])
		{
			std::cout << (turn == 0 ? 'A' : turn == 1 ? 'B' : 'C') << std::endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define ll  long long 
#define dl long double
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
int main ()
{
    
    FAST
    ll t ;
    cin >>t;
    string s ;
    cin>>s;
    int w=0,r=0,a=0,b=0;
    for (int i = 0 ;i<s.size();i++)
    {
        if (s[i]=='W'  )
            w++;
        else
            r++;
    }
    int i = 0 ;
    for ( i = 0 ;i<r;i++)
    {
        if (s[i]=='W'  )
            a++;
      
    }
    for (int j=i ;j<w;j++)
    {
        if (s[j]=='R'  )
            b++;
    }
    cout<<max(a,b)<<endl;
    return 0;

}

Measured memory_bytes: 3704