akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>

typedef unsigned long long int uint64;
typedef long long int          int64;
 
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void get_N (int64 *n)
{
  int cnt;
  
  cnt = scanf("%lld", n);

  return;
}

void get_NK (int64 *n, int64 *k)
{
  int cnt;
  
  cnt = scanf("%lld %lld", n, k);

  return;
}

void omit_LF (void)
{
  char c;
  int  cnt;
  
  cnt = scanf("%c", &c);
  return;
}

char *get_S (int64 n)
{
  char *buf;
  int  i;

  buf = malloc((size_t)(n * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  scanf("%s", buf);

  return buf;
}

char *get_SN (int64 max, int64 *size)
{
  char *buf;
  int  i;
  int  n;

  buf = malloc((size_t)(max * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  scanf("%s", buf);

  n = strlen(buf);

  *size = n;
  
  return buf;
}

int64 *get_NSeq (int64 n)
{
  int64 *buf;
  int64 i;

  buf = malloc((size_t)(n * sizeof(int64)));
  for (i=0; i<n; i++) {
    get_N(&buf[i]);
  }

  return buf;
}

typedef struct _tmp_t {
  int64    a;
  int64    b;
} tmp_t;


int compare_a(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->a > y->a) return 1;
  if (x->a < y->a) return -1;

  return 0;
}

int compare_b(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->b > y->b) return 1;
  if (x->b < y->b) return -1;

  return 0;
}

void qsort_a (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_a);
}

void qsort_b (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_b);
}

int main()
{
  char c;
  int  cnt;

  cnt = scanf("%c", &c);

  printf("%c\n", (c+1));

  return 0;
}



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

int main(){
  int n,k=1,i=0;
  cin >>n;
  while(i<n){
    string c;
    cin >>c;
    if(c=="Y"){
      cout <<"Four"<<endl;
      k=0;
      break;
    }
    else{
    i++;}
  }
  if(k!=0){
    cout <<"Three"<<endl;
  }
}
   
  

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#pragma GCC optimize ("O3")

inline static int gl(void){
    int x = 0;
    for(;;){
        unsigned int c = getchar_unlocked() - 48;
        if(c < 10){
            x = x*10 + c;
        }else{
            break;
        }
    }
    return x;
}

inline static int gcd(int a, int b){
    if(a==0) return b;
    if(b==0) return a;
    do{
        int t=a%b;
        a=b;
        b=t;
    }while(b!=0);
    return a;
}

int main(void){
    int n=gl(), s=gl(), g=0, t;
    for(long i=0; i<n; i++){
        t = gl();
        g=gcd(abs(t-s), g);
    }
    printf("%d\n", g);
    return 0;
}


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

string s;

