akhauriyash/Code-Regression huggingface dataset:
s = input()
k = int(input())

def replacePoint(s):
    arr = [-1]
    for i in range(len(s)):
        if arr[-1] != i-1:
            if s[i] == s[i-1]:
                arr.append(i)
    arr.remove(-1)
    return arr

double = s*2
triple = s*3
arr = replacePoint(s)
darr = replacePoint(double)
tarr = replacePoint(triple)
a = len(arr)
b = len(darr) - len(arr)

if arr+[i+len(s) for i in arr] == darr:
    print(a*k)
elif darr+[i+len(s)*2 for i in arr] == tarr:
    print(a*((k+1)//2)+b*(k//2))
else:
    print(a+b*(k-1))


Measured memory_bytes: 3064
import heapq
def dijkstra(start,goal,graph):

    INF = 2 << 20
    node_num = len(graph) 
    visited = [False] * node_num
    costs = [INF] * node_num
    pq = []
    costs[start] = 0
    #print costs[start]
    heapq.heappush(pq, [0,start])
    
    while not len(pq) == 0:
        cur_cost,cur_node = heapq.heappop(pq)

        if visited[cur_node]:
            continue
        if all(visited[1:]):
            break

        #print cur_cost,cur_node

        visited[cur_node] = True
        costs[cur_node] = cur_cost
        #print costs
        
        for i in xrange(node_num):
            if not visited[i]:
                heapq.heappush(pq,[graph[cur_node][i] + costs[cur_node],i])
    return costs[goal]

n = input()
m = input()
INF = 2 << 20
graph = [[INF] * (n+1) for _ in xrange(n+1)]
for _ in xrange(m):
    a,b,c,d = map(int,raw_input().split(","))
    #graph[from][to] = cost
    graph[a][b] = c
    graph[b][a] = d
home,shop,reward,price = map(int,raw_input().split(","))
cost = dijkstra(home,shop,graph) + dijkstra(shop,home,graph)
print reward - price - cost

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

int main() {

  int A,B;
  cin >> A >> B;
  int sum = 0;
  for (int i = A; i <= B; i++) {
  	//i 桁数調査
  	int j = i;
  	int keta = 0;
  	while(j > 0)
  	{
  		keta++;
  		j /= 10;
  	}
  	
  	//iが回文数かを調査し回文数ならカウントアップ
  	for(int k =0;k < (keta / 2);k++)
  	{
  		int c=i,d=0;
  		for(int l =0;l < k+1;l++)
  		{
  			d = c % 10;
  			c /= 10;
  		}
  		int e=i,f=0;
  		for(int m = 0;m < keta-k;m++)
  		{
  			f = e % 10;
  			e /= 10;
  		}
  		if(d == f && k == (keta/2)-1)
  		{
  			sum++;
  		}
  		else if(d == f){}
  		else
  		{
  			break;
  		}
  	}
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;



int main(){
    ll n; cin >> n;
    vector<pair<ll,P>> v(n);
    rep(i,n){
        ll x,y,h; cin >> x >> y >> h;
        v[i].first = h;
        v[i].second.first = x;
        v[i].second.second = y;
    }
    sort(v.rbegin(), v.rend());
    ll H=-1,X=-1,Y=-1;
    rep(xx,101){
        rep(yy,101){
            ll hh = v[0].first + abs(xx-v[0].second.first) + abs(yy-v[0].second.second);
            ll p[101][101];
            rep(i,101){
                rep(j,101){
                    p[i][j] = max(0LL,hh - abs(xx-i) - abs(yy-j));
                }
            }
            bool flag = true;
            rep(k,n){
                ll h,x,y;
                h = v[k].first;
                x = v[k].second.first;
                y = v[k].second.second;
                if(p[x][y] != h){
                    flag = false;
                    break;
                }
            }
            if(flag){
                H = hh;
                X = xx;
                Y = yy;
                break;
            }
        }
        if(H!=-1 && X!=-1 && Y!=-1) break;
    }
    printf("%lld %lld %lld",X,Y,H);
}


Measured memory_bytes: 384
// Aizu Vol-6 0631: Point Card
// 2017.9.4 bal4u@uu

#include <stdio.h>


int main()
{
	int m, n, i, a, b, min, ans;

	scanf("%d%d", &n, &m);
	for (ans = 0, min = n + n, i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		if (a < n) { ans += n - a; if (a < min) min = a; }
	}
	if (ans > 0) ans -= n - min;
	printf("%d\n", ans);
	return 0;
}

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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    int i,j;
    int max_number = 1e6;
    vector<int> era(max_number+1, 0);
    for(i = 2;i <= sqrt(max_number);++i){
        if(!era.at(i)){
            for(j = 2*i;j <= max_number;j += i){
                if(!era.at(j)) era.at(j) = i;
            }
        }
    }
    int n;
    cin >> n;
    vector<int> a(n);
    cin >> a.at(0);
    int tmp = a.at(0);
    for(i = 1;i < n;++i){
        cin >> a.at(i);
        tmp = gcd(tmp, a.at(i));
    }
    if(tmp != 1){
        cout << "not coprime" << endl;
        return 0;
    }
    vector<bool> v(1e6+1, false);
    rep(i,n){
        if(era.at(a.at(i)) == 0){
            if(a.at(i) == 1) continue;
            if(v.at(a.at(i))){
                cout << "setwise coprime" << endl;
                return 0;
            }else v.at(a.at(i)) = true;
        }else{
            for(j = era.at(a.at(i));j <= sqrt(a.at(i));++j){
                if(a.at(i) == 1) break;
                if(a.at(i)%j == 0){
                    if(v.at(j)){
                        cout << "setwise coprime" << endl;
                        return 0;
                    }else{
                        v.at(j) = true;
                        while(a.at(i)%j == 0) a.at(i) /= j;
                    }
                }
            }
            if(a.at(i) != 1){
                if(v.at(a.at(i))){
                    cout << "setwise coprime" << endl;
                    return 0;
                }else v.at(a.at(i)) = true;
            }
        }
    }
    cout << "pairwise coprime" << endl;

    return 0;
}

Measured memory_bytes: 11228
a,b,k=input().split()
aa=int(a)
bb=int(b)
kk=int(k)
res=(aa+bb)-kk
if res<=0:
    print(0,'',0)
elif aa>kk:
    print(aa-kk,'',bb)
elif aa<=kk:
    print(0,'',res)

Measured memory_bytes: 3060
#include <stdio.h>
#include <math.h>
#define TRUE 1
#define FALSE 0
#define MAX 10000
int isprime(int);
int main(){

  int i;
  int n,jud,sum=0;
  int arry[MAX];

  
  scanf("%d",&n);

  for(i=0;i<n;i++){
    
    scanf("%d",&arry[i]);
    if(arry[i]<2 && 1000000000<arry[i])break;
    
  }

  for(i=0;i<n;i++){
   jud=isprime(arry[i]);

  if(jud==TRUE)sum++;
  else continue;
  }

  printf("%d\n",sum);
  
  return 0;

}

int isprime(int x){

  int i=3;
  int sx;
  
  if(x==2)return TRUE;

  else if(x<2 || x%2==0)return FALSE;

  sx=sqrt(x);
  
  while(i<=sx){

    if(x%i==0)return FALSE;

    else i=i+2;
  }

  return TRUE;
  
}
  

Measured memory_bytes: 628
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

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

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

trait Joinable {
    fn join(self, sep: &str) -> String;
}

impl<U: ToString, T: Iterator<Item = U>> Joinable for T {
    fn join(self, sep: &str) -> String {
        self.map(|x| x.to_string()).collect::<Vec<_>>().join(sep)
    }
}

const MAX: i64 = 3234566667;

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let K: usize = sc.get();
    let mut q = VecDeque::new();
    let mut ans = Vec::new();
    for i in 1..10 {
        q.push_front(i);
        ans.push(i);
    }
    'outer: while let Some(i) = q.pop_back() {
        let d = i % 10;
        for n in max(0, d - 1)..min(10, d + 2) {
            q.push_front(i * 10 + n);
            ans.push(i * 10 + n);
            if i * 10 + n >= MAX {
                break 'outer;
            }
        }
    }
    println!("{}", ans[K-1]);
}


Measured memory_bytes: 6396
#include<iostream>
using namespace std;
int main()
{
	string s;
	cin>>s;
	for(int i=0;i<5;i++)
	{
            cout<<s[i];
    }
      cout<<" ";

       	for(int i=6;i<13;i++)
   	{
       cout<<s[i];
    }
      cout<<" ";
	

      	for(int i=14;i<19;i++)
    {
       cout<<s[i];
    }
	    
	
	
	
}


Measured memory_bytes: 256
from collections import deque
N = int(input())
A = deque(map(int, input().split()))
B = deque(map(int, input().split()))
ans = 0
tmp = A.popleft()
while A:
  b = B.popleft()
  nxt = A.popleft()
  ans += min(b, tmp + nxt)
  if b >= tmp + nxt:
    tmp = 0
  elif tmp + nxt > b >= tmp:
    tmp = tmp + nxt - b
  else:
    tmp = nxt
print(ans)

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)

