akhauriyash/Code-Regression huggingface dataset:
def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    n, k = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    gcd = 0
    for v in a:
        gcd = fractions.gcd(gcd, v)
    mv = max(a)
    if mv < k:
        print("IMPOSSIBLE")
    else:
        if (mv - k) % gcd == 0:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")


if __name__ == '__main__':
    slove()


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

char str[1010];

void MAIN() {
    int n;
    scanf("%d", &n);
    std::vector<int> arr(n);
    for(int &now: arr) {
        scanf("%d", &now);
    }
    long long ans = 0;
    int preLeft = 0;
    for(int i = 0; i < (int)arr.size(); ++ i) {
        int magic = std::min(preLeft, arr[i]);
        ans += magic;
        arr[i] -= magic;
        ans += arr[i] / 2;
        preLeft = arr[i] & 1;
    }
    printf("%lld\n", ans);
}

int main() {
    MAIN();
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define vi   vector<int>
#define vvi  vector<vi >
#define vvvi vector<vvi >
#define pii  pair<int,int>
#define INF  (int)1e9
#define MOD  (int)1e9+7
typedef long long llong;
using namespace std;

int main(){
	int n;
	cin>>n;
	
	vi p(n);
	REP(i,n) cin>>p[i];
	
	vi q=p;
	sort(ALL(q));
	
	int cnt=0;
	REP(i,n){
		if(p[i]!=q[i]) cnt++;
	}
	
	if(cnt<=2) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

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

using i8  = int8_t;   /* -128 ~ 127 */
using u8  = uint8_t;  /* 0 ~ 255 */
using i16 = int16_t;  /* -32,768 ~ 32,767 */
using u16 = uint16_t; /* 0 ~ 65,535 */
using i32 = int32_t;  /* -2,147,483,648 ~ 2,147,483,647 */
using u32 = uint32_t; /* 0 ~ 4,294,967,295 */
using i64 = int64_t;  /* -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 */
using u64 = uint64_t; /* 0 ~ 18,446,744,073,709,551,615 */
using f32 = float;    /* (-3.4 * 10^38) ~ (3.4 * 10^38) */
using f64 = double;   /* (-1.7 * 10^308) ~ (1.7 * 10^308) */
using f80 = __float80;
template <class T> using Vec = vector<T>;
constexpr i64 INF = 1010000000000000017;
constexpr i64 MOD = 1e9 + 7;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define ALL(v) v.begin(), v.end()
#define GCD(a, b) __gcd(a, b) /* 最大公約数 */
#define LCM(a, b) a / __gcd(a, b) * b /* 最小公倍数 */

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

void Main() {
    u32 K, X;
    cin >> K >> X;
    if (K * 500 >= X) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>


int main() {
    long long x; std::cin >> x;
    for (long long a = -120; a <= 120; a++) {
        for (long long b = -120; b <= 120; b++) {
            if (a*a*a*a*a - b*b*b*b*b == x) {
                std::cout << a << " " << b << std::endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <limits>
#include <algorithm>
#include <utility>
#include <sstream>
#include <numeric>
#include <iterator>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef pair<int, int> P;

int main(int argc, const char * argv[]) {
  char a;
  cin >> a;
  cout << (char)(a+1) << endl;
  return 0;
}


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

ll mod=1e9+7;

int main(){
	ll n,m,a1,r1;
	cin>>n>>m;
	vector<ll> dp(n+5,0);
	vector<ll> no(n+5,0);
	for(a1=0;a1<m;++a1){
		cin>>r1;
		no[r1]=1;
	}
	dp[0]=1;
	for(a1=1;a1<=n;++a1){
		if(no[a1]) continue;
		int x=0;
		if(a1-2>=0) x=dp[a1-2];
		dp[a1]=(dp[a1-1]+x)%mod;
	}
	cout<<dp[n];
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {

    int A, B;
    cin >> A >> B;

    vector<vector<char>> gridWhite(50, vector<char>(100, '.'));
    vector<vector<char>> gridBlack(50, vector<char>(100, '#'));

    A--; B--;
    
    rep(i,50/3) rep(j,100/3) {
        if (A > 0) {
            A--;
            gridBlack[3 * i + 1][3 * j + 1] = '.';
        }
        if (B > 0) {
            B--;
            gridWhite[3 * i + 1][3 * j + 1] = '#';
        }
    }

    printf("100 100\n");
    rep(i,50) {
        rep(j,100) cout << gridWhite[i][j];
        cout << endl;
    }
    rep(i,50) {
        rep(j,100) cout << gridBlack[i][j];
        cout << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
R = N - K
mod = 10**9 + 7
fac = [0] * 2010
facinv = [0] * 2010
fac[1] = 1
facinv[1] = pow(1, -1, mod)
fac[0] = 1
facinv[0] = 1

for i in range(2, 2000):
    fac[i] = (fac[i-1] * i) % mod
    facinv[i] = (facinv[i-1] * pow(i, -1, mod)) % mod

def nCk(n, k):
    return (fac[n] * facinv[k] * facinv[n-k]) % mod

for i in range(K):#i = 間に入れるボール
    if i > R:
        print("0")
    else:
        print((nCk(K-1, i) * nCk(R+1, i+1)) % mod)


Measured memory_bytes: 9168
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <iomanip>

typedef long double ld;
typedef long long ll;

using namespace std;


/* TEMPLATE ENDS HERE */

#define MAXN 200010

int a[MAXN][26];
int m;

int main() {
	cout << fixed << setprecision(12);	
	string s, t;
	int n;
	cin >> s >> t;
	m = s.length();
	s += s;
	n = s.length();
	for (int j = 0; j < 26; j++) {
		char c = 'a' + j;
		int cur = -1;
		for (int i = n - 1; i >= 0; i--) {
			if (s[i] == c) {
				cur = i;
			}
			a[i][j] = cur;
		}
	}
	ll cur = 0;
	int pos = 0;
	for (int i = 0; i < t.length(); i++) {
		int nnext = a[pos][t[i] - 'a'];	
		if (nnext == -1) {
			cout << -1 << endl;
			return 0;
		}
		cur += nnext - pos + 1;
		pos = (nnext + 1) % m;
	}
	cout << cur << endl;
	return 0;
}


ll MOD = ((ll)1e9 + 7);

struct mod {
	ll x;

	mod(ll tx = 0) {
		x = tx;
		x %= MOD;
	}
	
	mod& operator=(const ll & tx) {
		x = tx % MOD;
		return *this;
	}
	
	mod& operator=(const mod & m2) {
		x = m2.x;
		return *this;
	}

	mod operator+(const mod& m2) const {
		return mod((x + m2.x) % MOD);
	}

	mod& operator+=(const mod& m2) {
		x += m2.x;
		x %= MOD;
		return *this;
	}

	mod operator-(const mod & m2) const {
		return mod((x - m2.x + MOD) % MOD);
	}

	mod& operator-=(const mod & m2) {
		x -= m2.x;
		x = (x + MOD) % MOD;
		return *this;
	}

	mod operator*(const mod & m2) const {
		return mod((x * m2.x) % MOD);
	}

	mod& operator*=(const mod & m2) {
		x *= m2.x;
		x %= MOD;
		return *this;
	}

	mod mypow(ll k) const {
		mod ret = 1;
		mod cur = x;
		while (k) {
			if (k & 1) {
				ret *= cur;
			}
			cur *= cur;
			k >>= 1;
		}
		return ret;
	}

	mod inv() const {
		return mypow(MOD - 2);
	}

	mod operator/(const mod & m2) const {
		return (*this) * m2.inv();
	}

	mod& operator/=(const mod & m2) {
		x *= m2.inv().x;
		x %= MOD;
		return *this;
	}

	bool operator<(const mod & m2) const {
		return x < m2.x;
	}
};

ostream &operator<<(ostream & os, const mod & m) {
	return os << m.x;
}



Measured memory_bytes: 24124
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void solve() {
  int h, w;
  cin >> h >> w;
  vector<string> v(h);
  rep(i,h) cin >> v[i];
  rep(i,h) {
    rep(j, w) {
      if (v[i][j] == '.') continue;
      bool b = true;
      rep(k, 4) {
        int y = dy[k] + i;
        int x = dx[k] + j;
        if (y < 0 || h - 1 < y || x < 0 || w - 1 < x) continue;
        if (v[y][x] == '#') b = false;
      }
      if (b) {
        cout << "No" << endl;
        return;
      }
    }
  }
  cout << "Yes" << endl;
}

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

Measured memory_bytes: 3564
mod reader {
    use std::fmt::Debug;
    use std::str::FromStr;
    use std::collections::VecDeque;
    use std::io::{self, Read};

    fn _read_line() -> String {
        let mut buf = String::new();
        let _ = io::stdin().read_to_string(&mut buf);
        buf
    }

    fn _read_vec_deque_string() -> VecDeque<String> {
        _read_line()
            .split_whitespace()
            .map(|s| s.to_string())
            .collect()
    }

    pub struct Reader {
        buf: VecDeque<String>,
    }

    #[allow(dead_code)]
    impl Reader {
        pub fn new() -> Reader {
            Reader { buf: VecDeque::new() }
        }

        fn update_buf(&mut self) {
            if self.buf.is_empty() {
                self.buf = _read_vec_deque_string();
            }
        }

        pub fn next<T>(&mut self) -> T
        where
            T: FromStr,
            T::Err: Debug,
        {
            self.update_buf();
            self.buf.pop_front().unwrap().parse::<T>().unwrap()
        }

        pub fn next_n<T>(&mut self, n: usize) -> Vec<T>
        where
            T: FromStr,
            T::Err: Debug,
        {
            let mut vec: Vec<T> = Vec::with_capacity(n);

            for _ in 0..n {
                vec.push(self.next());
            }
            vec
        }
    }
}

fn mod_pow(mut x: i64, mut p: i64, MOD: i64) -> i64 {
    let mut res = 1;
    while p > 0 {
        if p % 2 == 1 {
            res = res * x % MOD;
        }
        p /= 2;
        x = x * x % MOD;
    }
    res
}

fn comb(n: i64, r: i64, fact: &[i64], MOD: i64) -> i64 {
    if r < 0 || r > n {
        0
    } else {
        fact[n as usize] * mod_pow(fact[r as usize], MOD - 2, MOD) % MOD *
            mod_pow(fact[(n - r) as usize], MOD - 2, MOD) % MOD
    }
}

fn main() {
    let mut reader = reader::Reader::new();

    let n: usize = reader.next();
    const MOD: i64 = 1000000007;

    let v: Vec<usize> = reader.next_n(n + 1);

    let mut idx: Vec<usize> = vec![n + 1; n + 1];
    let mut i1: usize = 0;
    let mut i2: usize = 0;
    for i in 0..n + 1 {
        if idx[v[i]] <= n {
            i1 = idx[v[i]];
            i2 = i;
        } else {
            idx[v[i]] = i;
        }
    }
    // println!("i1={}", i1);
    // println!("i2={}", i2);

    let a = (n - i2 + i1) as i64;
    let b = (i2 - i1 - 1) as i64;

    let mut fact: Vec<i64> = vec![1, 1];
    for i in 2..n + 2 {
        let prv = fact[i-1];
        fact.push(i as i64 * prv % MOD);
    }

    // println!("a={}", a);
    // println!("b={}", b);
    for k in 1..(n + 2) as i64 {
        // println!("1:{}", comb(a + b, k - 2, &fact, MOD));
        // println!("2:{}", 2 * comb(a + b, k - 1, &fact, MOD) - comb(a, k - 1, &fact, MOD));
        // println!("3:{}", comb(a + b, k, &fact, MOD));

        let ans = comb(a + b, k - 2, &fact, MOD) + 2 * comb(a + b, k - 1, &fact, MOD) -
            comb(a, k - 1, &fact, MOD) + comb(a + b, k, &fact, MOD) + MOD;
        println!("{}", ans % MOD);
    }
}

Measured memory_bytes: 10904
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    cin >> s;
    int len= 0;
    int ans = 0;
    rep(i,s.length())
    {
        if (s[i]=='A' || s[i] == 'T' || s[i] == 'G' || s[i] == 'C')
        {
            len++;
        }
        else
        {
            ans = max(ans, len);
            len = 0;
        }
    }
    cout << max(ans, len) << endl;
}


Measured memory_bytes: 256
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    MOD = 10**9 + 7
    from collections import Counter
    c = Counter(A)
    # print(c)
    for k, v in c.items():
        if k != 0 and v != 2:
            return print(0)
    if N & 1 and c[0] != 1:
        return print(0)

    if N & 1:
        ma = max(A)//2
    else:
        ma = (max(A) + 1)//2
    print(pow(2, ma, MOD))


if __name__ == '__main__':
    main()


Measured memory_bytes: 55404
import copy
N = int(input())
A = list(map(int,input().split()))
ans = []
S = 0
for i in range(N-1):
    S += abs(A[i]-A[i+1])
S += abs(A[0])
S += abs(A[N-1])
B = []
B.append(0)
for i in range(N):
    B.append(A[i])
B.append(0)

for i in range(1,N+1):
    s = S + abs(B[i-1]-B[i+1])-(abs(B[i-1]-B[i])+abs(B[i]-B[i+1]))
    ans.append(s)
for i in range(N):
    print(ans[i])


Measured memory_bytes: 14560
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */

int n,r;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  while (cin >> n >> r, n) {
    vector<int> v(n);
    iota(ALL(v),1);
    REV(v);
    REP(i,r) {
      int p,c;
      cin >> p >> c;
      vector<int> w(n);
      for (int j = 0; j < c; j++) {
        w[j] = v[p-1+j];
      }
      for (int j = 0; j < p-1; j++) {
        w[j+c] = v[j];
      }
      for (int j = c+p-1; j < n; j++) {
        w[j] = v[j];
      }
      v = w;
    }
    cout << v[0] << endl;
  }

  return 0;
}


Measured memory_bytes: 3144
a = [0] * 3
for i in range(3):
    a[i] = list(map(int, input().split()))
N = int(input())
b = [0] * N
for i in range(N):
    b[i] = int(input())

for i in range(N):
    for j in range(3):
        for k in range(3):
            if a[j][k] == b[i]:
                a[j][k] = 0
if sum(a[0]) == 0 or sum(a[1]) == 0 or sum(a[2]) == 0:
    print("Yes")
elif a[0][0] + a[1][1] + a[2][2] == 0 or a[0][2] + a[1][1] + a[2][0] == 0:
    print("Yes")
elif a[0][0] + a[1][0] + a[2][0] == 0 or a[0][1] + a[1][1] + a[2][1] == 0 or a[0][2] + a[1][2] + a[2][2] == 0:
    print("Yes")
else:
    print("No")


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

char x;

signed main()
{
	cin>>x;
	if ('A'<=x&&x<='Z')  cout<<'A'<<endl;
	else if ('a'<=x&&x<='z')  cout<<'a'<<endl;
	
	return 0;
}

Measured memory_bytes: 3632
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <cstdint>
using namespace std;
#define     loop(n,i,a)     for(ll i=a;i<n;i++)
#define     loopR(n,i,a)    for(ll i=n-1;i>=a;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define     vii             vector<pair<ll,ll>>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
int dx[] = { 1 , 0 ,-1 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 1 , 0 ,-1 ,-1 , 1 ,-1 , 1 };
int KnightI[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int KnightJ[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
template<typename T>
void max_self(T &a,T b){
    a=max(a,b);
}
template<typename T>
void min_self(T &a,T b){
    a=min(a,b);
}
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
const ll mxN=2e5+10,oo=0x3f3f3f3f,MOD=1e9+7;
const double PI = acos(-1);

void solve(){
    ll n;
    cin>>n;
    loop(3501,i,1){
        loop(3501,j,1){
            ll num=(4*i*j-n*(i+j));
            if(num<=0)
                continue;
            ll g=__gcd(num,n*i*j);
            num/=g;
            if(num==1){
                cout<<i<<' '<<j<<' '<<(n*i*j)/g<<Endl;
                return;
            }
        }
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast();
    solve();
}


Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <functional>
using namespace std;


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    long long int n;
    cin >> n;
    long long int power = 1;
    long long int MAX = 1000000007;
    for (int i = 1; i <= n; i++) {
        power *= i;
        if (power > MAX) {
            power %= MAX;
        }
    }
    cout << power << endl;
	return 0;
}

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

void solve () {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int mn = 1e5;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mn = min (mn, a[i]);
        sum += a[i];
    }
    a[n] = mn;
    int mn2 = 1e5;
    int ans = mn;
    for (int i = 0; i <= n; i++) {
        a[i] -= mn;
        sum -= mn;
    }
    sum += mn;
    mn = 0;
    while (sum) {
        for (int i = 0; i <= n; i++) {
            if (a[i] == mn && mn2 != 1e5) {
                ans += mn2;
                for (int j = i - 1; j >= 0; j--) {
                    if (a[j] == mn) {
                        break;
                    }
                    a[j] -= mn2;
                    sum -= mn2;
                }
                mn2 = 1e5;
            }
            if (a[i]) {
                mn2 = min (mn2, a[i]);
            }
        }
    }
    cout << ans;

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


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))

using namespace std;

using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
inline u64 xorshift() { static u64 x = 88172645463325252ull; x = x ^ (x << 7); return x = x ^ (x >> 9); }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { os << p.first << ' ' << p.second; return os; }

void solve() {
  int n, k;
  cin >> n >> k;
  if (k == 1) {
    cout << 0 << endl;
    return;
  }
  vi32 a(n);
  cin >> a;
  rep(i, n) a[i]--;

  vi32 sum(n + 1);
  rep(i, n) (sum[i + 1] = sum[i] + a[i]) %= k;
  
  i64 ans = 0;
  unordered_map<int, int> ma;
  repc(i, n) {
    int r = i, l = i - k;
    if (l >= 0) ma[sum[l]]--;
    ma[sum[r]]++;
    ans += ma[sum[r]] - 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 10056
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MOD 1000000009
#define MAX(a,b) (a>b?a:b)
#define MAX3(a,b,c) MAX(a,MAX(b,c))
#define MIN(a,b) (a<b?a:b)
#define MIN3(a,b,c) MIN(a, MIN(b,c))
#define top(i,j) val[i*m+j]
#define s(a,b) strcmp(a,b)
typedef long long lli;
typedef unsigned short int usi;

typedef struct {
    int a;
    int b;
    int c;
} dish;

// (a+b)の値の降順にソート
int cmp(const void *a, const void *b) {
    return ((dish*)b)->c - ((dish*)a)->c;
}

int main()
{
    int n;
    int i;
    lli taka=0, aoki=0;
    scanf("%d",&n);
    dish *d = (dish*)malloc(n * sizeof(dish));
    for(i=0; i<n; i++) {
        scanf("%d %d",&d[i].a, &d[i].b);
        d[i].c = d[i].a + d[i].b;
    }
    qsort(d,n,sizeof(dish),cmp);
    for(i=0; i<n/2; i++) {
        taka += d[2*i].a;
        aoki += d[2*i+1].b;
        //printf("%lld %lld\n",taka,aoki);
    }
    if(n%2==1)taka+=d[n-1].a;
    printf("%lld",taka-aoki);
    return 0;
}


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

template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
int character_count(string text, char character){ int ans = 0; for(int i = 0; i < text.size(); i++){ ans += (text[i] == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }}
#define mod long(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))

struct item{
    int num;
    long value;
};

int main(){
    int N, K;
    cin >> N >> K;
    item items[N];
    long ans = 0;
    for(int i = 0; i < N; i++){
        cin >> items[i].num >> items[i].value;
        if((K | items[i].num) == K){
            ans += items[i].value;
        }
    }
    for(int i = 1; i < 30; i++){
        if((K >> i) & 1){
            int this_K = ((K & ~(1 << i)) | ((1 << i) - 1));
            long this_ans = 0;
            for(int j = 0; j < N; j++){
                if((this_K | items[j].num) == this_K){
                    this_ans += items[j].value;
                }
            }
            ans = max(ans, this_ans);
        }
    }
    cout << ans << endl;
}




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

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

  for (int i = 0; i < S.size(); i++) {
    if ((int)S.at(i) + N > 90) S.at(i) += N - (26 + N);
    S.at(i) += N;
  }

  cout << S << endl;
}

Measured memory_bytes: 256
def intlist(x):
    y = []
    for i in range(len(x)):
        y.append(int(x[i]))
    return y
 
N, M, X = map(int, input().split())
price = -1
 
L = []
a = []
c = []
suit =[]
for i in range(M+1):
    a.append(0)
    
for i in range(N):
    text = input().split()
    L.append(intlist(text))
 
def buy(x,y):
    
    if x + y <= N:
        
        for i in range(0,M+1):
            
            a[i] += L[x+y-1][i]
            
       
        if x + y == N:
            score = a[1:len(a)]
            
            if min(score) >= X:
                suit.append(a.copy())
                
        elif x + y != N:
            buy(x+1,y)
            for i in range(0,M+1):
                a[i] -= L[x+y][i]
           
            notbuy(x,y+1)
 
 
def notbuy(x,y):
   
    if x + y <= N:
        
        if x + y == N:
            score = a[1:len(a)]
            if min(score) >= X:
                suit.append(a.copy())
                    
             
        elif x + y != N:
            buy(x+1,y)
            for i in range(0,M+1):
                a[i] -= L[x+y][i]
            notbuy(x,y+1)    
 
def textbook(x,y):
    buy(x+1,y)
    for i in range(0,M+1):
        a[i] -= L[x+y][i]
    notbuy(x,y+1)
 
textbook(0,0)
 



if suit != []:
    if len(suit) >= 2:
    
        cheaper = suit[0][0]
        for i in range(len(suit)):
            if cheaper > suit[i][0]:
                cheaper = suit[i][0]
        price = cheaper
    elif len(suit) == 1:
        price = suit[0][0]
 


print(price)


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

const ll mod = 1e9 + 7;

ll fpow(ll a, ll b) {
	ll ret = 1;
	while (b) {
		if (b & 1) ret = ret * a %mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}

int main() {
	ll n, k; cin >> n >> k;
	ll gcd[k+1] = {};
	for (ll i = 1; i <= k; i++)
		gcd[i] = fpow(k / i, n);
	for (int i = k; i >= 1; i--)
		for (int j = i + i; j <= k; j += i)
			gcd[i] -= gcd[j];
	for (ll i = 1; i <= k; i++)
		gcd[i] = i * gcd[i] % mod;
	cout << accumulate(gcd + 1, gcd + 1 + k, 0LL) % mod;
}


Measured memory_bytes: 4412
import java.io.*;
import java.util.Scanner;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int a = sc.nextInt();
		int b = sc.nextInt();

		int max = Integer.MIN_VALUE;
		max = Math.max(max, a + b);
		max = Math.max(max, a - b);
		max = Math.max(max, a * b);

		pr.println(max);
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);
			
		solve();
			
		pr.close();
		sc.close();
	}

	static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}


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

ll W, H, x, y;

int main() {
    cin >> W >> H >> x >> y;
    double area = (double)H*W/2;
    int judge = !(W%2) && !(H%2) && (W/2 == x) && (H/2 == y);
    printf("%.9f %d\n", area, judge);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
long int a,b,c,i,d,min;
  scanf("%ld %ld",&a,&b);
  d=0;
  
  if(a<b) min=a;
  else min=b;
    i=min;
  while(d==0 && i>0)
  {
  if(a%i==0 && b%i==0) {c=i;
                        d++;}
  else i--;                    
  }

  printf("%ld",a*b/c);
  
return 0;
}

Measured memory_bytes: 128
using System;
using System.Linq;
using System.Collections.Generic;
using System.Runtime.InteropServices;

class P
{
    static void Main()
    {
        long[] NK = Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray();
        int[][] ab = new int[NK[0]][].Select(_ => Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray()).OrderBy(x => x[0]).ToArray();

        long nowindex = 0;
        for (int i = 0; i < ab.Length; i++)
        {
            nowindex += ab[i][1];
            if (nowindex >= NK[1])
            {
                Console.WriteLine(ab[i][0]);
                break;
            }
        }
    }
}

Measured memory_bytes: 29496
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int flag=0;
  char ch;
  cin>>ch;
  for(char c='A';c<='Z';c++)
    {if(ch==c)
          flag=1;
     }
  if(flag==1)
    cout<<"A\n";
  else
    cout<<"a\n";
return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

ll S(ll n){
	if(n<10) return n;
	else return n%10+S(n/10);
}

double snuke(pair<ll,ll> p){
	return (double)p.first/p.second;
}

ll f(ll n){

	vector<pair<ll,ll> > res;

	pair<ll,ll> y;
	y.first = n;
	y.second = S(n);
	res.push_back(y);

	for(int d = 1; d < 15; d++){
		ll x = pow(10,d)*floor((double)n/pow(10,d)+1)-1;
		y.first = x;
		y.second = S(x);
		res.push_back(y);
	}

	ll m=res[0].first;
	double ms = snuke(res[0]);

	for(int i = 0; i < res.size(); i++){
		//cout << snuke(res[i]) << endl;
		if(ms > snuke(res[i])){
			m = res[i].first;
			ms = snuke(res[i]);
		}
	}

	return m;
}

int main()
{
	ll k;
	cin >> k;
	ll a = 1;
	for(int i = 1; i <= k; i++){
		cout << a << endl;
		a = f(a+1);
	}

	return 0;
}


Measured memory_bytes: 256
const input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.trim().split('\n');

let i = 0;
while (line = lines.shift()) {
	i++;
	const number = Number.parseInt(line);

        if (number ===0 ) break;

	console.log(`Case ${i}: ${number}`);
}



Measured memory_bytes: 22660
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

template<typename T, typename U>
std::enable_if_t<std::rank<T>::value == 0> fill_all(T& arr, const U& v) {
    arr = v;
}
template<typename ARR, typename U>
std::enable_if_t<std::rank<ARR>::value != 0> fill_all(ARR& arr, const U& v) {
    for (auto& i : arr) {
        fill_all(i, v);
    }
}

int64_t V[362244];
int64_t W[362244];
int64_t dp[1<<9][100100];
int64_t func(int32_t i, int32_t w)
{
    if (i >= sizeof(dp) / sizeof(dp[0])) {
        int64_t memo;
        memo = func((i - 1) / 2, w);
        if (W[i] <= w) {
            memo = std::max(memo, func((i - 1) / 2, w - W[i]) + V[i]);
        }
        return memo;
    }

    auto& memo = dp[i][w];
    if (memo != -1) {
        return memo;
    }
    if (i == 0) {
        if (W[i] <= w) {
            return memo =  V[i];
        }
        return memo = 0;
    }
    if (w == 0) {
        return memo = 0;
    }

    memo = func((i - 1) / 2, w);
    if (W[i] <= w) {
        memo = std::max(memo, func((i - 1) / 2, w - W[i]) + V[i]);
    }
    return memo;
}

void func_init()
{
    for (int32_t w = 0; w < W[0]; w++)
    {
        dp[0][w] = 0;
    }
    for (int32_t w = W[0]; w < 100100; w++)
    {
        dp[0][w] = V[0];
    }
    for (int32_t i = 1; i < sizeof(dp)/sizeof(dp[0]); i++)
    {
        auto p = (i - 1) / 2;
        for (int32_t w = 0; w < W[i]; w++)
        {
            dp[i][w] = dp[p][w];
        }
        for (int32_t w = W[i]; w < 100100; w++)
        {
            dp[i][w] = std::max(dp[p][w], dp[p][w - W[i]] + V[i]);
        }
    }
}

int32_t N;

int main()
{
    using std::endl;
    in.sync_with_stdio(false);
    out.sync_with_stdio(false);
    in.tie(nullptr);
    out.tie(nullptr);
    fill_all(dp, -1);
    in >> N;
    for (int i = 0; i < N; i++)
    {
        in >> V[i] >> W[i];
    }
    func_init();
    int Q;
    in >> Q;
    while (Q--) {
        int32_t v;
        int32_t  L;
        in >> v >> L; --v;
        out << func(v, L) << '\n';
    }

    return 0;
}
#endif


Measured memory_bytes: 407672
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    X,Y=input().split()
    if ord(X)<ord(Y):
        print('<')
    elif ord(X)==ord(Y):
        print('=')
    else:
        print('>')

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int mxn=1e7;
vector<int> v;
int n,k,ans=1;
map<int,int> m;
int Pow(int x,int y){
	int sum=1;
	while (y) {
		if (y%2) ans*=x;
		x*=x;
		y/=2;
	}
	return sum;
}
signed main () {
	cin>>n>>k;
	int s=k;
	for (int i=2;i<=sqrt(k);i++) {
		if (s%i==0) v.pb(i);
		while (s%i==0) {
			m[i]++;s/=i;
		}
		m[i]/=n;
	}
	if (s!=1) {
		v.pb(s);
		m[s]++;m[s]/=n;
	}
	for (int i=0;i<v.size();i++) {
		if (m[v[i]]!=0) ans*=Pow(v[i],m[v[i]]);
	}
	cout<<ans;
}

Measured memory_bytes: 66000
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		// 入力
		final String[] s = new String[3];
		try(Scanner scan = new Scanner(System.in)) {
			s[0] = scan.next();
			s[1] = scan.next();
			s[2] = scan.next();
		}
		
		int[] index = {0, -1, -1};
		

		int next = 0;
		while (s[next].length() > index[next]) {
			next = (int) (s[next].charAt(index[next]) - 'a');
			index[next]++;
		}
		
		char result = (char) (next + 'A');
		
		// 出力
		try (PrintWriter out = new PrintWriter(System.out)) {
			out.println(result);
		}

	}

}


Measured memory_bytes: 10068
typedef long long L;
L GCD(L X, L Y){
	if(Y)
		return GCD(Y,X%Y);
	else
		return X;
}
L LCM(L X, L Y){
	return X/GCD(X,Y)*Y;
}
main(){
	int n,i,v[10],d[10],t;
	L T,G;
	for(;scanf("%d",&n),n;){
		for(i=0;i<n;i++){
			scanf("%d%d",d+i,v+i);
			t=GCD(d[i],v[i]);
			d[i]/=t;
			v[i]/=t;
		}
		T=d[0];
		for(i=1;i<n;i++)
			T=LCM(T,d[i]);
		G=T/d[0]*v[0];
		for(i=1;i<n;i++)
			G=GCD(G,T/d[i]*v[i]);
		for(i=0;i<n;i++)
			printf("%d\n",(int)(T/d[i]*v[i]/G));
	}
	exit(0);
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
#define MAX 50
long a[MAX+1], p[MAX+1];

long f(int N, long X) {
  if (N == 0) {
    if (X <= 0) {
     return 0;
    } else return 1;
  } else if (X <= 1 + a[N-1]) {
    return f(N-1, X-1);
  } else if (X == 2 + a[N-1]) {
    // cout << "hoge" << endl;
    return p[N-1] + 1;
  } else if (X <= 2 + 2*a[N-1]) {
    // cout << "hoge2\n" <<  2 + a[N-1] << "\n" << 2 + 2*a[N-1] << endl;
    return p[N-1] + 1 + f(N-1, X-1-a[N-1]-1);
  } else{
    return 2 * p[N-1] + 1;
  }
}

int main() {
  int N;
  long X;
  cin >> N >> X;
  // cout << X << endl;
  a[0] = 1;
  p[0] = 1;
  for (int i = 1;i < N + 1; i++) {
    // cout << i << endl;
    a[i] = 2 * a[i-1] + 3;
    p[i] = 2 * p[i-1] + 1;
    // cout << a[i] << "\n" << p[i] << endl;
  }
  // cout << a[49] << p[49];
  // cout << a[50] << p[50];
  cout << f(N, X);
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(), vec.end()
typedef long long ll;ll MM = 1000000000;ll mod = MM + 7;

int main(){
  ll k,x; cin>>k>>x;
  for(ll i=x-k+1 ;i<=x+k-1 ;i++){
  if(i==x+k-1) cout<<i<<endl;
    else cout<<i<<" ";
  }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define m0(x) memset(x, 0, sizeof(x))
#define MAX_H 60
#define MAX_W 60
int H, W;
char S[MAX_H][MAX_W];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};

int main() {
  cin >> H >> W;
  REP(i, H) REP(j, W) cin >> S[i][j];
  int ans[MAX_H][MAX_W];
  REP(i, H) REP(j, W) ans[i][j] = 0;

  REP(i, H) {
    REP(j, W) {
      if (S[i][j] == '.') {
        REP(k, 8) {
          if (i + dx[k] >= 0 && i + dx[k] < H && j + dy[k] >= 0 &&
              j + dy[k] < W && S[i + dx[k]][j + dy[k]] == '#') {
            ans[i][j]++;
          }
        }
      }
    }
  }

  REP(i, H) {
    REP(j, W) {
      if (S[i][j] == '#')
        cout << S[i][j];
      else
        cout << ans[i][j];
    }
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 256
package main

import (
        "fmt"
)

func solution(d, t, s int) string {
        if s*t >= d {
                return "Yes"
        }
        return "No"
}

func main() {
        var d, t, s int
        fmt.Scan(&d, &t, &s)
        fmt.Println(solution(d, t, s))
}

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

def search(keta, num):
  if keta == 0:
    if '0' in str(int(num)):
      return 0
    elif '3' in num and '5' in num and '7' in num:
      if int(num) <= N:
        return 1
      else:
        return 0
    else:
      return 0
  else:
    return search(keta-1, num + '0') + search(keta-1, num + '3') + search(keta-1, num + '5') + search(keta-1, num + '7')

keta = len(str(N))

ans = search(keta, '')
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    rep(i,0,n-1) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> ord;
    vector<bool> vis(n);
    vector<vector<int>> ch(n);
    function<void(int)> dfs = [&](int u) {
        vis[u] = true;
        ord.push_back(u);
        for(int v: g[u]) {
            if(!vis[v]) {
                dfs(v);
                ch[u].push_back(v);
            }
        }
    };
    dfs(0);
    auto rord = ord;
    reverse(all(rord));
    vector<ll> dp1(n);
    for(int u: rord) {
        ll prod = 1;
        for(int v: ch[u]) prod = (prod*dp1[v])%m;
        dp1[u] = (prod+1)%m;
    }
    vector<ll> dp2(n,1);
    for(int u: ord) {
        int k = ch[u].size();
        vector<ll> p1(k+1,1), p2(k+1,1);
        rep(j,1,k) p1[j]=(dp1[ch[u][j-1]]*p1[j-1])%m;
        for(int j=k-1;j>=0;--j) {
            p2[j] = (dp1[ch[u][j]]*p2[j+1])%m;
        }
        rep(j,0,k) {
            dp2[ch[u][j]] = (1+(dp2[u]*((p1[j]*p2[j+1])%m)))%m;
        }
    }
    rep(i,0,n) {
        ll ans = dp2[i];
        for(int v:ch[i]) ans = (ans*dp1[v])%m;
        cout << ans << "\n";
    }
} 


Measured memory_bytes: 18556
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
/*answer*/
    int n, i, j, max, min, sum, a;

    for(;;){
      n = sc.nextInt();
      if(n == 0)break;

      max = 0;
      min = 500;
      for(i = 0;i < n;i++){
        sum = 0;
        for(j = 0;j < 5;j++){
          a = sc.nextInt();
          sum += a;
        }
        if(max < sum)max = sum;
        if(min > sum)min = sum;
      }
      System.out.println(max + " " + min);
    }
/*end*/
    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 33592
from collections import deque, defaultdict

def read_input():
    n, k, l = map(int, input().split())
    roads = []
    for i in range(k):
        p, q = map(int, input().split())
        roads.append((p, q))

    rails = []
    for j in range(l):
        r, s = map(int, input().split())
        rails.append((r, s))

    return n, k, l, roads, rails


def set_ids(nodes, paths):
    edge_table = {n: [] for n in nodes}

    for p in paths:
        edge_table[p[0]].append(p[1])
        edge_table[p[1]].append(p[0])

    ids = [-1] * (len(nodes) + 1)
    q = deque()
    start = 1
    group = 1
    while True:
        # まだセットしていないnodeを見つける
        while ids[start] != -1:
            start += 1
            if start > len(nodes):
                return ids

        q.appendleft(start)
        while len(q) > 0:
            curr = q.popleft()
            ids[curr] = group

            for node in edge_table[curr]:
                if ids[node] == -1:
                    q.appendleft(node)
        group += 1


def submit():
    n, k, l, roads, rails = read_input()
    nodes = list(range(1, n + 1))

    road_ids = set_ids(nodes, roads)
    rail_ids = set_ids(nodes, rails)

    count = defaultdict(int)
    for node in nodes:
        count[(road_ids[node], rail_ids[node])] += 1

    print(' '.join([str(count[(road_ids[node], rail_ids[node])]) for node in nodes]))


if __name__ == '__main__':
    submit()


Measured memory_bytes: 127696
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
  int n, a[101], max, min, ans;
  ans = max - min;
  cin >> n;

  for(int i=0; i<n; i++){
    cin >> a[i];
  }

  max = a[0];
  min = a[0];

  for(int i=1; i<n; i++){
    if(a[i]>max){
    max = a[i];
    }
    if(a[i]<min){
    min = a[i];
    }
  }
  cout << max - min << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}
const int N=1e5+5;
int n,a[N],ans;
signed main(){
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	sort(a+1,a+1+n,greater<int>());
	for(int i=1;i<=n;i++) if(i>=a[i+1]){
		for(int j=i+1;a[j]==i;j++)
			ans^=1;
		if(ans||(a[i]-i)&1) puts("First");
		else puts("Second");
		return 0;
	}
}

Measured memory_bytes: 1024
buf=input()
buf=buf.split(" ")
a=int(buf[0])
b=int(buf[1])
k=int(buf[2])

r=[]

if a>b:
  c=range(1,a+1)
else:
  c=range(1,b+1)

for x in c:
  if a % x==0 and b%x==0:
    r.append(x)

print(r[-1*k])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for (ll i=0; i<n; ++i)
#define all(c) begin(c),end(c)
#define PI acos(-1)
#define oo LLONG_MAX
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
/*
1
+ (n-5)C1
+ (n-7)C2
+ (n-9)C3
+
*/
const int MAX = 2000010;
const int MOD = 1000000007;

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

void COMinit(){
  fac[0] = fac[1]=1;
  finv[0] = finv[1]=1;
  inv[1] = 1;
  for(int i=2; i<MAX; i++){
    fac[i] = fac[i-1] * i % MOD;
    inv[i] = MOD-inv[MOD%i] * (MOD/i) % MOD;
    finv[i] = finv[i-1] * inv[i] % MOD;//逆元の階上
  }
}

ll COM(int n, int k){
  if (n<k)
    return 0;
  if (n<0 || k<0)
    return 0;
  return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  COMinit();
  
  ll N, ans = 1;
  cin >> N;
  if (N <= 2){
    cout << 0 << endl;
    return 0;
  }
  ll tmp = 5, i=1;
  while(N - tmp > 0){
    ans += COM(N-tmp, i);
    ans %= MOD;
    i++;
    tmp += 2;
  }
  cout << ans << endl;
}


Measured memory_bytes: 50504
s = input()
last = 'R'
count = 0

lst =[]
for i in range(len(s)):
  if last == s[i]:
    count += 1
  else:
    lst.append(count)
    count = 1
    last = s[i]
    
lst.append(count)

ans = []

for i in range(0, len(lst), 2):
  ans.extend([0] * (lst[i] - 1))
  count_l = 0
  count_r = 0
  if lst[i] % 2 != 0:
    count_l += lst[i] //2 + 1
    count_r += lst[i] //2
  else:
    count_l += lst[i] //2
    count_r += lst[i] //2
  
  if lst[i+1] % 2 != 0:
    count_r += lst[i+1] //2 + 1
    count_l += lst[i+1] //2
  else:
    count_l += lst[i+1] //2
    count_r += lst[i+1] //2
    
  ans.append(count_l)
  ans.append(count_r)
  
  ans.extend([0] * (lst[i+1] - 1))
  
ans = map(str,ans)

print(' '.join(ans))

Measured memory_bytes: 11132
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <utility>
using namespace std;

#define MOD 1000000007
#define INF 1e9+7
#define INF_LONG 1e18
#define rep(i, n) for(int i=0; i<n; ++i)
#define rrep(i, m, n) for(int i=m; i<n; ++i)
typedef long long ll;

#define MAX_N 100000
#define MAX_M 100000
#define MAX_V 100
#define MAX_E 100
#define MAX_Q 100000

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

int ddx[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int ddy[] = {0, -1, 0, 1, 1, 1, -1, -1};

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



int main() {

  int n, f = 0;
  string s, t;

  cin >> n >> s;

  if(n%2!=0) {
    f = 1;
  }else {
    for(int i=0; i<n/2; ++i) {
      t += s[i];
    }
    for(int i=n/2; i<n; ++i) {
      if(t[i-n/2]!=s[i]) {
        f = 1;
        break;
      }
    }
  }

  if(!f) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int w, n;
	int a[30], b[30];
	int numbers[30];
	int i, buf;
	
	scanf("%d %d", &w, &n);
	
	for (i = 0; i < w; i++){
		numbers[i] = i + 1;
	}
	
	for (i = 0; i < n; i++){
		scanf("%d,%d", &a[i], &b[i]);
	}
	
	for (i = 0; i < n; i++){
		buf = numbers[a[i] - 1];
		numbers[a[i] - 1] = numbers[b[i] - 1];
		numbers[b[i] - 1] = buf;
	}
	
	for (i = 0; i < w; i++){
		printf("%d\n", numbers[i]);
	}
	
	return (0);
}

Measured memory_bytes: 596