int main(){
	cin.sync_with_stdio(false);
	cin>>s;
	for(ll i=s.length();i>0;){
		if(s.substr(i-5,5)=="dream"||s.substr(i-5,5)=="erase"){
			i-=5;
			continue;
		}
		if(s.substr(i-6,6)=="eraser"){
			i-=6;
			continue;
		}
		if(s.substr(i-7,7)=="dreamer"){
			i-=7;
			continue;
		}
		cout<<"NO"<<endl;
		return 0;
	}
	cout<<"YES"<<endl;
	return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int main(void){
  char str[60];
  long int a,b,k,i;
  
  fgets(str,sizeof(str),stdin);
  a=atol(strtok(str," "));
  b=atol(strtok(NULL," "));
  k=atol(strtok(NULL," "));
  
  if(a>k){
    printf("%Ld %Ld\n",a-k,b);
  }else if(a+b>k){
    printf("%Ld %Ld\n",0,b-k+a);
  }else{
    printf("%Ld %Ld\n",0,0);
  }
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<limits>
#include<bitset>
#include<functional>
#include<type_traits>
#include<queue>
#include<stack>
#include<array>
#include<random>
#include<utility>
#include<cstdlib>
#include<ctime>
#include <numeric>
#include <stdio.h>
using namespace std;

int main() {
    int n, k;
    int ans;
    cin >> n >> k;
    ans = 1;
    while(true) {
        if(n / k ==0) break;
        n = n / k;
        ans++;
    }
    cout << ans << endl;
    return 0;
    
}

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

int main(){
    int D, G;
    cin >> D >> G;
    vector<int> p(D);
    vector<int> c(D);
    priority_queue<int, vector<int>, greater<int>> q;
    rep(i, D) cin >> p[i] >> c[i];
    rep(i, 1 << D){
        bitset<10> a(i);
        int sum = 0, ans = 0;
        rep(j, D)if(a.test(j)){
            rep(k, p[j]){
                sum += 100*(j+1);
                ans++;
                if(sum >= G) break;
            }
            sum += c[j];
            if(sum >= G) q.push(ans);
        }
        if(sum < G){
            for(int j = D-1; j >= 0; j--) if(!a.test(j)){
                rep(k, p[j]){
                    sum += 100*(j+1);
                    ans++;
                    if(sum >= G) break;
                }
                break;
            }
            if(sum >= G) q.push(ans);
        }
    }
    cout << q.top() << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int64_t n;
  cin >> n;
  vector<int64_t> a(n),b(0);
  rep(i,n){
    cin >> a.at(i);
  }
  if(n%2==0){
    for(int i=n-1;i>0;i-=2){
      b.push_back(a.at(i));
    }
    for(int i=0;i<n-1;i+=2){
      b.push_back(a.at(i));
    }
  }else{
    for(int i=n-1;i>=0;i-=2){
      b.push_back(a.at(i));
    }
    for(int i=1;i<n-1;i+=2){
      b.push_back(a.at(i));
    }
  }
  rep(i,n){
    cout << b.at(i) << " ";
  }
}

Measured memory_bytes: 5488
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define INF 9223372036854775807
#define MOD 1000000007
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<ll, ll> pll;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0;
string s;
bool flag;
#pragma endregion
#define MAX 111111

ll a[MAX], b[MAX];

ll mpow(ll x, ll y) {
  ll ret = 1;
  while (y > 0) {
	if (y & 1) ret = (x*ret) % MOD;
	x = (x*x) % MOD;
	y >>= 1;
  }
  return ret;
}

ll comb(ll x, ll y) {
  if (x < y) return 0;
  ll fac1 = b[x], fac2 = b[x - y], fac3 = b[y];
  return ((fac1 *mpow(fac2, MOD - 2)) % MOD *mpow(fac3, MOD - 2)) % MOD;
}

int main(void) {
  ll le = -1,ri = 0;
  map < ll, ll > mp;
  cin >> n;
  FOR(i, 0, n + 1) {
	cin >> a[i];
	if (mp[a[i]] == 1) tmp = a[i];
	mp[a[i]]++;
  }

  FOR(i, 0, n+1) {
	if (a[i] == tmp) {
	  if (le == -1) {
		le = i;
	  }
	  else {
		ri = i;
	  }
	}
  }

  ri = n - ri;
  cnt = max(ri, 0LL) + max(le, 0LL);

  b[0] = 1;
  FOR(i, 1, 100005) {
	b[i] = (b[i - 1] * i) % MOD;
  }

  FOR(i, 1, n + 2) {
	ans = (comb(n + 1, i) - comb(cnt, i - 1)) % MOD;
	if (ans < 0) ans += MOD;
	cout << ans << endl;
  }
  return 0;
}

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

#define int long long int
#define vi vector<int>
#define vvi vector<vi>
#define read(a)  for(int i = 0; i < n; i++) cin >> a[i];
#define print(a)  for(int i = 0; i < n; i++) cout << a[i] << " ";
#define pb push_back
#define ins insert
#define pql priority_queue<int>
#define pqs priority_queue<int, vi, greater<int>>
#define pqlv priority_queue<vi>
#define pqsv priority_queue<vi, vvi, greater<vi>>
#define endl '\n'

int n, k, val;
vi a, vis, v;

void dfs(int i) {
    if(vis[i]) {
        val = i;
        return;
    }
    v.pb(i);
    vis[i] = 1;
    dfs(a[i - 1]);
}

signed main() {
    int n, k;
    cin >> n >> k;
    a.resize(n);
    read(a);
    vis.assign(n + 1, 0);
    dfs(1);
    vi x;
    bool has = false;
    for(int i : v) {
        if(i == val)
            has = true;
        if(has)  {
            x.pb(i);
        }
    }
    int diff = v.size() - x.size();
    if(k <= diff) {
        cout << v[k];
    }
    else {
        k -= diff;
        int ans = x[k % x.size()];
        cout << ans;
    }
}


Measured memory_bytes: 16648
#![allow(clippy::needless_range_loop)]
#![allow(unused_macros)]
#![allow(dead_code)]

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        #[allow(unused_mut)]
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
    }
    let mut cnt = vec![0; 10001];
    for x in 1..=100 {
        for y in 1..=100 {
            for z in 1..=100 {
                let ans = x*x + y*y + z*z + x*y + y*z + z*x;
                if ans <= 10000 {
                    cnt[ans] += 1;
                }
            }
        }
    }
    for ans in &cnt[1..=n] {
        println!("{}", ans);
    }
}


Measured memory_bytes: 2116
n = int(input())
s = input()

dict = dict()
for a in s:
  if a in dict:
    dict[a] = dict[a] + 1
  else:
    dict[a] = 1
res = 1
for k in dict:
  res *= (dict[k] + 1)
res -= 1 
res %= (10**9 + 7) 
print(res)


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

using namespace std;

#define debug(x) cout << '>' << #x << ':' << x << endl;
#define loop0(i,n) for(int i=0; i<(n); i++)
#define loop1(i,n) for(int i=1; i<=(n); i++)
#define fori(a,b,i) for(int i=(a); i<=(b); i++)
#define ford(a,b,i) for(int i=(a); i>=(b); i--)
#define fast_io ios_base::sync_with_stdio(false), cin.tie(NULL)
#define ign cin.ignore(numeric_limits<streamsize>::max(),'\n')

#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define endl "\n"
#define fir first
#define sec second
#define pb push_back
#define mp make_pair

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MII;
typedef map<int,int> MCI;
typedef unordered_map<int,int> UMII;
typedef unordered_map<char,int> UMCI;
typedef set<int> SI;
typedef long long int llint;

// Display Map
//~for (auto const& pair: m) {
//~std::cout << "{" << pair.first << ": " << pair.second << "}\n";
//~}

// Extract word(w) from sentence(s)
//~stringstream str(s);
//~string w;
//~while(str >> w){
//~// w is your word
//~}

//Memset Syntax
// memset(array, value,sizeof(array)) val is 0,-1 or bool only

// To get accurate precision
//~cout.precision(20);

int main() {
    fast_io;
	int a,b;
	cin >> a >> b;
	cout << a*b << endl;
}