#define mod 1e9+7;
#define inf 1e18+7;

typedef long long ll;

int main() {
    ll n;cin>>n;

    vector<ll>x(5);
    rep(i,5){
        cin>>x[i];
    }
    sort(x.begin(),x.end());

    ll ans=4+(n+x[0]-1)/x[0];

    cout<<ans<<endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

int main() {
  int t;
  string num;
  while(cin >> t >> num, t||num!="0") {
    int n = num.size();
    vector<string> ansv;
    int ans = 0;
    bool reject = 0;
    REP(S, 1<<(n-1)) {
      int last = 0;
      vector<string> v;
      REP(i, n-1) {
        if (S>>i & 1) {
          v.push_back(num.substr(last, i-last+1));
          last = i+1;
        }
      }
      v.push_back(num.substr(last));
      int sum = 0;
      FOR(it, v)
        sum += atoi(it->c_str());
      if (sum > ans && sum <= t) {
        ans = sum;
        ansv = v;
        reject = 0;
      } else if (sum == ans) {
        // cout << "hgoidjso" << endl;
        // FOR(it, ansv) {
        //   cout << " " << *it;
        // }
        // cout << endl;
        // FOR(it,v) {
        //   cout << " " << *it;
        // }
        // cout << endl;
        reject = 1;
      }
    }
    if (reject) {
      cout << "rejected" <<endl;
    } else if (ans == 0) {
      cout << "error" << endl;
    } else {
      cout << ans;
      FOR(it, ansv) {
        cout << " " << *it;
      }
      cout << endl;
    }
  }
}

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

#define MOD 998244353

long long kai[400010];

void init(){
    kai[0] = 1;
    for(int i = 1;i < 400010;i++){
        kai[i] = kai[i-1] * i % MOD;
    }
    return;
}

long long pow_mod(long long n, long long m){
    long long ans = 1;
    while(m > 0){
        if(m & 1) ans = ans * n % MOD;
        n = n*n % MOD;
        m >>= 1;
    }
    return ans;
}

long long combi(int n, int r){
    return (kai[n] * pow_mod(kai[r], MOD-2) % MOD) * pow_mod(kai[n-r], MOD-2) % MOD;
}

int main(){
    int n;
    long long a, b, k;
    cin >> n >> a >> b >> k;

    init();

    long long ans = 0;
    for(int i = 0;i <= n;i++){
        if(k-(a*i) >= 0 && (k-(a*i)) % b == 0 && (k-(a*i)) / b <= n){
            ans = (ans + (combi(n, i) * combi(n, (k-(a*i)) / b)) % MOD) % MOD;
        }
    }

    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
typedef vector<long long> VLL;
typedef vector<pair<int,int>> VP;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
/*--------------------------------------------*/

int main(){
  int r;
  cin >> r;
  
  cout << r * r << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    string S;
    LLONG K;
    cin >> S >> K;
    if (K == 1)
    {
        cout << S[0] << endl;
    }
    else
    {
        for (int i = 0; i < static_cast<int>(S.length()); ++i)
        {
            if (i + 1 == K)
            {
                cout << S[i] << endl;
                break;
            }
            if (S[i] != '1')
            {
                cout << S[i] << endl;
                break;
            }
        }
    }
}


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

using namespace std;
struct Node{
    int key;
    Node *parent, *left, *right;
};

Node *root, *NIL;

void Preorder(Node *root) {
    if ( root != NIL ) {
    cout << " " << root->key;
    Preorder(root->left);
    Preorder(root->right);
   }
}

void Inorder(Node *root) {
    if ( root != NIL ) {
       Inorder( root->left);
      cout << " " << root->key;
       Inorder( root->right);
     }
}

void Postorder(Node *root) {
    if ( root != NIL ) {
       Postorder( root->left);
       Postorder( root->right);
       cout << " " << root->key;
     }
}
void insert(int key) {
	Node *p=new Node;
	p->key=key;
	p->left=NIL;
	p->right=NIL;

	Node *x = root;
	Node *y = NIL;

	while(x != NIL ){
		y=x;
		if ( p->key > x->key ) x = x->right;
		else x = x->left;

	}
    
    p->parent = y;
    if( y == NIL ) root = p;
    else {
    	if ( p->key > y->key ) y->right = p;
    	else y->left = p;
    }

	//delete p;

}
int main() {
    int n;
    string op;
    int key;

    cin >> n;
    while ( n-- ) {
    	cin >> op;
    	if ( op == "insert" ) {
    		cin >> key;
    		insert(key);
    	} else if ( op == "print" ){
    		Inorder(root);
    		cout << endl;
    		Preorder(root);
    		cout << endl;
    	}
    }
	return 0;
}


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

int main() {
  ll l,r;
  int ans = 3000;
  cin >> l >> r;
  r = min(r, l+3000);
  for(ll i = l; i < r; ++i) {
    for(ll j = i+1; j <= r; ++j) {
      int x = i*j%mod;
      ans = min(ans, x);
    }
  }
  cout << ans << endl;
  return 0;
}

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



signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    
    int n;
    cin>>n;
    string s[n];
    int p = 0,cnt=1e9;
    for(int i=0;i<n;i++){
        cin>>s[i];
        int ret = 0;
        for(int j=0;j<n;j++){
            if(s[i][j]=='1') ret++;
        }
        if(cnt>ret){
            cnt = ret;
            p = i;
        }
    }
    int ans = 0;
    for(int h=0;h<n;h++){
        int c[n]={};
        queue<int> st;
        st.push(h);
        c[h] = 1;
        while(!st.empty()){
            ll t = st.front(); st.pop();
            for(int i=0;i<n;i++){
                if(!c[i] && s[t][i]=='1'){
                    st.push(i);
                    c[i] = c[t] + 1;
                }
                else if(c[i] && s[t][i]=='1'){
                    if(c[i]!=c[t]+1 && c[i]!=c[t]-1){
                        cout << -1 << endl;
                        return 0;
                    }
                }
            }
        }
        for(int i=0;i<n;i++){
            if(c[i]==0){
                cout << -1  << endl;
                return 0;
            }
            ans = max(ans,c[i]);
            for(int j=0;j<n;j++){
                if(s[i][j]=='1'){
                    if(c[i]+1!=c[j] && c[i]-1!=c[j]){
                        cout << -1 << endl;
                        return 0;
                    }
                }
            }
        }
    }
    cout << ans << endl;


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using ll = long long;
using P = pair<ll, ll>;

const ll infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

void fail() {
    cout << -1 << endl;
    exit(0);
}

int main(){
    string s, base = "AKIHABARA", base2 = "KIHBR";
    cin >> s;

    ll j = 0;
    for(ll i=0; i < ll(base.size()); i++){
        if(s[j] == base[i]) j++;
    }
    ll k = 0;
    for(ll i=0; i < ll(s.size()); i++){
        if(base2[k] == s[i]) k++;
    }
    if(j == ll(s.size()) && k == ll(base2.size())){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(long long x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl
#define NN 1000000007
#define all(x) x.begin(),x.end()
typedef pair<long long,long long> P;
typedef pair<long long,P> PP;
long long a[200005];
long long n;
long long M;
long long ans;
long long torino;
long long tor[200005];
long long mm(long long aa,long long bb)
{
	if(aa<bb)return bb;
	else return aa;
}
int main()
{
	cin>>n;
	rep(i,n)cin>>a[i];
	if(n==2)
	{
		cout<<2<<endl;
		return 0;
	}
	rep2(i,1,n)
	{
		if(a[i]%2==0)
		{
			M=a[i]/2;
		}
		else M=a[i]/2+1;
		tor[i]=mm(i+1-M,0);
		tor[i]=mm(tor[i],tor[i-1]);
	}
	ans=1;
	rep2(i,1,n)
	{
		ans*=(i+1-tor[i-1]);
		ans%=NN;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.IO.Pipes;
using System.Linq;
using System.Numerics;
using System.Text.RegularExpressions;
using System.Threading;

namespace Atcoder
{
	class Program
	{
		//string s = Console.ReadLine();
		//int[] intArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
		//int H = intArray[0];
		//int W = intArray[1];
		//int N = int.Parse(Console.ReadLine());
		//List<int> A = new List<int>(Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray());
		//Boolean ok = false;

		//Console.WriteLine(ans);
		//Console.WriteLine("Yes");
		//Console.WriteLine("No");
		//Console.ReadKey();
		//Console.WriteLine(cnt);

		//string[] strArray = Console.ReadLine().Split(' ').ToArray();
		//string S = strArray[0];
		//string T = strArray[1];
		static void Main(string[] args)
		{
			int N = int.Parse(Console.ReadLine());
			string[] ST = Console.ReadLine().Split(' ').ToArray();

			string S = ST[0];
			string T = ST[1];
			string ans = "";

			for (int i = 0; i < N; i++)
				ans += S[i] + "" + T[i];

			Console.WriteLine(ans);
		}

		/// <summary>
		/// 回文
		/// </summary>
		/// <param name="Target"></param>
		/// <param name="len"></param>
		/// <returns></returns>
		static bool Palindrome(string Target , int len)
        {
			bool yes = true;

			for(int i = 0;i < len; i++)
            {
				if(Target[i] != Target[len - 1 - i])
                {
					yes = false;
					break;
                }
            }
			return yes;
        }

		/// <summary>
		/// アナグラム
		/// </summary>
		/// <param name="word1"></param>
		/// <param name="word2"></param>
		/// <returns></returns>
		static bool IsAnagramOf(string word1, string word2)
		{
			return word1.OrderBy(x => x).SequenceEqual(word2.OrderBy(x => x));
		}
		/// <summary>
		/// 最小公倍数
		/// </summary>
		/// <param name="a"></param>
		/// <param name="b"></param>
		/// <returns></returns>
		public static BigInteger Lcm(BigInteger a, BigInteger b)
		{
			return a * b / Gcd(a, b);
		}

		/// <summary>
		/// 最大公約数
		/// </summary>
		/// <param name="a"></param>
		/// <param name="b"></param>
		/// <returns></returns>
		public static BigInteger Gcd(BigInteger a, BigInteger b)
		{
			if (a < b)
				// 引数を入替えて自分を呼び出す
				return Gcd(b, a);
			while (b != 0)
			{
				var remainder = a % b;
				a = b;
				b = remainder;
			}
			return a;
		}
	}
}

Measured memory_bytes: 27984
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		Point[] p=new Point[n];
		int count=0;
		long ans=0;
		for(int i = 0; i<n; i++){
			long a=sc.nextLong();
			int b = sc.nextInt();
			p[i]=new Point(a,b);
		}
		Arrays.sort(p,Comparator.comparing(Point::getX));
		while(m>0){
			if(p[count].y<m){
				m-=p[count].y;
				ans+=p[count].x*p[count].y;
			}else{
				ans+=p[count].x*m;
				m=0;
			}
			count++;
		}
		System.out.println(ans);
	}
	static class Point{
		long x;
		int y;
		public Point(long x, int y){
			this.x=x;
			this.y=y;
		}
		
		public long getX(){
			return x;
		}
		 
		public int getY(){
			return y;
		}
	}
}

Measured memory_bytes: 93936
#include <bits/stdc++.h>
#define PB push_back
#define LL long long
#define SZ(a) (int)(a.size())
using namespace std;
LL ans = 0;
LL N;
void check(LL x)
{
    if(x == 0)
        return;
    if(N % x == N / x)
        ans += x;
}
int main() {
    
    cin >> N;
    
    for(LL i = 1; i * i <= N; i++)
    {
        if(N % i == 0)
        {
            LL div1 = N / i;
            check(div1 - 1);
            if(i != div1)
            {
                div1 = i;
                check(div1 - 1);
            }
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
function Main(input) {
  let n = Number(input);
  for (let i = 1; i <= n; i++) {
    if (isValid(i)) {
      process.stdout.write(" " + String(i));
    }
  }
  console.log();
}

function isValid(x) {
  if (x % 3 === 0) {
    return true;
  }
  while (x !== 0) {
    if (x % 10 === 3) {
      return true;
    }
    x = parseInt(x / 10, 10);
  }
  return false;
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 19532
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N;
	cin >> N;
	VI x(N), y(N), h(N);
	bool P = true;

	REP(i, N) {
		cin >> x[i] >> y[i] >> h[i];
		if (h[i])P = false;
	}
	if (P) {
		eFOR(i, 0, 100) {
			eFOR(j, 0, 100) {
				bool F = true;
				int tmp = abs(x[0]-i)+abs(y[0]-j);

				FOR(k,1, N) {
					if (abs(x[k] - i) + abs(y[k] - j) != tmp) {
						F = false;
						break;
					}			
				}
				if (F) {
					cout << i << " " << j << " " << tmp << endl;
					return 0;
				}
			}
		}
	}

	





	eFOR(i,0, 100) {
		eFOR(j,0, 100) {
			bool F = true;
			int tmp = INF;

			REP(k, N) {				
				
				if (h[k]>0 && tmp==INF){

					tmp = abs(x[k] - i) + abs(y[k] - j);
					tmp += h[k];

				}
				else if (h[k] > 0) {
					if (tmp - abs(x[k] - i) - abs(y[k] - j)!=h[k]) {
						F = false;
						break;
					}
				}
				else if (tmp == INF)continue;
				else {
					if (tmp - abs(x[k] - i) - abs(y[k] - j)>0) {
						F = false;
						break;
					}
				}
			}
			REP(k, N) {

				if (h[k] > 0) {
					if (tmp - abs(x[k] - i) - abs(y[k] - j) != h[k]) {
						F = false;
						break;
					}
				}
				else {
					if (tmp - abs(x[k] - i) - abs(y[k] - j) > 0) {
						F = false;
						break;
					}
				}
			}
			if (F) {
				cout << i << " " << j << " " << tmp << endl;
				return 0;
			}
		}
	}

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n; cin>>n;
    vector <int> a(n),b(n);
    map <int,int> ma;
    for(int i=0;i<n;i++){
        cin>>a[i]; b[i]=a[i];
        ma[a[i]]++;
    }
    int cnt0=count(a.begin(), a.end(), 0);
    
    if(cnt0 == n) {cout<<"Yes"<<endl; return 0;}
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    if(n%3 != 0) {cout<<"No"<<endl; return 0;}
    else{
        if((cnt0== n/3&&ma.size()==2)) {cout<<"Yes"<<endl; return 0;}
        if(ma.size()==3){
            
            if(a[0]==(a[1]^a[2]) && a[1] == (a[2]^a[0]) && a[2] == (a[0]^a[1])&& count(b.begin(), b.end(), a[0])==count(b.begin(), b.end(), a[1])&&
            count(b.begin(), b.end(), a[2])==count(b.begin(), b.end(), a[1])
            ) {cout<<"Yes"<<endl; return 0;}
        }
    }
    cout<<"No"<<endl;
}


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

const int MAXN = 1000002;
int S[MAXN], T[MAXN];

int main() {
  S[1] = 1;
  for(int i = 0; i*2 < MAXN; ++i) S[i*2] += S[i];
  for(int i = 0; i*3 < MAXN; ++i) S[i*3] += S[i];
  for(int i = 0; i*5 < MAXN; ++i) S[i*5] += S[i];
  for(int i = 0; i+1 < MAXN; ++i) S[i+1] += S[i];
  int n, m;
  while(cin >> m && m) {
    cin >> n;
    cout << S[n] - S[m-1] << endl;
  }
  return 0;
}

Measured memory_bytes: 6932
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,m,cnt,num1,num2,chk;
int head[N],vis[N],col[N],to[N<<1],nxt[N<<1],val[N<<1],stk[3];
ll ans;
inline void add(int u,int v,int w){
	to[++cnt]=v,nxt[cnt]=head[u],val[cnt]=w,head[u]=cnt;
}
inline int tp(int x){ x=(x%3+3)%3; return x; }
void dfs(int u,int c){
	vis[u]=1,col[u]=c,stk[col[u]]++,num1++;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		num2+=(val[i]==1);
		if(!vis[v]) dfs(v,tp(col[u]+val[i]));
		else if(col[v]!=tp(col[u]+val[i])) chk=1;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v,1),add(v,u,-1); }
	for(int i=1;i<=n;i++){
		if(vis[i]) continue; 
		num1=0,num2=0,chk=0; stk[0]=stk[1]=stk[2]=0; 
		dfs(i,0);
		if(chk) ans+=1ll*num1*num1;
		else if(stk[0] && stk[1] && stk[2]) ans+=1ll*stk[0]*stk[1]+1ll*stk[1]*stk[2]+1ll*stk[2]*stk[0];
		else ans+=num2;
	}
	printf("%lld",ans);
}

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

int Y,X;

struct Item{
    int x1,x2,y1,y2;
    set<pair<int,int>> st;
    Item(){
        x1 = y1 = +100;
        x2 = y2 = -100;
    }
    void update(int x,int y){
        x1 = min(x1,x);
        x2 = max(x2,x);
        y1 = min(y1,y);
        y2 = max(y2,y);
        st.insert({x,y});
    }

    bool isRectangle(){
        return (x2-x1+1)*(y2-y1+1) == (int) st.size();
    }
    bool isin(int x,int y){
        return x1<=x && x<=x2 && y1<=y && y<=y2;
    }
};

int main(void){
    int T;
    cin>>T;
    while(T--){
        cin>>Y>>X;
        vector<string> s(Y);
        rep(y,Y) cin>>s[y];
        vector<Item> items(26);
        rep(y,Y)rep(x,X){
            if(s[y][x] == '.') continue;
            int a = s[y][x] - 'A';
            items[a].update(x,y);
        }
        for(auto it=items.begin(); it!=items.end();){
            if((int)it->st.size() == 0){
                it = items.erase(it);
            }else ++it;
        }

        size_t prev = 0;
        while(prev != items.size()){
            prev = items.size();
            for(auto it=items.begin(); it!=items.end();){
                if(it->isRectangle()){
                    for(int x=it->x1; x<=it->x2; x++){
                        for(int y=it->y1; y<=it->y2; y++){
                            for(auto &back : items){
                                if(back.isin(x,y)){
                                    back.update(x,y);
                                }
                            }
                        }
                    }
                    it = items.erase(it);
                }else ++it;
            }
        }
        cout<<(items.size() ? "SUSPICIOUS" : "SAFE")<<endl;
    }
    return 0;
}



Measured memory_bytes: 3116
#!/bin/bash
read w h n

minx=0
maxx=$w
miny=0
maxy=$h
n=$(echo $n | sed "s/\n//")
for i in $(seq 1 $n); do
  read x y a
  a=$(echo $a | sed "s/\n//")
  if [ $a -eq 1 ]; then
    if [ $x -gt $minx ]; then
      minx=$x
    fi
  elif [ $a -eq 2 ]; then
    if [ $x -lt $maxx ]; then
      maxx=$x
    fi
  elif [ $a -eq 3 ]; then
    if [ $y -gt $miny ]; then
      miny=$y
    fi
  elif [ $a -eq 4 ]; then
    if [ $y -lt $maxy ]; then
      maxy=$y
    fi
  fi
done

ans=$(((maxx-minx)*(maxy-miny)))

[ $maxx -lt $minx ] || [ $maxy -lt $miny ] && ans=0

echo $ans


Measured memory_bytes: 824
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#define rep(i,r) for(int i = 0; i < (r); i++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define uint unsigned long long
#define endl '\n'
using namespace std;

const int mn = 2e5 + 10;
int a[mn], b[mn];

signed main() {
    fastio;
    int n;
    cin >> n;
    int maxi = 0, res = 0;
    rep(i, n) {
        cin >> a[i];
        int ai = a[i];
        maxi = max(maxi, ai);
        if (ai < maxi) {
            res += maxi - ai;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 4732
#include<stdio.h>
int main(void){
	int a,b;

scanf("%d%d",&a,&b);

if(a<b){
	printf("a < b\n");
}else if(a>b){
	printf("a > b\n");
}else{
	printf("a == b\n");
}
return 0 ;
}

Measured memory_bytes: 580
#include<iostream>
#include<cmath>
using namespace std;
#define MAX 1000000

bool prime[MAX]={};

void run(){
  for(int i=2;i<MAX;i++){
    prime[i]=true;
  } 

  for(int i=2;i<MAX;i++){
    if(!prime[i])continue;
    for(int j=2;j*i<MAX;j++){//i*1 is prime number
      prime[i*j]=false;
    }
  }
  return;
}

int main(){

  run();
  
  int n;
  while(cin>>n){
    int sum=0;
    for(int i=2; i<=n; i++){
      if(prime[i])sum++;
    }
    cout<<sum<<endl;
  }
  return 0;

}

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

using LL = long long;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

const string YES = "YES";
const string NO = "NO";

void solve(long long N, std::vector<long long> A) {
  // solver code

  sort(A.begin(), A.end());

  for (int i = 0; i < N - 1; i++) {
    if (A[i] >= A[i + 1]) {
      cout << NO << endl;
      return;
    }
  }

  cout << YES << endl;
}

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


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<stdio.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;


#define ll                  long long
#define scl(n)              scanf("%lld",&n)
#define scll(n, m)              scanf("%lld%lld",&n, &m)
#define scc(c)	            scanf("%c",&c)
#define fr(i,n)             for (ll i=0;i<n;i++)
#define fr1(i,n)            for(ll i=1;i<=n;i++)
#define pfl(x)              printf("%lld\n",x)
#define pb                  push_back
#define debug               cout<<"I am here"<<endl;
#define pno                 cout<<"NO"<<endl
#define pys                 cout<<"YES"<<endl
#define tcas(i,t)           for(ll i=1;i<=t;i++)

#define l(s)                s.size()
#define asort(a)            sort(a,a+n)
#define all(x) 	            (x).begin(), (x).end()
#define dsort(a)            sort(a,a+n,greater<int>())
#define vasort(v)           sort(v.begin(), v.end());
#define vdsort(v)           sort(v.begin(), v.end(),greater<int>());
#define uniquee(x)          x.erase(unique(x.begin(), x.end()),x.end())
#define pn                  printf("\n")
#define el                  cout<<endl
#define md                  1000000007
#define inf                 9e18

#define N 100006
ll dp[N];

int main()
{
    ll m,n,b,c,d,i,j,k,x,y,z,l,q,r;
    string s,s1, s2, s3, s4;

    ll cnt=0,cn=0,ans=0,sum=0 ;
    scll(n, k);
    ll a[n];

    vector<ll>dp(n, inf);

    fr(i,n)cin>>a[i];

    dp[0]=0;

    fr(i, n)
    {
        for(j=i+1; j<=i+k; j++)
        {
            if(j<n )
            {
                dp[j]=min(dp[j], dp[i]+abs(a[i]-a[j] )  );
               // cout<<dp[i]<<" "<<dp[j]<<endl;
            }
        }
    }

    ans=dp[n-1];

    cout<<ans;
    pn;

    return 0;
}

///***************Before submit*****************

///    ****Please check all base case output***
///    *check for integer overflow,array bounds
///    *check for n=1





Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <queue>

using namespace std;
typedef long long ll;
#define MOD 1000000007

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

    int H[N];
    for(int i=0; i<N; i++) cin >> H[i];

    int ans = 0, tmp = 0;

    for(int i=1; i<N; i++) {
        if(H[i-1]>=H[i]) {
            tmp++;
            ans = max(ans, tmp);
        } else {
            tmp = 0;
        }
    }

    cout << ans << endl;

    return 0;
}

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

typedef long long LL;
const int MAX_N = 56;

int a[MAX_N];

LL pow(LL a,LL n) {
    LL ret=1;
    for (int i=0;n>i;i++) ret*=a;
    return ret;
}

int main () {
    int n;
    int p;
    scanf("%d %d",&n,&p);
    int cnt[2] = {0,0};
    for (int i=1;n>=i;i++) {
        scanf("%d",&a[i]);
        a[i]%=2;
        cnt[ a[i] ]++;
    }
    LL ans;
    if (p==0) {
        if (cnt[1] == 0) printf("%lld\n",pow(2,cnt[0]));
        else printf("%lld\n",pow(2,cnt[0]+cnt[1]-1));
    }
    else if (p==1) {
        if (cnt[1] == 0) puts("0");
        else {
            printf("%lld\n",pow(2,cnt[0]+cnt[1]-1));
        }
    }
}



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

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<int, int> Pair;
typedef pair<ll, ll> PL;
typedef priority_queue<int> PQ;
typedef priority_queue<int, V, greater<int>> PQG;

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

ll n, x;

int main() {
    while(true) {
        cin >> n >> x;
        if(n == 0 && x == 0) {
            return 0;
        }
        ll ans = 0;
        FOR(i, 1, n + 1) FOR(j, i + 1, n + 1) FOR(k, j + 1, n + 1) {
            if(i + j + k == x) ans++;
        }
        cout << ans << "\n";
    }
}



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

  int S,h,m,s;
  scanf("%d",&S);
  h = S / 3600;
  m  = (S - 3600 * h) / 60;
  s = (S - (3600 * h + 60 * m));
  printf("%d:%d:%d\n",h,m,s);

 return 0;
}

Measured memory_bytes: 592
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
using namespace std;

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

int main() {
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    int l[Q], r[Q];
    for (int i = 0; i < Q; i++) {
        scanf("%d %d", &l[i], &r[i]);
        l[i]--;
        r[i]--;
    }

    int sum[N];
    sum[0] = 0;
    int count = 0;
    for (int i = 1; i < N; i++) {
        if (S[i - 1] == 'A' && S[i] == 'C') {
            count++;
        }
        sum[i] = count;
    }
    for (int i = 0; i < Q; i++) {
        printf("%d\n", sum[r[i]] - sum[l[i]]);
    }

    return 0;
}

Measured memory_bytes: 2176
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
using namespace std;

inline char gc() {
//	static char buf[100000],*p1,*p2;
//	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
	return getchar();
}

template<class T>
int read(T &ans) {
	ans=0;char ch=gc();T f=1;
	while(!isdigit(ch)) {
		if(ch==EOF) return -1;
		if(ch=='-') f=-1;
		ch=gc();
	}
	while(isdigit(ch))
		ans=ans*10+ch-'0',ch=gc();
	ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
	return read(a)!=EOF&&read(b)!=EOF?2:EOF;
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
	return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;
}

typedef long long ll;
const int Maxn=110000;
const int inf=0x3f3f3f3f;
const int mod=1000000007;

int n,k,x;
ll f[Maxn],g[Maxn];

signed main() {
//	freopen("test.in","r",stdin);
	read(n,k);
	f[0]=1;
	for(int i=1;i<=n;i++) {
		read(x);
		int sum=0;
		for(int j=0;j<=x;j++) {
			sum+=f[j];
			sum%=mod;
			g[j]=sum;
		}
		for(int l=0,r=x+1;r<=k;l++,r++) {
			sum+=f[r]-f[l];
			sum%=mod;
			sum+=mod;
			sum%=mod;
			g[r]=sum;
		}
		memcpy(f,g,sizeof(f));
	}
	printf("%d",f[k]);
	return 0;
}



Measured memory_bytes: 1792
import java.io.File;
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);
		// Scanner scan = new Scanner(new
		// File("D:\\UserArea\\J0124567\\Downloads\\ALDS1_6_A-in9.txt"));

		int n = scan.nextInt();
		int[] w = new int[n];
		int[] sq = new int[n];
		for (int i = 0; i < n; i++) {
			sq[i] = i;
			w[i] = scan.nextInt();
		}

		QuickSsort(w, sq, 0, n - 1);

		System.out.println(CostOf(w, sq));

		scan.close();
		System.exit(0);
	}

	private static int CostOf(int[] w, int[] sq) {
		int cost = PartCost(w, sq, 0);

		int[] save = new int[sq.length];
		for (int i = 1; i < sq.length; i++)
			if (sq[i] != i) {
				for (int j = i; j < sq.length; j++)
					save[j] = sq[j];
				int savew = w[i];
				w[i] = w[0];
				int pc1 = PartCost(w, sq, i) + (savew + w[0]) * 2;
				w[i] = savew;
				for (int j = i; j < sq.length; j++)
					sq[j] = save[j];
				int pc2 = PartCost(w, sq, i);
				cost += Math.min(pc1, pc2);
			}
		return cost;
	}

	private static int PartCost(int[] w, int[] sq, int fr) {
		int cost = 0;
		while (sq[fr] != fr) {
			int swp = sq[fr];
			cost += (w[fr] + w[swp]);
			sq[fr] = sq[swp];
			sq[swp] = swp;
		}
		return cost;
	}

	private static int xxCostOf(int[] w, int[] sq) {
		int cost = 0;
		for (int i = 0; i < sq.length; i++)
			while (sq[i] != i) {
				int swp = sq[i];
				cost += (w[i] + w[swp]);
				sq[i] = sq[swp];
				sq[swp] = swp;
			}
		return cost;
	}

	private static void QuickSsort(int[] a, int[] sq, int st, int ed) {
		if (st >= ed)
			return;
		int v = Q2sort(a, sq, st, ed);
		QuickSsort(a, sq, st, v - 1);
		QuickSsort(a, sq, v + 1, ed);
	}

	private static int Q2sort(int[] a, int[] sq, int st, int ed) {
		int x = a[ed];
		int i = st - 1;
		for (int j = st; j < ed; j++)
			if (a[j] <= x) {
				i++;
				int tmp = a[j];
				a[j] = a[i];
				a[i] = tmp;
				tmp = sq[j];
				sq[j] = sq[i];
				sq[i] = tmp;
			}
		int tmp = a[i + 1];
		a[i + 1] = a[ed];
		a[ed] = tmp;
		tmp = sq[i + 1];
		sq[i + 1] = sq[ed];
		sq[ed] = tmp;

		return i + 1;
	}

}

Measured memory_bytes: 32048
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline
import itertools
 
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

s = str(input().rstrip())
s = tuple(int(s[i]) for i in range(len(s)))


mylist = [1, 0]
d = []

for i in itertools.product(mylist, repeat = len(s)-1):
    temp = s[0]
    result = 0
    for j, k in zip(s[1:], i):
        if k != 1:
            temp = temp * 10 + j
        else:
            result += temp
            temp = j
    result += temp
    d.append(result)
    
print(sum(d))

Measured memory_bytes: 39664
#include <bits/stdc++.h>                        
#define pb push_back                            
#define mp make_pair                            
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)((x).size())
#define jonathan ios_base::sync_with_stdio(0)
#define livingston cin.tie(0)
using namespace std;                            
                                                
void yes() {cout << "Yes" << endl;}                                               
void no() {cout << "No" << endl;}                                                        
                                                
int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};         
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1}; 

const int INF = 1e9 + 9;
const long long LINF = 1e18 + 8;
const double EPS = 1e-9;
const long long MOD = 1e9 + 7; //998244353
const double PI = acos(-1);

void solve() {
    int n, m; cin >> n >> m;
    vector<long long> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    sort(all(a));
    sort(all(b));
    int i = 0, j = 0;
    long long res = 0;
    while (i < n and j < m) {
        if (a[i] <= b[j]) {
            res += a[i++] * (m + 1 - j);
        } else {
            res += b[j++] * (n + 1 - i);
        }
    } 
    while (i < n) res += a[i++];
    while (j < m) res += b[j++];
    cout << res << endl;
} 

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

Measured memory_bytes: 4776
from fractions import gcd

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

a = A[0]
n = 1
while a % 2 == 0:
    n *= 2
    a //= 2

lcm = 1
for a in A:
    if a % n != 0 or a % (2 * n) == 0:
        print(0)
        exit()
    lcm = lcm * a // gcd(lcm, a)
    if lcm // 2 > M:
        print(0)
        exit()

print((M - lcm // 2) // lcm + 1)

Measured memory_bytes: 16320
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}



fn main() {
    let n = read::<usize>();
    let a = read_vec::<f64>();
    
    let x = calc(n, &a);
    println!("{}", x);
}

fn calc(n: usize, a: &[f64]) -> f64 {
    let mut sum : f64 = 0.0;
    for i in 0..n {
        sum += (1.0f64 / a[i]);
    }
    return 1.0f64 / sum;
}


Measured memory_bytes: 4352
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val N, H = sc.nextInt()
    val A, B = new Array[Int](N)
    (0 until N) foreach { i =>
      val a, b = sc.nextInt()
      A(i) = a
      B(i) = b
    }

    // 常に ai <= bi, 投げた方が高い攻撃力
    // 振る場合, 常に 最大の ai で降った方が良さそう
    // この時最大の ai >= bi の剣は要らない
    // ai より 大きい bi の剣は何本かある
    // 振る順番を無視して考える
    // 最大のa * n 回 攻撃 する場合,
    // 投げた時めちゃくちゃ強い剣も存在するはず..
    // Biでソートしておいて, 途中から 最大のAiより小さくなった時にAiに切り替える
    // 既に使っている場合, 順番を入れ替える事でいける

    def solve(N: Int, H: Int, A: Array[Int], B: Array[Int]): Int = {
      val AMAX = A.max
      def loop(lst: List[Int], rest: Int, count: Int): Int =
        if (rest > 0) {
          lst match {
            case Nil => count + (rest / AMAX.toDouble).ceil.toInt
            case i :: t =>
              if (B(i) > AMAX) loop(t, rest - B(i), count + 1)
              else count + (rest / AMAX.toDouble).ceil.toInt
          }
        } else count
      loop((0 until N).sortBy(i => B(i))(Ordering.Int.reverse).toList, H, 0)
    }

    println(solve(N, H, A, B))
  }

}


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

int main() {
  int A,B;
  cin >> A >> B;
  if (A >= 13) {
    cout << B << endl;
  } else if (A >= 6 && A <= 12) {
    cout << B/2 << endl;
  } else {
    cout << 0 << endl;
  }    
}

Measured memory_bytes: 256