akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define loop(n, i) for(int i=0;i<n;i++)
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;
using namespace std;
using ll = long long;
template <class T>
using V = vector<T>;
using P = pair<ll, ll>;


void solve(long long N, long long Q, std::string S, std::vector<long long> l, std::vector<long long> r){
    V<int> C(N + 10);
    loop (N, i) {
        if (i == 0) continue;
        C[i] = C[i - 1];
        if (S[i - 1] == 'A' && S[i] == 'C') {
            C[i] += 1;
        }
    }

    loop (Q, i) {
        r[i]--;
        l[i]--;
        int ans = C[r[i]] - C[l[i]];
        cout << ans << endl;
    }
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long Q;
    scanf("%lld",&Q);
    std::string S;
    std::cin >> S;
    std::vector<long long> l(Q);
    std::vector<long long> r(Q);
    for(int i = 0 ; i < Q ; i++){
        scanf("%lld",&l[i]);
        scanf("%lld",&r[i]);
    }
    solve(N, Q, S, std::move(l), std::move(r));
    return 0;
}



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

long long f(long long b,long long n){
    if(n<b){
        return n;
    }else{
        return f(b,n/b)+n%b;
    }
}

int main() {
long long n,s,m,l=-1;
cin>>n>>s;
m=n-s;
if(m<0){
    cout<<-1<<endl;
    return 0;
}else if(m==0){
    cout<<n+1<<endl;
    return 0;
}

for(long long i=1;i*i<=m;i++){
    if(m%i==0){
        if(f(i+1,n)==s){
            cout<<i+1<<endl;
            return 0;
        }else if(f(m/i+1,n)==s){
            l=m/i+1;
        }
    }
}
cout<<l<<endl;
	return 0;
}

Measured memory_bytes: 256
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, X, M = map(int, input().split())
    L = [X]
    D = [0] * M
    D[X] = 1
    k = 2
    while k < N + 1:

        # k回目
        l = L[-1] ** 2 % M


        if D[l] != 0:
            n = N - k+1  # 残り回数
            one_cycle = k - D[l]
            mass = sum(L[D[l]-1:])
            ans = n//one_cycle *mass
            res = sum(L[D[l]-1:D[l]+(n%one_cycle)-1])
            print(ans +res +sum(L))
            exit()

        if l == 0:
            print(sum(L))
            exit()

        L.append(l)
        D[l] =k
        k += 1

    print(sum(L))


if __name__ == "__main__":
    main()

# \n