Measured memory_bytes: 3648
// Problem : A - Circle Pond
// Contest : AtCoder - AtCoder Beginner Contest 163
// URL : https://atcoder.jp/contests/abc163/tasks/abc163_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

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

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	double ans = 2*acos(-1)*n;
	cout << fixed << setprecision(20);
	cout << ans << '\n';
				
	return 0;
}


Measured memory_bytes: 3804
#include <bits/stdc++.h>
using namespace std;
const int MMAX = 500;

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  while(cin >> n >> m){
    if(n == 0 && m == 0){
      break;
    }
    vector<bitset<MMAX>> R(n);
    for(int i = 0; i < n; i++){
      string str; cin >> str;
      R[i] = bitset<MMAX>(str);
    }

    if(n <= 22){
      int ans = 0;
      for(int i = 0; i < (1<<n); i++){
        bitset<MMAX> m(0);
        for(int j = 0; j < n; j++){
          if(i & (1 << j)){
            m = m ^ R[j];
          }
        }
        if(m.none()){
          ans = max(ans, __builtin_popcount(i));
        }
      }
      cout << ans << endl;
    }else{
      vector<int> cur(1 << m, -1);
      vector<int> nxt(1 << m, -1);
      cur[0] = 0;
      for(int j = 0; j < n; j++){
        nxt = vector<int>(cur);
        for(int i = 0; i < (1 << m); i++){
          if(cur[i] == -1) continue;
          nxt[i ^ R[j].to_ulong()] = max(nxt[i ^ R[j].to_ulong()], cur[i] + 1);
          // dp[i ^ R[j].to_ulong()][j+1] = max(dp[i ^ R[j].to_ulong()][j+1], dp[i][j] + 1);
          // dp[i][j+1] = max(dp[i][j+1], dp[i][j]); //
        }
        swap(nxt, cur);
      }
      cout << cur[0] << endl;
    }
  }
}



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

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

Measured memory_bytes: 3596
using System;
using System.Collections.Generic;
using System.Linq;
// using System.Linq;

namespace easy_Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            // float[] ABN = Array.ConvertAll(Console.ReadLine().Split(),float.Parse);
            // int[] nx = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            // long K = long.Parse(Console.ReadLine());
            // int[] abc = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            // string S = Console.ReadLine();
            // int a = int.Parse(Console.ReadLine());
            // int b = int.Parse(Console.ReadLine());
            // int h = int.Parse(Console.ReadLine());
            // float N = float.Parse(Console.ReadLine());
            // string c = Console.ReadLine();
            // string B = Console.ReadLine();
            string[] AopB = Console.ReadLine().Split();
            // var s = (new string[] { Console.ReadLine(), Console.ReadLine(), Console.ReadLine() }).Select(float.Parse);
            // float[] a = Array.ConvertAll(Console.ReadLine().Split(),float.Parse);
            // var X = Console.ReadLine();
            // int[,] abcd = new int[NMQ[2],4];
            // int[] A = new int[NMQ[0]];
            // int[] A_num = new int[NMQ[0]];
            // for(int i = 0; i<A_num.Length;i++){
            //     A_num[i] = 0;
            // }
            int A = int.Parse(AopB[0]);
            int B = int.Parse(AopB[2]);
            Console.WriteLine(AopB[1]=="+"?A+B:A-B);
        }
        //最小公倍数
        static long Lcm(long a, long b)
        {
            return a/Gcd(a,b)*b;
        }

        //最大公約数
        static long Gcd(long m, long n)
        {
            if(n==0)return m;
            return Gcd(n,m%n);
        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
#define int long long
#define endre getchar();getchar();return 0
#define INF 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define input(a,n) for(int i=0;i<n;i++)cin>>a[i];
#define P pair<int,int>
#define prique priority_queue<int,vector<int>,greater<int>>
using namespace std;
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return (y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int n) {
	if (n == 0)return 1;
	return (kai(n - 1)*n) % INF;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int mystoi(string s) {
	int cnt = 0;
	for (int i = 0; i < s.size(); i++) {
		cnt += (int)(s[i] - '0') * pow(10, s.size() - i - 1);
	}
	return cnt;
}

signed main() {
	int n;
	cin >> n;
	for (int i = 11; n; i += 5) {
		if (prime(i))cout << i << " ", n--;
	}
	endre;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>
#include <cstring>

#define rep(i,n) for(int i=0;i<int(n);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back

using namespace std;
using ll = long long;


const ll mod = 1000000007;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
// bool debug=false;

/*---------------------------------------------------*/


struct Edge{
    long long to, cost;
    Edge(long long t, long long c){
        to = t;
        cost = c;
    }
};

class Bellman_Ford{
    private:
        const long long Inf = 1LL << 50;
        vector<long long> dist;
        vector<vector<Edge> > adj;
    public:
  Bellman_Ford(int v, int s){
            dist.resize(v + 1);
            adj.resize(v + 1);
	    for(int i = 0; i < (int)dist.size(); i++) dist[i] = Inf;
	    dist[s] = 0;
        }

        void add_path(int from, int to, long long cost){
            adj[from].push_back(Edge(to, cost));
        }

        bool shortest_path(int s){            
            int cnt = 0;
            bool update = true;
            while(update){
                if(cnt > (int)dist.size() + 1)return false;
                cnt++;
                update = false;
                for(int i = 0; i < (int)dist.size(); i++){
                    for(int  j = 0; j < (int)adj[i].size(); j++){
                        Edge e = adj[i][j];
                        if(dist[e.to] > dist[i] + e.cost && dist[i] != Inf){
                            dist[e.to] = dist[i] + e.cost;
                            update = true;
                        }
                    }
                }
            }
            return true;
        }

        long long get_distance(int x){
            return dist[x];
        }

        void DEBUG(){
            for(int i = 0; i < (int)dist.size(); i++){
                cout << 1 << " --> " << i << " = " << dist[i] << endl;
            }
        }
};

int main() {
  long long N, M, a, b, c;
  cin >> N >> M;
  Bellman_Ford bel = Bellman_Ford(N, 0);
  for(int i = 0; i < M; i++) {
    cin >> a >> b >> c;
    a--; b--;
    bel.add_path(a, b, -c);
  }
  
  bel.shortest_path(0);
  long long first_cost = -bel.get_distance(N - 1);
  bel.shortest_path(0);
  long long second_cost = -bel.get_distance(N - 1);
  if(first_cost == second_cost) {
    cout << -bel.get_distance(N - 1) << endl;
  } else {
    cout << "inf" << endl;
  }
  return 0;
}


Measured memory_bytes: 384
// ------------------------------------
// Date:2018/ 3/ 1
// Problem:ABC 058 ∵∴∵ b.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

typedef long long ll;

static const int MOD = 1000000007;

int main()
{
  string O, E;
  string ans = "";
  cin >> O >> E;
  int o,e;
  o = O.length();
  e = E.length();
  REP(i, e) {
    ans += O[i];
    ans += E[i];
  }
  if (o > e) ans += O[o-1];
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
const int maxn=1e5+10;
char s[maxn];
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	if(s[n]=='1' || s[n-1]=='0' || s[1]=='0') return printf("-1\n"),0;
	bool flag=1;
	REP(i,1,n>>1) flag&=(s[i]==s[n-i]);
	if(flag==0) return printf("-1\n"),0;
	int lst=1,num=1,lstnum=1;
	REP(i,2,n-1) if(s[i]=='1'){
		printf("%d %d\n",lstnum,num+1);
		++num;
		lstnum=num;
		REP(j,1,i-lst-1){
			++num;
			printf("%d %d\n",lstnum,num);
		}
		lst=i;
	}
	if(num<n) printf("%d %d\n",lstnum,num+1);
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define Abs(x)((x) < 0 ? (x) * -1 : (x))
#define rep(x, y) for ((x) = 0; (x) < (y); (x)++)
#define repin(x, y) for ((x) = 0; (x) <= (y); (x)++)
#define nep(x, y) for ((x) = (y) - 1; 0 <= (x); (x)--)
#define nepi(x, y, z) for ((x) = (y) - 1; (z) <= (x); (x)--)
#define repi(x, y, z) for ((x) = (z); (x) < (y); (x)++)
#define repiin(x, y, z) for ((x) = (z); (x) <= (y); (x)++)
#define reps(x, y, z) for ((x) = 0; (x) < (y); (x) += (z))
#define repit(x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define All(x) (x).begin(),(x).end()
#define Mem0(x) memset(x, 0, sizeof(x))
#define Mem1(x) memset(x, -1, sizeof(x))
#define End '\n'
#define Out(x) cout<<(x)<<End
template<typename T> inline bool Max(T &x, const T &y) { return x < y ? x = y, 1 : 0; }
template<typename T> inline bool Min(T &x, const T &y) { return x > y ? x = y, 1 : 0; }
template<typename T> using V = vector<T>;
template<typename T> using VV = V<V<T> >;

#define pb push_back
#define mp make_pair

static const ll MOD = 1e9 + 7;
static const double PI = 3.141592653589793;

#define LOCAL 0

int main()
{
#if LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif

    cin.tie(0);
    ios::sync_with_stdio(false);


    int a, b, x;

    cin >> a >> b >> x;

    if (a <= x && x <= a + b) Out("YES");
    else Out("NO");

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100010
int main()
{
    long long x,y,z;
    scanf("%lld%lld",&x,&y);
    if(x==y)
    {
        printf("-1\n");
        return 0;
    }
    for(long long i=2;i<=100000;i++)
    {
        z=x*i;
        if(z%y)
        {
            printf("%lld\n",z);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

Measured memory_bytes: 128
/*
            _ _  ___            __ _ _  _       _     
 _   _  ___| | |/ _ \__      __/ _| | || |  ___| |__  
| | | |/ _ \ | | | | \ \ /\ / / |_| | || |_/ __| '_ \ 
| |_| |  __/ | | |_| |\ V  V /|  _| |__   _\__ \ | | |
 \__, |\___|_|_|\___/  \_/\_/ |_| |_|  |_| |___/_| |_|
 |___/                 

 */

#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
#define MOD 1000000007
#define INF 1000000000000000007
#define MAXN 300005


signed main(){
	fast
	int n;
	cin>>n;
	int abc[n][3] = {0};
	int dp[n][3] = {0};

	For(i, 0, n){
		For(j, 0, 3){
			cin>>abc[i][j];
		}
	}

	For(j, 0, 3){
		dp[0][j] = abc[0][j];
	}

	For(i, 1, n){
		int m = 0;
		dp[i][0] = max(dp[i-1][1], dp[i-1][2])+ abc[i][0];			
		dp[i][1] = max(dp[i-1][0], dp[i-1][2])+ abc[i][1];			
		dp[i][2] = max(dp[i-1][1], dp[i-1][0])+ abc[i][2];			
	}

	int ans = max(max(dp[n-1][0], dp[n-1][1]), dp[n-1][2]);
	cout<<ans<<endl;
	// For(i, 0, n){
	// 	For(j, 0, 3){
	// 		cout<<dp[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }

    return 0;
}
    



Measured memory_bytes: 4992
#include<iostream>
#include<iomanip>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;


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

	string S, T, U;
	int A, B;
	cin >> S >> T >> A >> B >> U;
	if (S == U) A--;
	else B--;
	cout << A << " " << B << endl;

	return 0;
}

								

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

int N,S,T;

int sdis[303];
int tdis[303];

const int INF=2e9;

int main(){
  cin>>N>>S>>T;
  
  for(int i=1;i<=N;i++){
      if(i==S) continue;
      cout<<"? "<<S<<" "<<i<<endl;
      int x;
      cin>>x;
      sdis[i]=x;
  }
  for(int i=1;i<=N;i++){
      if(i==T) continue;
      if(i==S){
          tdis[S]=sdis[T];
      }else{
          cout<<"? "<<T<<" "<<i<<endl;
          int x;
          cin>>x;
          tdis[i]=x;
      }
  }

  int now=S;
  vector<int> ans;
  ans.push_back(S);
  while(S!=T){
      int nex;
      int mi=INF;
      for(int i=1;i<=N;i++){
          if(sdis[now]<sdis[i]&&tdis[now]>tdis[i]){
              int a=sdis[i]-sdis[now];
              int b=tdis[now]-tdis[i];
              if(a==b){
                  if(mi>a){
                      nex=i;
                      mi=a;
                  }
              }
          }
      }
      ans.push_back(nex);
      if(nex==T) break;
      now=nex;
  }

  cout<<"!";
  for(int i=0;i<ans.size();i++) cout<<" "<<ans[i];
  cout<<endl;

  return 0;
}



Measured memory_bytes: 4652
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST
{
    
    static void Main()
    {


        var s = Console.ReadLine();
        var t = Console.ReadLine();

        int op = 0;

        for(int i=0;i<s.Length;i++)
        {
            if(s[i]!=t[i])
            {
                op++;
            }
        }

        Console.Write(op);
      

    }
   
}


Measured memory_bytes: 18180
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){
    string s ; cin >> s ;
    int i=0,c=0,n=sz(s);
    while (i<n){
        bool f=false;
        while (i<n and s[i]=='W') {
            i++;
            f=true;
        }
        if (f) c++;
        f=false;
        while (i<n and s[i]=='B') {
            i++;
            f=true;
        } 
        if (f) c++; 
    }
    cout << (c-1) << endl;
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}

/*

*/

Measured memory_bytes: 3720
#include <iostream>
#include <cmath>
#include <string.h>

using namespace std;

#define MAX 1000000
int p[MAX];

int main() {
  int n;
  int a[100005];
  int cnt = 0;
  int flag=0;
  int l = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) {
	cin >> a[i];
  }

  while (cnt < n) {
	l = a[l];
	cnt++;
	if (l == 2) {
	  flag = 1;
	  break;
	}
  }

  if (flag)cout << cnt << endl;
  else cout << -1 << endl;
}

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

int main() {
	ll n, y;
	cin >> n >> y;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= n-i; j++) {
			int k = n-i-j;
			if(i*10000+j*5000+k*1000 == y){
				cout << i << " " << j << " " << k << endl;
				return 0;
			}
			
		}
	}
	cout << "-1 -1 -1" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define abs(a) (a>0) ? (a) : (-a) 

int main()
{
    int n,i,max,maxi,ansi,kari=1000000000,a[100000];
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&(a[i]));
        if(!i)max=a[0], maxi=0;
        else if(a[i]>=max)max=a[i], maxi=i;
    }
    for(i=0;i<n;i++)
    {
        if(maxi!=i)
        {
            if(kari>(abs((a[i]*2-max))))
            {
                kari=(abs((a[i]*2-max)));
                ansi=i;
            }
        }
    }
    printf("%d %d",max,a[ansi]);
}

Measured memory_bytes: 512
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
abc = [inpl() for i in range(n)]
dp = [[0] * 3 for i in range(n+5)]
for i in range(3):
    dp[0][i] = abc[0][i]
for i in range(n-1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][j] = max(dp[i+1][j], dp[i][k] + abc[i+1][j])
print(max(dp[n-1]))

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

int main(){
    int N,max_height,ans;
    max_height = 0;
    ans = 0;
    cin >> N;
    rep(i,N){
        int h;
        cin >> h;
        if (h >= max_height){
            max_height = h;
            ans++;
        } 
    }   
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
# define INF 0x3f3f3f3f
#define MOD 1000000007
#define si(x) scanf("%d",&x)
#define sii(x,y) scanf("%d%d",&x,&y)
#define siii(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define pi(x) printf("%d",x)
#define pii(x,y) printf("%d%d",x,y)
#define piii(x,y,z) printf("%d%d%d",x,y,z) 
#define sl(x) scanf("%lld",&x)
#define sll(x,y) scanf("%lld%lld",&x,&y)
#define slll(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define pl(x) printf("%lld",x)
#define pll(x,y) printf("%lld%lld",x,y)
#define plll(x,y,z) printf("%lld%lld%lld",x,y,z) 
 
#define ll long long
#define mp make_pair
#define pb push_back
#define pp pop_back
#define nl printf("\n");
#define sf scanf
#define pf printf
#define rep(i,n) for(ll i=0;i<n;i++)
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define vint vector<int> 
#define tci int t;scanf("%d",&t);while(t--)
#define tcl ll t;sl(t);while(t--) 
int main() 
{
    ll h,w;
    sll(h,w);
    ll n;
    sl(n);
    ll a[n];
    ll res[h][w];
    rep(i,n)
        sl(a[i]);
    ll ptr=a[0],ind=1;
    rep(i,h)
    {
        rep(j,w)
        {
            res[i][j]=ind;
            //cout<<ind<<" ";
            ptr--;
            if(ptr==0)
            {
                ptr=a[ind];
                ind++;
            }
        }
    }
    rep(i,h)
    {
        rep(j,w)
        {
            if(i%2==0)
                cout<<res[i][j]<<" ";
            else
                cout<<res[i][w-j-1]<<" ";
        }
        nl;
        
    }
    return 0;
}   

Measured memory_bytes: 384
main = do
  li <- getLine
  let [a,b,c,k] = map read $ words li
  let ans = compute a b c k
  print ans

compute :: Int -> Int -> Int -> Int -> Int
compute a b c k
  | a >= k = k
  | b >= k1 = a
  | True = a - k2
  where
    k1 = k - a
    k2 = k1 - b

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

#define fi first
#define se second
#define mp make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define repd(i, a, b) for(int i = a; i >= (b); i--)
#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 INF = 1e9+7;
long long INFLL = 1e17;

int N;
string s;

const int maxn = 5e3 + 5;
int DP[maxn][maxn];

int dp(int cmd, int pos) {
    if (cmd == 0) {
        return pos == s.size() ? 1 : 0;
    }
    int &ret = DP[cmd][pos];
    if (ret != -1) return ret;
    ret = dp(cmd - 1, pos + 1);
    if (pos == 0) ret += dp(cmd - 1, pos);
    else ret += dp(cmd - 1, pos - 1) * 2 % INF;
    ret %= INF;
    return ret;
}
int main() {
    cin >> N >> s;
    memset(DP, -1, sizeof DP);
    // puts("gg");
    printf("%d\n", dp(N, 0));
}


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

int main()
{
    int A, B, K, tmp, count=0;
    cin >> A >> B >> K;
    vector<int> aa(A+1);
    vector<int> bb(B+1);
    vector<int> ans(100);

    for (int i = 1; i <= A;i++){
        if(A%(i)==0){
            aa.at(i) = 1;
        }
    }

    for (int i = 1; i <= B; i++)
    {
        if (B % (i) == 0)
        {
            bb.at(i) = 1;
        }
    }

    tmp = min(A, B);
    for (int i = 0; i < tmp+1;i++){
        if(aa.at(i)==1 && bb.at(i)==1){
            count++;
            //cout << i << endl;
            ans.at(count) = i;
            
        }
    }
    //cout << count << endl;
    cout << ans.at(count - K+1) << endl;
}

Measured memory_bytes: 256
#ABC081

n = int(input())
a = list(map(int,input().split()))


c = True
for i in range(n):
        if a[i] % 2 != 0:
            c = False
count = 0
while c:
    
    a = [a[i] // 2 for i in range(len(a))]
    count += 1
    for i in range(n):
        if a[i] % 2 != 0:
            c = False
            break
    
print(count) 

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <utility>
#include <bitset>
using namespace std;
constexpr int maxnum = 15*30;

int rot[4][6] = {{5, 4, 2, 3, 0, 1},
                 {4, 5, 2, 3, 1, 0},
                 {0, 1, 5, 4, 2, 3},
                 {0, 1, 4, 5, 3, 2}};
int dir_x[4] = {-1, 1, 0, 0};
int dir_y[4] = {0, 0, -1, 1};
vector<int> rotate(vector<int> a, int dir){
    vector<int> res(6);
    for(int i=0; i<6; i++){
        res[i] = a[rot[dir][i]];
    }
    return res;
}
vector<int> dir_to_idx(string &s){
    vector<int> res;
    for(char c: s){
        if(c == 'L') res.push_back(0);
        else if(c == 'R') res.push_back(1);
        else if(c == 'F') res.push_back(2);
        else if(c == 'B') res.push_back(3);
    }
    return res;
}

int main(){
    while(1){
        int n;
        cin >> n;
        if(n == 0) break;

        vector<map<pair<int,int>, int>> boards(n);
        for(int i=0; i<n; i++){
            int x,y;
            cin >> x >> y;
            vector<int> p(6);
            for(int i=0; i<6; i++){
                cin >> p[i];
            }
            string s;
            cin >> s;
            vector<int> dirs = dir_to_idx(s);
            boards[i][{x,y}] = p[4];
            for(int j: dirs){
                p = rotate(p, j);
                x += dir_x[j];
                y += dir_y[j];
                boards[i][{x,y}] = p[4];
            }
        }

        map<pair<int,int>, int> idx_cmp;
        for(auto &b: boards){
            for(auto &p: b){
                idx_cmp[p.first] = 0;
            }
        }
        int count = 0;
        for(auto &p: idx_cmp){
            p.second = count++;
        }
        
        vector<int> dp(1<<n, 0);
        vector<bitset<maxnum>> used(1<<n);
        for(int i=0; i<(1<<n); i++){
            for(int j=0; j<n; j++){
                if(i>>j&1) continue;
                int k = i | (1<<j);
                bitset<maxnum> used_curr;
                int add_points = 0;
                for(auto &p: boards[j]){
                    int pos = idx_cmp[p.first];
                    used_curr[pos] = 1;
                    if(used[i][pos] == 0){
                        add_points += p.second;
                    }
                }
                dp[k] = max(dp[k], dp[i]+add_points);
                used[k] |= used_curr;
            }
        }
        cout << dp[(1<<n)-1] << endl;
    }
    return 0;
}



Measured memory_bytes: 5436
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll          long long
#define pb          push_back
#define mp 	    make_pair
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pii>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define all(a)      (a).begin(),(a).end()
#define fi          first
#define si          second
#define sz(x)       (ll)x.size()
#define endl        '\n'
#define mod        1000000007
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
ll power(ll a , ll b,ll modi)
{
    a%=modi;
    ll res = 1 ;
    while(b)
    {
        if(b%2) {
            res = (res * a) % modi ;
        }
        b/=2 ;
        a = (a*a) % modi ;
    }
    return res ;
}
ll dp[1000][1000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
	//cin>>t;
	while(t--)
	{
	ll n,m;
	cin>>n>>m;
	string s[n];
	for(int i=0;i<n;i++)
	cin>>s[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(s[i][j]=='#')
			continue;
			if(i==0 && j==0)
			dp[i][j]=1;
			if(i-1>=0)
			dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
			if(j-1>=0)
			dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
		}
	}
	// for(int i=0;i<n;i++){
		// for(int j=0;j<m;j++)
		// cout<<dp[i][j]<<" ";
		// cout<<endl;
	// }
	cout<<dp[n-1][m-1];
	}
return 0;
}

Measured memory_bytes: 12504
# dp[n][i][j]=(頂点iから頂点jへ行く長さnのパスの個数)
# dp[n][i][j]=sum(dp[n-1][i][k]*a[k][j])⇒DP[n]=DP[n-1]*A DP[0]=Eより DP[n]=A^n
import sys
input = sys.stdin.readline

def dot(A,B,MOD=1000000007):
    N,M,L = len(A),len(A[0]),len(B[0])
    res = [[0]*L for i in range(N)]
    for i in range(N):
        for j in range(L):
            s = 0
            for k in range(M):
                s = (s + A[i][k]*B[k][j]) % MOD
            res[i][j] = s
    return res

def matPow(A,x,MOD=1000000007):
    N = len(A)
    res = [[0]*N for i in range(N)]
    for i in range(N):
        res[i][i] = 1
    for i in range(x.bit_length()):
        if (x>>i) & 1:
            res = dot(res,A)
        A = dot(A,A)
    return res

def main():
    n,k = map(int,input().split())
    mod = 10**9+7
    a = [list(map(int,input().split())) for i in range(n)]
    dp = matPow(a,k)
    ans = 0
    for i in range(n):
        for j in range(n):
            ans += dp[i][j]
    print(ans%mod)

main()

Measured memory_bytes: 41904
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<int,int> pi;
typedef stringstream sst;
typedef vector<int> vi;

char c[9][9];

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	rep(i,8)cin>>c[i];
	char me='o',ene='x';
	int pass=0;
	while(1){
		/*rep(i,8)cout<<c[i]<<endl;
		cout<<endl;*/
		int Y=-1,X=-1,best=0;
		rep(i,8)rep(j,8)if(c[i][j]=='.'){
			int flip=0;
			rep2(dy,-1,2)rep2(dx,-1,2)if(dy||dx){
				int y=i,x=j,f=0;
				while(1){
					y+=dy,x+=dx;
					if(y<0 || 7<y || x<0 || 7<x)break;
					if(c[y][x]!=ene){
						if(c[y][x]==me)flip+=f;
						break;
					}
					f++;
				}
			}
			if(me=='o'){
				if(flip>best)best=flip,Y=i,X=j;
			}else{
				if(flip>=best)best=flip,Y=i,X=j;
			}
		}
		if(best==0){
			pass++;
			if(pass==2)break;
			swap(me,ene);
			continue;
		}
		c[Y][X]=me;
		rep2(dy,-1,2)rep2(dx,-1,2)if(dy||dx){
			int y=Y,x=X,ok=0;
			while(1){
				y+=dy,x+=dx;
				if(y<0 || 7<y || x<0 || 7<x)break;
				if(c[y][x]!=ene){
					if(c[y][x]==me)ok=1;
					break;
				}
			}
			if(ok){
				y=Y,x=X;
				while(1){
					y+=dy,x+=dx;
					if(y<0 || 7<y || x<0 || 7<x)break;
					if(c[y][x]!=ene)break;
					c[y][x]=me;
				}
			}
		}
		pass=0;
		swap(me,ene);
	}
	rep(i,8)cout<<c[i]<<endl;
}

Measured memory_bytes: 1172
N, M, *A = map(int, open(0).read().split())

# 増える幸福度が，定数X以上になる握手の方法の通り数
def func(X):
    cnt = 0
    j = N
    for i in range(1, N + 1):
        while A[i] + A[j] < X:
            j -= 1
        cnt += j
    return cnt

A = [10 ** 11] + sorted(A, reverse=True)

lb = 0
ub = 10 ** 11
while ub - lb > 1:
    mid = (lb + ub) // 2
    if func(mid)>= M:
        lb = mid
    else:
        ub = mid

acc = A[:]
acc[0] = 0
for i in range(N):
    acc[i + 1] += acc[i]

ans = 0
j = N
for i in range(1, N + 1):
    while A[i] + A[j] < lb + 1:
        j -= 1
    ans += A[i] * j + acc[j]
    M -= j
    
if M:
    ans += lb * M
    
print(ans)




Measured memory_bytes: 64196
#include <iostream>
#include <cstdio>
#include <vector>
#include <math.h>
#include <string>
#include <iomanip>
#include <algorithm>
#include <map>
//#include <unordered_map>
//#include <bits/stdc++.h>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;

vector <int> kmp (string s)
{
    int n=s.length();
    vector <int> ret(n,-1);
    int k=-1;
    for(int i=1; i<n; i++)
    {
        //cout<<"start "<<k<<" "<<s[i]<<" "<<s[k+1]<<endl;
        for( ; s[i]!=s[k+1] && k>=0; k=ret[k])
        {
            //cout<<k<<" "<<s[i]<<" "<<s[k+1]<<"\n";
        }
        if(s[i]==s[k+1])
        {
            k++;
        }
        ret[i]=k;
    }
return ret;    
}
template <class D> long long bin(vector <D> ar,long long start,long long end,D val)
{
    long long l=start,r=end;
    while(l<=r)
    {
        long long mid=l+(r-l)/2;
        if(ar[mid]>val)
        {
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
return l-1;
}

bool found(string s1,string s2)
{
    long long  n1=s1.length();
    long long n2=s2.length();
    vector <int> pat=kmp(s2);
    //for(int i=0; i<pat.size(); i++)
        //cout<<pat[i]<<" ";
    //cout<<endl;    
    int j=-1;
    for(int i=0; i<n1; i++)
    {
        //cout<<j<<" "<<s1[i]<<"\t"<<s2[j+1]<<endl; 
        for( ; s1[i]!=s2[j+1] && j>=0; j=pat[j]){}
        if(s1[i]==s2[j+1])
            j++;
        if(j==n2-1)
        {
            return true;
        }    
    }
return false;
}
 
int main()
{
  	ios_base::sync_with_stdio(false);
  	cin.tie(NULL);
  	long long n,m,k;
  	cin>>n>>m>>k;
  	vector <long long> a(n);
  	vector <long long> b(m);
    vector <long long> A(n+1);
    vector <long long> B(m+1);
    A[0]=B[0]=0;
  	for(long long i=0; i<n; i++)
    {  
        cin>>a[i];
        A[i+1]=a[i]+A[i];
    }    
  	for(long long i=0; i<m; i++)
    {
        cin>>b[i];
        B[i+1]=b[i]+B[i];
    }    
  	long long c1=0,c2=0;
    long long j=m;
    long long ans=0;
  	// for( long long i=m; i>=0; i--)
    // {
    //     long long t=B[i];
    //     if(t>k)
    //         continue;
    //     long long idx=bin(A,0,n,k-t);
    //     c1=max(c1,idx+i);
    //     if(t+A[idx]<=k)
    //         break;  
    // }
    for( long long i=0; i<n+1; i++)
    {
        // long long t=A[i];
        // if(t>k)
        //     continue;
        // long long idx=bin(B,0,m,k-t);
        // c2=max(c2,idx+i);
        // if(t+B[idx]<=k)
        //     break;  
        if(A[i]>k)
            break;
        while(B[j]> k - A[i])
            j--;
        
        ans=max(ans,i+j);
    }
    // long long res=max(c1,c2);
  	// cout<<res<<endl;
    cout<<ans<<endl;
return 0;
}  
  


Measured memory_bytes: 9524
#include <iostream>
#define N 4
using namespace std;
int Ret(int);
int main(){
  int n,i,j,k,l,c[N],cal,cnt,min,min10,min50,min100,min500,flag=0;
  while(1){
    min=100;
    min10=min50=min100=min500=0;
    cin >> n;
    if(n==0) break;
    if(flag!=0) cout << endl;
    for(i=0;i<N;i++) cin >> c[i];
    for(i=0;i<=c[0];i++){
      for(j=0;j<=c[1];j++){
	for(k=0;k<=c[2];k++){
	  for(l=0;l<=c[3];l++){
	    cal=i*10+j*50+k*100+l*500;
	    if(cal>=n){
	      cnt=c[0]-i+c[1]-j+c[2]-k+c[3]-l;
	      cnt+=Ret(cal-n);
	      if(cnt<min){
		min=cnt;
		min10=i;
		min50=j;
		min100=k;
		min500=l;
	      }
	    }
	  }
	}
      }
    }
    if(min10!=0) cout << 10 << ' ' << min10 << endl;
    if(min50!=0) cout << 50 << ' ' << min50 << endl;
    if(min100!=0) cout << 100 << ' ' << min100 << endl;
    if(min500!=0) cout << 500 << ' ' << min500 << endl;
    flag=1;
  }
  return 0;
}
int Ret(int n){
  int retcnt,n10,n50,n100,n500;
  n500=n/500;
  n%=500;
  n100=n/100;
  n%=100;
  n50=n/50;
  n%=50;
  n10=n/10;
  retcnt=n10+n50+n100+n500;
  return retcnt;
}

Measured memory_bytes: 1160
N = int(input())
a = list(map(int,input().split()))
ans = 0
now = a[0]
i = 1
while i < N:
    if now == a[i]:
        ans += 1
        if i == N-1:
            break
        now = a[i+1]
        i += 2
        
    else:
        now = a[i]
        i += 1
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;

signed main(){IOS;
	string s; cin>>s;
	cout<<string(s.size(),'x')<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <cmath>
#include <map>
#include <tuple>
#include <queue>
#include <stack>
#include <iomanip>

#define MOD (1000000007)
using namespace std;

typedef long long ll;

int main() {

    int N;
    cin >> N;

    int d = N % 10;

    if(d == 2 || d == 4 || d == 5 || d == 7 || d == 9) cout << "hon" << endl;
    else if (d == 0|| d == 1 || d == 6 || d == 8) cout << "pon" << endl;
    else if (d == 3) cout << "bon" << endl;


    return 0;
}


Measured memory_bytes: 3604