Measured memory_bytes: 69468
#include <cmath>
#include <cstdio>
using namespace std;
int main(){
	double a, b, x, pi = 3.14159265358979;
	scanf("%lf %lf %lf", &a, &b, &x);
	if (2 * x < a * a * b){
		printf("%.12lf\n", 90 - atan((2 * x) / (a * b * b)) * 180 / pi);
	}else if (2 * x > a * a * b){
		printf("%.12lf\n", atan((a * a * b - x) * 2 / (a * a * a)) * 180 / pi);
	}else{
		printf("%.12lf\n", atan(a / b) * 180 / pi);
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
string a;
vector<int> b(4);
int main(){
    cin>>a;
  for(int i=0;i<4;i++){
      b.at(i)=a.at(i)-'0';
  }
  int w=b.at(0);
  int x=b.at(1);
  int y=b.at(2);
  int z=b.at(3);
  if(w+x+y+z==7){
      cout<<w<<'+'<<x<<'+'<<y<<'+'<<z;
  }
  else if(w+x+y-z==7){
      cout<<w<<'+'<<x<<'+'<<y<<'-'<<z;
  }else if(w+x-y+z==7){
      cout<<w<<'+'<<x<<'-'<<y<<'+'<<z;
  }else if(w+x-y-z==7){
      cout<<w<<'+'<<x<<'-'<<y<<'-'<<z;
  }else if(w-x+y+z==7){
      cout<<w<<'-'<<x<<'+'<<y<<'+'<<z;
  }else if(w-x+y-z==7){
      cout<<w<<'-'<<x<<'+'<<y<<'-'<<z;
  }else if(w-x-y+z==7){
      cout<<w<<'-'<<x<<'-'<<y<<'+'<<z;
  }
  else cout<<w<<'-'<<x<<'-'<<y<<'-'<<z;
  cout<<"=7"<<endl;
}

Measured memory_bytes: 256
n,m = map(int,input().split())
h = list(map(int,input().split()))
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
f = [[0 for i in range(0)]for _ in range(n)]
for i in range(m):
    f[a[i]-1].append(b[i]-1)
    f[b[i]-1].append(a[i]-1)
ans = 0
for i in range(n):
    flag = 1
    for j in range(len(f[i])):
        if h[i] <= h[f[i][j]]:
            flag = 0
            break
    if flag:
        ans += 1
print(ans)

Measured memory_bytes: 37464
#include <bits/stdc++.h>
using namespace std;
int main() {
  int W, a, b;
  cin >> W >> a >> b;
  int c = a - b;
  if (c < 0) {c *= -1;}
  if (c <= W) {cout << 0 << endl;}
  else {cout << c - W << endl;}
}

Measured memory_bytes: 3616
#include<iostream>
using namespace std;
int main(int argc, char const *argv[]){
    int A, B, C, X;
    cin >>A>>B>>C>>X;
    int count=0;
    
    for (int i = 0;i <=A; ++i){
        for (int j = 0;j <=B; ++j){
            for (int k = 0;k <=C; ++k){
                if (500*i+100*j+50*k==X)count++;
            }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long
signed main(){
  int x,y,a,b,c,res=0;
  cin>>x>>y>>a>>b>>c;
  vector<int> p(a),q(b);
  priority_queue<int> que;
  for(auto& i:p)cin>>i;
  for(auto& i:q)cin>>i;
  for(int i=0,k;i<c;++i){
    cin>>k;
    que.push(k);
  }
  sort(p.rbegin(),p.rend());
  sort(q.rbegin(),q.rend());
  for(int i=0;i<x;++i)que.push(p[i]);
  for(int i=0;i<y;++i)que.push(q[i]);
  for(int i=0;i<x+y;++i)res+=que.top(),que.pop();
  cout<<res;
}

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

using namespace std;

int main(){
    int N, L;
    cin >> N >> L;
    string s[N];
    for(int i=0; i<N; i++) cin >> s[i];
    sort(s,s+N);
    for(int i=0; i<N; i++) cout << s[i];
    cout << endl;
}

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

using namespace std;

const int mod = 1000000009;

struct Mat{
  int v[80][80];
  int h,w;

  Mat():h(0),w(0){}
  Mat(int h, int w):h(h),w(w){}
};

vector<Mat> A2;

Mat operator * (const Mat &a, const Mat &b){
  Mat c(a.h,b.w);
  for(int i = 0; i < a.h; ++i){
    for(int j = 0; j <= i && j <= a.h - i - 1; ++j){
      c.v[i][j] = 0;
      for(int k = 0; k < a.w; ++k){
        c.v[i][j] += (long long)a.v[i][k] * b.v[k][j] % mod;
        c.v[i][j] %= mod;
      }
      c.v[j][i] = c.v[c.h-i-1][c.w-j-1] = c.v[c.w-j-1][c.w-i-1] = c.v[i][j];
    }
  }
  return c;
}


Mat power(const Mat &a, long long e)
{
  Mat x = a;
  Mat ret(a.h,a.w);
  
  for(int i = 0; i < ret.h; ++i) for(int j = 0; j < ret.w; ++j)
      ret.v[i][j] = i == j ? 1 : 0;
  A2[0] = ret;

  int ref = 1;
  while(e){if(e&1)ret=ret*A2[ref];++ref;e>>=1;};
  
  return ret;
}

int solve(int w, long long h, int n, const vector<pair<long long, int> > &st)
{
  long long pre = 0;
  Mat b1(w,1), b2(w,1);
  Mat A(w,w);

  for(int i = 0; i < w; ++i){
    b1.v[i][0] = 0;
    b2.v[i][0] = 0;
  }
  b1.v[0][0] = 1;
  for(int i = 0; i < w; ++i){
    for(int j = 0; j < w; ++j){
      if( abs(i-j) <= 1 ) A.v[i][j] = 1;
      else A.v[i][j] = 0;
    }
  }

  A2.clear();
  A2.push_back(A);
  A2.push_back(A);
  int maxit = 0;
  long long tmp_h = h;
  while(tmp_h>0){++maxit;tmp_h>>=1;}
  maxit+=2;
  for(int i = 2; i < maxit; ++i){
    A2.push_back( A2[i-1] * A2[i-1] );
  }
  
  for(int i = 0; i < n; ++i){
    Mat Ae = power(A, st[i].first - pre);
    for(int j = 0; j < w; ++j){
      for(int k = 0; k < w; ++k){
        b2.v[j][0] += (long long)Ae.v[j][k] * b1.v[k][0] % mod;
        b2.v[j][0] %= mod;
      }
    }

    for(int j = 0; j < w; ++j){
      b1.v[j][0] = j!=st[i].second?b2.v[j][0]:0;
      b2.v[j][0] = 0;
    }

    pre = st[i].first;
  }

  return b1.v[w-1][0];
}

int main()
{
  int W,N;
  long long H;
  int tc = 1;

  while( cin >> W >> H >> N ){
    if( W == 0 && H == 0 && N == 0 ) break;
    
    vector<pair<long long,int> > stones;
    for(int i = 0; i < N; ++i){
      int x;
      long long y;
      cin >> x >> y;
      stones.push_back(make_pair(y-1,x-1));
    }
    stones.push_back(make_pair(H-1,W));
    sort(stones.begin(),stones.end());
    
    int res = solve(W,H,N+1,stones);

    cout << "Case " << tc << ": " << res << endl;
    ++tc;
  }
  return 0;
}

Measured memory_bytes: 2752
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int q;

int main(void){
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		ll a,b;
		scanf("%lld%lld",&a,&b);
		ll sc=a*b;
		ll l=0,r=1LL<<30;
		while(l+1<r){
			ll mid=(l+r)/2LL;
			if(mid*mid<=sc)l=mid;
			else r=mid;
		}
		ll ans=0;
		if(l>0){
			ans+=(l-1)*2LL;
		}
		if(l*(l+1)<sc){
			ans+=2;
			if(l==a && l+1==b)ans--;
			else if(l+1==a && l==b)ans--;
			else{
				if(a<=l)ans--;
				if(b<=l)ans--;
			}
		}else if(l*l<sc){
			ans++;
			if(l==a && l==b)ans--;
			else{
				if(a<=l)ans--;
				if(b<=l)ans--;
			}
		}else{
			if(a<l)ans--;
			if(b<l)ans--;
		}
		
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
bool odd(const int &n) { return n & 1; }
bool even(const int &n) { return ~n & 1; }
template<typename T> int len(const T &v) { return v.size(); }
template<typename T = int> T in() { T x; cin >> x; return x; }
template<typename T = int> T in(T &&x) { T z(forward<T>(x)); cin >> z; return z; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> istream &operator>>(istream &is, pair<A, B> &p) { return is >> p.first >> p.second; }
template<typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : "\n"); return os; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : " "); return os; }
template<typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << p.first << ' ' << p.second; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
// clang-format on

main() {
  int n = in();
  vector<int> a(n);
  cin >> a;
  int q = in();
  while (q--) {
    int b, m, e;
    cin >> b >> m >> e;
    rotate(a.begin() + b, a.begin() + m, a.begin() + e);
  }
  cout << a << endl;
}



Measured memory_bytes: 3148
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const int EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 30);
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string S;
	cin >> S;
	int p = SZ(S) / 2;
	REP(i,SZ(S)) {
		if (S[i] == 'p')p--;
	}
	cout << p << endl;
	PAU;
	return 0;
}


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

vector<vector<int>> e;
vector<ll> num;
int k;

void dfs(int r){
    int cnt=0;
    for(int i=0; i<e[r].size(); i++){
        if(num[e[r][i]]==-1e+9){
            num[e[r][i]] = k-1-cnt-(r!=0);
            dfs(e[r][i]);
            cnt++;
        }
    }
}


int main(){
    int n;
    cin>>n>>k;
    e.resize(n);
    num.resize(n,-1e+9);
    rep(i,n-1){
        int a,b;
        cin>>a>>b;
        a--;b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    num[0]=k;
    dfs(0);
    ll ans=1;
    rep(i,n){
        ans=(ans*num[i])%ll(1e+9+7);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fo(i,s,e) for( i=s;i<e;i++)
#define rfo(i,s,e) for(i=s;i>e;i--)
#define LL long long int 
const LL MOD=1e9+7;
#define pb push_back
#define pob pop_back()
#define sp " "
#define ff first
#define ss second
//            When something is important enough, you do it even if the odds are not in your favor.

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    // code goes here
    int t=1;//cin>>t;
    while(t--){
      LL n;cin>>n;
      string s;cin>>s;
      std::vector<LL> v;
      for(auto x:s){
        v.pb(x-'a');
      }
      cout<<unique(v.begin(), v.end())-v.begin();
    }
    return 0;
}

Measured memory_bytes: 4464
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

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;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    string s, t;
    cin >> s >> t;
    if (s == t) {
        cout << "Yes" << endl;
        return 0;
    }
    for (int i = 0; i < s.size(); i++) {
        char a = s.back();
        s.insert(s.begin(), a);
        s.pop_back();
        if (s == t) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    return max(A+B, A-B, A*B)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    print(solve(A, B))

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use itertools::Itertools;
use std::process::exit;
use std::cmp::*;
use num::*;
use num::integer::Roots;
use std::str::FromStr;
use std::io::stdin;

fn main() {
    input!{
    a:String,
    }
    let mut a=a.chars().collect_vec();
    a.push('R');
    let mut v=vec![0;a.len()];
    let mut x='R';
    let mut y=0;
    let mut z=0;
    for i in 0..a.len(){
        if a[i]==x{
            z+=1;
        }
        else if x=='R'{
            y=i;
            v[i]+=z/2;
            v[i-1]+=z-z/2;
            z=1;
            x='L';
        }
        else {
            v[y]+=z-z/2;
            v[y-1]+=z/2;
            z=1;
            x='R'
        }
    }
    for i in 0..a.len()-2 {
        print!("{} ",v[i])
    }
    println!("{}",v[a.len()-2])
}
















/// 必要に応じて標準入力から一行入力を受け取り、空白で区切って保持しておく構造体
/// cinのRust版的な
pub struct Scanner {
    buf: std::collections::VecDeque<String>,
}

impl Scanner {
    /// 新しいScannerを生成する
    /// mutを付けないと意味なし
    pub fn new() -> Self {
        Self {
            buf: std::collections::VecDeque::new(),
        }
    }

    /// 区切られた入力を持っていない時に、次の一行を受け取り、空白区切りをして保持する。
    ///
    /// # Panics
    /// - 5行以上連続して空行が入力された場合はパニックする
    fn scan_line(&mut self) {
        let mut flag = 0;
        while self.buf.is_empty() {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            let mut iter = s.split_whitespace().peekable();
            if iter.peek().is_none() {
                if flag >= 5 {
                    panic!("There is no input!");
                }
                flag += 1;
                continue;
            }

            for si in iter {
                self.buf.push_back(si.to_string());
            }
        }
    }

    /// 次のトークンを、FromStrを持ち、Stringからパースできる任意の型に変換して返す。
    ///
    /// # Panics
    /// - パースに失敗した場合はパニックする
    ///
    /// # Examples
    /// ```rust
    /// use at_coder::basic::scanner::Scanner;
    /// let mut sc = Scanner::new();
    /// let m = sc.next::<bool>();
    /// ```
    pub fn next<T: std::str::FromStr>(&mut self) -> T {
        self.scan_line();
        self.buf
            .pop_front()
            .unwrap()
            .parse()
            .unwrap_or_else(|_| panic!("Couldn't parse!"))
    }

    pub fn next_usize(&mut self) -> usize {
        self.next()
    }

    pub fn next_isize(&mut self) -> isize {
        self.next()
    }

    pub fn next_chars(&mut self) -> Vec<char> {
        self.next::<String>().chars().collect()
    }

    pub fn next_string(&mut self) -> String {
        self.next()
    }

    pub fn next_char(&mut self) -> char {
        self.next()
    }

    pub fn next_float(&mut self) -> f64 {
        self.next()
    }
}


Measured memory_bytes: 3204
# Cycle Detection for a Directed Graph
[vertex, edge] = list(map(int, input("").split()))
array = [[0 for j in range(vertex)] for i in range(vertex)]

for i in range(edge):
    data = list(map(int, input("").split()))
    array[data[0]][data[1]] = 1

visited = [0 for j in range(vertex)]
result = 0

def dfs(node, goal):
    for t in range(vertex):
        visited[node] = 1
        if array[node][t] != 0 and t == goal:
            global result
            result = 1
        if array[node][t] != 0 and visited[t] == 0:
            dfs(t, goal)

for i in range(vertex):
    visited = [0 for j in range(vertex)]
    dfs(i,i)
    if result == 1:
        print(1)
        break

if result == 0:
    print(0)





Measured memory_bytes: 5720
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#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>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

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

#define MP make_pair
#define EACH(i,c) for(auto i: c)
#define SORT(c) sort((c).begin(),(c).end())

#define ALL(a)  (a).begin(),(a).end()

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int K, A, B;
	cin >> K >> A >> B;

	FOR(i, A, B + 1){
		if((i % K) == 0){
			cout << "OK" << endl;
			return 0;
		}
	}

	cout << "NG" << endl;


	return 0;
}


Measured memory_bytes: 3108
import sys
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for test in range(int(input())):
'''
inf = 100000000000000000  # 1e17


def cal(x):
    return x * (x - 1) // 2


n = int(input())
A = list(map(int, input().split()))
B = [0] * (n + 1)
for a in A:
    B[a] += 1
ans = sum(cal(b) for b in B)
for a in A:
    num = ans
    num -= cal(B[a])
    B[a] -= 1
    num += cal(B[a])
    print(num)
    B[a] += 1


Measured memory_bytes: 76620
K=input()




if K<=500:
	print K
	for i in range(1,K+1):
		print ( str(i)+" " )*K
else:	
	N=(K+1)/2
	if N%2==1: N+=1
	print N
	for i in range(N):
		s=""
		for j in range(N):
			num=(i+j)+1
			if num > N: num-=N

			if i%2==1 and num <= (K - N): num += N
			s+=str(num)
			s+=" "
		print s

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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    int s=0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        s+=a[i];
    }
    sort(a.begin(),a.end(),greater<int>());
    s-=(a[0]/2);
    cout << s<< endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define N 500000

int cnt=0;

int a[N];

void merge(int left,int mid,int right){
	int L[N/2];
	int R[N/2];
	int i,j,idx;
	
	
	for(i=left;i<=mid;i++)
		L[i-left]=a[i];
	
	
	for(i=mid+1;i<=right;i++)
		R[i-mid-1]=a[i];
		

	i=0;  j=0;  idx=left;
	
	while(i<=(mid-left) && j<=(right-mid-1)){
		if(L[i] < R[j]){
			a[idx++]=L[i++];
		}
		else {
			a[idx++]=R[j++];
		}
		cnt++;
	}
	
	while(i<=(mid-left)){
		a[idx++]=L[i++];
		cnt++;
	}
	
	while(j<=(right-mid-1)){
		a[idx++]=R[j++];
		cnt++;
	}
	
	return;
	
}

void mergeSort(int left,int right){
	int mid=(left+right)/2;
	
	if(left < right){
		mergeSort(left,mid);
		mergeSort(mid+1,right);
		merge(left,mid,right);
	}
	
	return;
	
}


int main(){
	int n,i;
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	
	mergeSort(0,n-1);
	
	for(i=0;i<n-1;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n-1]);
	
	printf("%d\n",cnt);
	
	return 0;
	
}


Measured memory_bytes: 5640
# -*- coding: utf-8 -*-

import sys
import os


n, k = map(int, input().split())
#print(k, '??°??§????????????')

W = []
for i in range(n):
    W.append(int(input()))

def check(P):
    # ?????????P?????\?????¨??????????????????????????????????????????????????¢??°
    weight_index = 0
    for i in range(k):
        current_weight = 0
        while current_weight + W[weight_index] <= P:
            #print('i', i, W[weight_index], '?????????')
            current_weight += W[weight_index]
            weight_index += 1
            if weight_index == len(W):
                # ??¨??¨?????£???
                return len(W)
    return weight_index

P_min = 1
P_max = sum(W)
P_mid = None
while True:
    P_mid = (P_min + P_max) // 2
    loaded_num = check(P_mid)

    if loaded_num < n:
        # ????????????????????????
        P_min = P_mid
    else:
        # ??????????????????????????§???P??????????????¢???
        P_max = P_mid

    if P_max - P_min <= 1:
        break

# ??????
if check(P_min) == n:
    print(P_min)
else:
    print(P_max)

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

ll n,a,b,p,t,sum=0;

int main(void){
    cin>>n>>a>>b;
    cin>>p;
    for(int i=0;i<n;i++){
        cin>>t;
        sum+=min(b,(t-p)*a);
        p=t;
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long ll;
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;}

int main(){
   int n,q;
   cin >> n >> q;
   vector<queue<int>> que(n);
   rep(i,n-1){//辺の接続
     int a,b;
     cin >> a >> b;
     que[a-1].push(b);
     que[b-1].push(a);
   }
  
   vector<ll> pp(n);
   bool seen[n];//探索用
   rep(i,n) {//初期化
      pp[i]=0;
      seen[i]=false;
   }
   // rep(i,n)cout << "SIZE" << que[i].size()<<endl;
   rep(i,q){
      int a,b;
      cin >> a >> b;
      pp[a-1]+=b;
      //cout << point[a-1]<<endl;
   }
   
   ll ans[n];
   rep(i,n) ans[i]=pp[i];
   ans[0]=pp[0];
   queue<int> nextp;
   nextp.push(0);
   seen[0]=true;
   while(true){
      int i=nextp.front();
      nextp.pop();
      while(que[i].size()){
         int index = que[i].front();
         if(seen[index-1]) {
            que[i].pop();
            continue;
         }
         seen[index-1] = true;
         nextp.push(index-1);
         que[i].pop();
         ans[index-1] = ans[i]+pp[index-1];
      }
      if(!nextp.size())break;
   }
   rep(i,n) cout << ans[i] << " ";
   cout << endl;
   return 0;
}

Measured memory_bytes: 140800
N = int(input())

list_1 = [1]
list_6 = [6**(i+1) for i in range(6)]
list_9 = [9**(i+1) for i in range(5)]
list_169 = list_1+list_6+list_9

list_169 = sorted(list_169, reverse=True)


N_sub = N
d_count = 0
for i in range(len(list_169)):
    while list_169[i] <= N_sub:
        N_sub -= list_169[i]
        d_count += 1


dp = [[100000 for j in range(13)] for i in range(N+1)]

def N_mai(N_sub, index, s_count):
    global d_count
    if N_sub == 0:
        return 0
    elif dp[N_sub][index] != 100000:
        return dp[N_sub][index]
    else:
        if list_169[index] == 1:
            count = N_sub
        elif N_sub >= list_169[index]:
            count = min(N_mai(N_sub - list_169[index], index, s_count+1)+1,
                        N_mai(N_sub - list_169[index], index+1, s_count+1)+1, 
                        N_mai(N_sub, index+1, s_count))
        else:
            count = N_mai(N_sub, index+1, s_count)

        dp[N_sub][index] = count
        return count

print(min(d_count, N_mai(N, 0, 0)))


Measured memory_bytes: 27052
#include<stdio.h>

int main(void){
	int dis[10];
	int v1,v2;
	int i;
	int sum,tmp;
	while(scanf("%d,",&dis[0])!=EOF){
		sum=dis[0];
		tmp=0;
		for(i=1;i<10;i++){
			scanf("%d,",&dis[i]);
			sum+=dis[i];
		}
		scanf("%d,",&v1);
		scanf("%d",&v2);
		for(i=0;i<10;i++){
			tmp+=dis[i];
			if((double)v1*sum/(v1+v2)<=tmp){
				//printf("%d\n",v1*sum/(v1+v2));
				printf("%d\n",i+1);
				break;
			}
		}
	}
	return 0;
}

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

typedef pair<int,int> P;

int now[10001];
int idx[10001]={};

int main(){
    memset(now,-1,sizeof(now));
    int N; cin >> N;
    vector<vector<int>> a(N, vector<int>(N-1));
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            cin >> a[i][j];
            a[i][j]--;
        }
    }
    queue<P> q;
    for(int i=0;i<N;i++){
        q.push(P(i,a[i][0]));
    }

    int day=0;
    int all=0;

    while(true){
        int upd=0;
        queue<P> Q;
        while(!q.empty()){
            P p=q.front();
            q.pop();
            int id=p.first;
            int to=p.second;
            if(now[to]==id){
                upd++; all++;
                idx[to]++; idx[id]++;
                if(idx[to]<N-1) Q.push(P(to,a[to][idx[to]]));
                if(idx[id]<N-1) Q.push(P(id,a[id][idx[id]]));
            }else{
                now[id]=to;
            }   
        }
        if(!upd) break;
        day++;
        q=Q;
    }
    if(all!=N*(N-1)/2) cout << -1 << endl;
    else cout << day << endl;
}

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

using namespace std;
using ll = long long;

int n;
ll k, a[100010];
ll p[41][2];

ll dp[41][2];
bool check[41][2];
ll f(int j, bool small){
    if(j < 0) return 0;

    if(check[j][small]) return dp[j][small];
    check[j][small] = true;
    ll ans;

    if(small){
        ll res1 = p[j][1] + f(j - 1, true);
        ll res2 = p[j][0] + f(j - 1, true);
        ans = max(res1, res2);
    }
    else{
        if(k & (1ll << j)){
            ll res1 = p[j][1] + f(j - 1, false);
            ll res2 = p[j][0] + f(j - 1, true);
            ans = max(res1, res2);
        }
        else{
            ans = p[j][0] + f(j - 1, false);
        }
    }
    return dp[j][small] = ans;
}

int main(){
    scanf("%d %lld", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);

    for(int j = 40; j >= 0; j--){
        for(int i = 1; i <= n; i++){
            if(a[i] & (1ll << j)) p[j][0] += 1ll << j;
            else p[j][1] += 1ll << j;
        }
    }

    printf("%lld\n", f(40, false));
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007


int main()
{    int a[210000],b[210000];
    int n,pp;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i%2==0&&n%2==0)
        {
            b[(n-i+1)/2+1]=a[i];
        }
        else if(i%2==0&&n%2!=0)
        {
             b[(n+i+1)/2]=a[i];
        }
        else if(i%2==1&&n%2==1)
        {
             b[(n-i+2)/2]=a[i];
        }
        else
        {
             b[(n+i+2)/2]=a[i];
        }
    }
    for(int i=1;i<=n-1;i++)
    {
        printf("%d ",b[i]);
    }
    printf("%d\n",b[n]);
  //  10 1 2 3 4 5 6 7 8 9 10
    return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define fi first
#define se second
#define pf push_front
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define debug(val) cerr << "Value " << #val << " : " << val << '\n';
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ld epsilon = 10e-9;
const ll nax = 1e5+5;
ll  n, m;
vector<ll>arr[nax];
bool vis[nax];
vector<ll>dist(nax);
	
int main(void){
	IOS
	cin >> n >> m;
	for(int i=0;i<m;i++){
		ll a, b;
		cin >> a >> b;
		arr[a].eb(b);
		arr[b].eb(a);
	}
	if(arr[1].empty()){
		cout << "No" << '\n';
		return 0;
	}
	cout << "Yes" << '\n';
	queue<ll>q;
	q.push(1);
	while(!q.empty()){
		ll curr=q.front();
		q.pop();
		for(auto x:arr[curr]){
			if(vis[x]) continue;
			vis[x]=1;
			dist[x]=curr;
			q.push(x);
		}
	}
	for(int i=2;i<=n;i++) cout << dist[i] << '\n';
}


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

int n,x,arr[10001], i,j,count, minIndex, ans;

int main(){
	cin >> n >> x;
	for(i=0; i<n; i++){
		cin >> arr[i];
	}
	
	for(i=0; i<n-1; i++){
		//while (count < x){
			minIndex = i;
			for(j=i+1; j<n; j++){
				if(arr[i] > arr[j]){
					swap(arr[i], arr[j]);
		//			count++;
				}
			}
		//}
	}
	for(i=0; i<x; i++){
		ans += arr[i];
	}
	cout << ans << endl;
}

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

int main(){
  int q;
  cin >> q;
  string X,Y;

  for(int i=0;i<q;i++){
    cin >> X >> Y;
    int dp[1001][1001]={};
    for(int j=1;j<=Y.size();j++){
      for(int k=1;k<=X.size();k++){
	if(X[k-1]==Y[j-1]) dp[j][k]=dp[j-1][k-1]+1;
	else dp[j][k]=max(dp[j-1][k],dp[j][k-1]);
      }
    }
    cout << dp[Y.size()][X.size()] << endl;
  }
}



Measured memory_bytes: 7096
import java.util.*;

class Main{

    int h, w;
    int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
    int[] dy = {1, -1, 0, 0, 1, -1, 1, -1};
    char[][] donut;
    String cutS;

    @SuppressWarnings("unchecked")
    void solve(){
        Scanner sc = new Scanner(System.in);

        while(true){
            h = sc.nextInt();
            w = sc.nextInt();
            if(h==0 && w==0) break;

            donut = new char[h][w];
            for(int i=0; i<h; i++){
                String line = sc.next();
                donut[i] = line.toCharArray();
            }

            int max = 0;
            StringBuilder minString = new StringBuilder();

            for(int l=h*w; l>=2; l--){
                HashSet<String> set = new HashSet<String>();
                for(int i=0; i<h; i++){
                    for(int j=0; j<w; j++){
                        for(int k=0; k<8; k++){                        
                            StringBuilder s = new StringBuilder();
                            s.append(donut[i][j]);
                            int ny = (i + dy[k]) % h, nx = (j + dx[k]) % w;
                            if(ny==-1) ny = h-1;
                            if(nx==-1) nx = w-1;
                            while(!(ny==i && nx==j)){
                                if(s.length()==l) break;
                                s.append(donut[ny][nx]);
                                ny = (ny + dy[k]) % h;
                                nx = (nx + dx[k]) % w;
                                if(ny==-1) ny = h-1;
                                if(nx==-1) nx = w-1;
                            }
                            if(s.length()!=l) continue;

                            if(!set.add(s.toString()) && (minString.length()==0 || min(s, minString))){
                                max = s.length();
                                minString = s;
                            }
                        }
                    }
                }
                if(max!=0) break;
            }

            if(minString.length()==0) System.out.println(0);
            else System.out.println(minString.toString());
        }
    }

    boolean min(StringBuilder s1, StringBuilder s2){ //s1 < s2?
        int l1 = s1.length(), l2 = s2.length();
        for(int i=0; i<Math.min(l1, l2); i++){
            if(s1.charAt(i)<s2.charAt(i)) return true;
            else if(s1.charAt(i)>s2.charAt(i)) return false;
        }
        if(l1<l2) return true;
        return false;
    }

    public static void main(String[] args){
        new Main().solve();
    }
}

Measured memory_bytes: 205168
#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
    int m,n,d;
    int num=0;
    cin>>m>>n>>d;
    for(int i=m;i<=n;i++)
    {
        if(i%d==0)
            num++;
    }
    cout<<num<<endl;
    return 0;
}


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

string A, B, C;
int a, b, c;

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

	cin >> A >> B >> C;
	a = A.length();
	b = B.length();
	c = C.length();

	if (A[a - 1] == B[0] && B[b - 1] == C[0]) {
		cout << "YES\n";
	}
	else {
		cout << "NO\n";
	}
	

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define N 10001
int main(){
    int a[3], b[3], c[4];
    cin >> a[0] >> a[1] >> a[2];
    for (int i = 0; i < 3; ++i) b[i] = a[i];
    int d = 0;
    while(true) {
        for (int i = 0; i < 3; ++i) if (a[i] % 2) {
            cout << d;
            return 0;
        }
        ++d;
        for (int i = 0; i < 3; ++i) c[i] = a[i] / 2;
        c[3] = c[0];
        for (int i = 0; i < 3; ++i) a[i] = c[i] + c[i + 1];
        int i;
        for (i = 0; i < 3; ++i) if (a[i] != b[i]) break;
        if (i == 3) {
            cout << -1;
            return 0;
        }
    }
}

Measured memory_bytes: 256
N = int(input())
act = [list(map(int,input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N+1)]

for i in range(N):
  dp[i+1][0] = max(dp[i][1], dp[i][2]) + act[i][0]
  dp[i+1][1] = max(dp[i][0], dp[i][2]) + act[i][1]
  dp[i+1][2] = max(dp[i][0], dp[i][1]) + act[i][2]
  
print(max(dp[N]))

Measured memory_bytes: 101896
#include <bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;

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

    int A[Q];
    int P[N];
    REP(i, N){
        P[i] = K - Q;
    }

    REP(i, Q){
        cin >> A[i];
        P[A[i]-1]++;
    }

    int ans = 0;
    REP(i, N){
        if (P[i] > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

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

using namespace std;
using ll = long long;
int n,x[16],y[16],d[16],D[16],p[16];
ll ans[16];
int main() {
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out1.txt", "w", stdout);
#endif

    memset(ans , 0x3f , sizeof(ans));
    cin >> n;
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i]>>p[i];
    }

    for(int i=0;i<n;i++){
        D[i] = min(abs(x[i]) , abs(y[i]));
    }
    ans[0] = 0;
    for(int i=0;i<n;i++){
        ans[0] += (ll)D[i]*p[i];
    }
    for(int i=1;i<(1<<n);i++){
        int j = i;
        do{
            memcpy(d,D,sizeof(D));
            for(int k=0;k<n;k++){
                if(i>>k&1){
                    if(j>>k&1){
                        for(int q=0;q<n;q++){
                            d[q] = min(d[q] , abs(x[q] - x[k]));
                        }
                    }
                    else{
                        for(int q=0;q<n;q++){
                            d[q] = min(d[q] , abs(y[q] - y[k]));
                        }
                    }
                }
            }
            ll tmp = 0;
            for(int i=0;i<n;i++) tmp += (ll)d[i] * p[i];
            ans[__builtin_popcount(i)] = min(ans[__builtin_popcount(i)] , tmp);
            j = (j-1) & i;
        }while(j != i);
    }
    for(int i=0;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}









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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}

int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  int A, B; cin >> A >> B;
  cout << A * B << endl;
}

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

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

	if ((c[1][0] - c[0][0] == c[1][1] - c[0][1] && c[1][0] - c[0][0] == c[1][2] - c[0][2]) &&
		(c[2][0] - c[0][0] == c[2][1] - c[0][1] && c[2][0] - c[0][0] == c[2][2] - c[0][2])) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

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

int main() {
    int N;
    cin >> N;
    int p[N];
    int count = 0;
    for(int i = 0;i < N;i++)
    {
        cin >> p[i];
        if(i + 1 != p[i])
        {
            count++;
        }

        if(count > 2)
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
aa = list(map(int,input().split()))
a = [[] for i in range(n)]
for i in range(n):
    a[i].append(aa[i])
    a[i].append(i)

a.sort()

mm = a[n//2-1][0]
m = a[n//2][0]
for i in range(n):
    a[i].append(i)
a.sort(key = lambda x:x[1])

for i in range(n):
    if a[i][2] <= n//2 -1:
        print(m) 
    else:
        print(mm)

Measured memory_bytes: 122580
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <cmath>
#include <sstream>
#include <map>
#define F first
#define S second
#define FOR(i,n) for(int i=0;i<(int)n;i++)
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define FORI(i,k,n) for(int i=k;i<(int)n;i++)
#define repp(i,k,n) for(int i=k;i<(int)n;i++)
using namespace std;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef pair< int , pair<int, int> > pip;
typedef unsigned long long ull;
const double EPS = 10e-6;
const int MMM=1000000007;


int gcd(int m,int n)
{
	if(m<n)swap(m,n);
	if(n==0)return m;
	return gcd(n,m%n);
}
int lcm(int m,int n)
{
	return m*n/gcd(m,n);
}

int main()
{
	int n;
	cin>>n;
	int a,b;
	cin>>a;
	for(int i=0;i<n-1;i++)
	{
		cin>>b;
		a=lcm(a,b);
	}
	cout<<a<<endl;
}

Measured memory_bytes: 1160
fn main(){
  let m: u32 = 100000;
  
  loop {
    let wh: Vec<usize> = read_vec();
    let w = wh[0];
    let h = wh[1];

    if w == 0 && h == 0 { break; }

    let mut dp: Vec<Vec<Vec<u32>>> = vec![vec![vec![0;4];w];h];

    for i in 1 .. w {
      dp[0][i][0] = 1;
    }

    for j in 1 .. h {
      dp[j][0][3] = 1;
    }

    for j in 1 .. h {
      for i in 1 .. w {
        dp[j][i][0] = (dp[j][i-1][0] + dp[j][i-1][1]) % m;
        dp[j][i][1] = dp[j][i-1][3];
        dp[j][i][2] = dp[j-1][i][0];
        dp[j][i][3] = (dp[j-1][i][2] + dp[j-1][i][3]) % m;
      }
    }

    let mut ans: u32 = dp[h-1][w-1].iter().sum();
    ans %= m;
    
    println!("{}", ans);
  }
}

fn read_vec<T>() -> Vec<T>
  where T: std::str::FromStr,
        T::Err: std::fmt::Debug
{
  let mut buf = String::new();
  std::io::stdin().read_line(&mut buf).expect("failed to read");
  buf.split_whitespace().map(|e| e.parse().unwrap()).collect()
}



Measured memory_bytes: 5052
#!/usr/bin/env python3
def main():
    from itertools import combinations

    _ = int(input())
    L = [int(x) for x in input().split()]

    ans = 0
    for i, j, k in combinations(L, 3):
        if i == j or j == k or k == i:
            continue
        tri = sorted([i, j, k])
        ans += 1 if tri[2] < sum(tri[:2]) else 0
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9180
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long int power(int a,int b)
{
    if(b==0)
        return 1;
    long long int k=power(a,b/2);
    if(b%2==0)
        return ((k%M)*(k%M))%M;
    else
        return ((k%M)*(k%M)*(a%M))%M;
}
long long int fact(long long int n)
{
    if(n==1 || n==0)
        return 1;
    else
        return ((n%M)*(fact(n-1)%M))%M;

}
int div(int n)
{  int c=0;
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
          if(n/i==i)
            c++;
          else
            c+=2;
        }

    }

    
    return  c;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifndef ONLINE_JUDGE
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
   #endif
   
   int d,n;
   cin>>d>>n;
   if(n!=100)
   cout<<n;
else
    cout<<101;
   for(int i=1;i<=2*d;i++)
    cout<<0;




 return 0;
}








Measured memory_bytes: 3636
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1e17
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const ll MAX = 510000;
const ll MOD = 1000000007;

struct edge {
    ll from;
    ll to;
    ll cost;
};

ll V, E;
ll d[MAX];
edge es[MAX];

bool has_negative_loop(ll s) {
    fill(d, d + V, INF);
    d[s] = 0;
    for (ll i = 0; i < V; i++) {
        for (ll j = 0; j < E; j++) {
            edge e = es[j];
            ll tmp = d[V-1];
            if (d[e.to] > d[e.from] + e.cost and d[e.from] != INF) {
                d[e.to] = d[e.from] + e.cost;
                if (i == V - 1 and d[V-1] < tmp) {
                    return true;
                }
            }
        }
    }
    return false;
}


int main(){
  cin>>V>>E;
  rep(i,E){
    ll from, to, cost;
    cin>>from>>to>>cost;
    from--;to--;
    es[i] = edge({from, to, -cost});
  }

  if(has_negative_loop(0)) cout<<"inf"<<endl;
  else cout<<-d[V-1]<<endl;


}


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

int digits(int n){
  int ans=0;
  while(n>0){
    ans+=n%10;
    n/=10;
  }
  return ans;
}

int main(){
  int n; cin>>n;
  int ans = digits(n);
  if(ans==1){
    cout<<10<<endl;
  }else{
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
int main(){
  int a,b,c,d,e;
  cin>>a>>b>>c>>d>>e;
  int k;
  cin>>k;
  if(abs(a-b)>k)
    cout<<":("<<endl;
  else if(abs(a-c)>k)
    cout<<":("<<endl;
  else if(abs(a-d)>k)
    cout<<":("<<endl;
  else if(abs(a-e)>k)
    cout<<":("<<endl;
  else if(abs(b-c)>k)
    cout<<":("<<endl;
  else if(abs(b-d)>k)
    cout<<":("<<endl;
  else if(abs(b-e)>k)
    cout<<":("<<endl;
  else if(abs(c-d)>k)
    cout<<":("<<endl;
  else if(abs(c-e)>k)
    cout<<":("<<endl;
  else if(abs(d-e)>k)
    cout<<":("<<endl;
  else
    cout<<"Yay!"<<endl;
}

Measured memory_bytes: 256
N=int(input())
testimony=[[-1]*N for i in range(N)]
count=0
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        testimony[i][x-1]=y
for i in range(1<<N):
    honest=[0]*N
    for j in range(N):
        if (i>>j)&1:
            honest[j]=1
    flag=True
    for j in range(N):
        if honest[j]:
            for k in range(N):
                if testimony[j][k]==-1:
                    continue
                if testimony[j][k]!=honest[k]:
                    flag=False
    if flag:
        count=max(count,honest.count(1))
print(count)


Measured memory_bytes: 3064
//For fast competitive programming

//INCLUDE
#include <bits/stdc++.h>
using namespace std;

//DATA_TYPES
typedef long long ll; 
typedef vector<int> vi;
typedef pair<int, int> ii; 
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f; //Infinity

//INITIALISING
//memset(arr, 0, sizeof arr);
//vi v(N, 0);

int main()
{
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(NULL);
	
	//write your code here
	int t;
	cin>>t;
//vector<string> ans;
//vi ans;
ll ans =0;
	for(int z=1;z<=t;z++)
	{
	    if (((z%5)==0) || ((z%3)==0)||((z%15)==0))
        {
           continue;
        }
        //cout<<z;
	    ans=ans+z;
	    
	}
	cout<<ans<<endl;
//int no =0;

	return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;



int main(){
    int n, k, s;
    cin >> n >> k >> s;
    vector<int> res(n);
    rep(i, k){
        res[i] = s;
    }
    REP(i, k, n - 1){
        if(s > 1000000)res[i] = 1;
        else res[i] = INF;
    }
    rep(i, n)cout << res[i] << " ";
}

Measured memory_bytes: 1664