akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

#define Mod 1000000007

using namespace std;
///                     start, num
vector < vector < pair < int, int > > > A;

int n, m, dp[301][301][301];

long long rec(int r, int g, int b)
{
    int idx = max(max(r, g), b) + 1;

    if(idx > 1)
    {
        for(int i = 0;i < A[idx - 1].size();++i)
        {
            int c = 0;
            int st = A[idx - 1][i].first;
            int num = A[idx - 1][i].second;

            if(r >= st)     ++c;
            if(g >= st)     ++c;
            if(b >= st)     ++c;

            if(c != num)        return 0;
        }
    }

    if(idx == n + 1)    return 1;

    int &ret = dp[r][g][b];
    if(ret != -1)       return ret;

    ret = rec(idx, g, b) + rec(r, idx, b);
    while(ret >= Mod)
        ret -= Mod;
    ret += rec(r, g, idx);
    while(ret >= Mod)
        ret -= Mod;

    return ret;
}

int main()
{
    scanf("%d%d", &n, &m);
    A.resize(n + 5);
    for(int i = 0;i < m;++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        A[b].push_back({a, c});
    }
    memset(dp, 0xff, sizeof(dp));
    printf("%d", rec(0, 0, 0));
    return 0;
}


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

#ifndef __TOPCYBERFLOWER
#define debug(...) 0
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
    while(*sdbg != ',') cout << *sdbg++;
    cout << '=' << (h) << ','; 
    _dbg(sdbg+1, a...);
}
#endif

#define TYPEMAX(type)   numeric_limits<type>::max()
#define TYPEMIN(type)   numeric_limits<type>::min()
typedef long long ll;
typedef pair<int,int> pii;
vector<int> arr;
bool myf(int n){
    for(int i=0;i<n;i++){
        if(arr[i]%2==1) continue;
        if(arr[i]%10!=0 && arr[i]%6!=0) return false;
    }
    return true;
}
int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin>>n;
    arr.resize(n,0);
    for(int i=0;i<n;i++) cin>>arr[i];
    if(myf(n)) cout<<"APPROVED";
    else cout<<"DENIED";
    return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

int main2() {
  int a[3];
  REP(i, 3) a[i] = nextInt();
  sort(a, a+3);
  int ans = a[0] + a[1] + 10*a[2];
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#include <climits>
#define rep(i,n) for (int i=0;i<(n);i++)

using namespace std;

vector<int> g[200005];

int main() {
	int a;
    string s;
	cin >> a >> s;
  
	if(a>=3200){
       cout << s << endl;
    }
    else{
       cout << "red" << endl;
    }
	return 0;
}


Measured memory_bytes: 8284
#include <stdio.h>
#include <math.h>
int kaijyou(int x){
  int sum=1;
  for(int i=1;i<=x;i++){
    sum=sum*(i);
  }
  return sum;
}
int main(){
  int n;
  scanf("%d",&n);
  int p[n],q[n],count[n-1],a=1,b=1,kai;
  /*一回目*/
  for(int i=0;i<n;i++){
    scanf("%d",&p[i]);
    count[i]=1;
  }
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      if(p[i]>p[j])
        count[i]++;
    }
  }
  for(int i=0;i<n-1;i++){
    a=a+kaijyou(i+1)*(count[n-2-i]-1);
  }
  
  /*二回目*/
  for(int i=0;i<n;i++){
    scanf("%d",&q[i]);
    count[i]=1;
  }
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      if(q[i]>q[j])
        count[i]++;
    }
  }
  for(int i=0;i<n-1;i++){
    b=b+kaijyou(i+1)*(count[n-2-i]-1);
  }
  
  printf("%d",abs(a-b));
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;



const int M = 4e5+1;
const int MD=1e9+7;
int n,m,mat[102][102],dp[102][102];
int fun(int x,int y){
	int ans=123456;
	if(x>=n || y>=m){
		return ans;
	}
	if(dp[x][y]!=-1) return dp[x][y];
	if(x==n-1 && y==m-1){
		return 0;
	}
	if(mat[x][y]-mat[x+1][y]==1){
		ans=min(ans,1+fun(x+1,y));
	}
	else{
		ans=min(ans,fun(x+1,y));
	}
	if(mat[x][y]-mat[x][y+1]==1){
		ans=min(ans,1+fun(x,y+1));
	}
	else{
		ans=min(ans,fun(x,y+1));
	}
	return dp[x][y]=ans;
}
int main() {
	fast_cin();
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char ch;
			cin>>ch;
			if(ch=='#'){
				mat[i][j]=1;
			}
			else{
				mat[i][j]=0;
			}
		}
	}
	memset(dp,-1,sizeof(dp));
	cout<<fun(0,0)+mat[n-1][m-1];
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

typedef long long ll;

#define f first
#define s second

int b[200002], n = 200000, x;

void ciur () {
  for (int i = 4; i <= n; i += 2)
    b[i] = 1;
  for (int i = 3; i * i <= n; i += 2)
    if (b[i] == 0)
      for (int j = i * i; j <= n; j += 2 * i)
        b[j] = 1;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  ciur();
  cin >> x;
  while (b[x])
    x++;
  cout << x;
  return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		double x1 = sc.nextDouble();
		double y1 = sc.nextDouble();
		double x2 = sc.nextDouble();
		double y2 = sc.nextDouble();
		
		double a =  x1-x2;
		double b =  y1-y2;
		System.out.printf("%f", Math.sqrt(a*a + b*b));
	}
}


Measured memory_bytes: 28132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define srep(i,l,n) for(int i = l; i < (int)(n); i++)
#define drep(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void err() {cout << -1 << endl;}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back

const int MOD = 1000000007;
const int INF = 1e9;

#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    int n;
    cin >> n;
    map<int, int> mp;
    vector<int> col(n);
    rep(i, n) {
        cin >> col[i];
        mp[col[i]]++;
    }
    if(mp.size() >= 3) {
        No();
    }
    else if(mp.size() == 1) {
        if(col[0] == n-1) Yes();
        else if(col[0] <= n/2) Yes();
        else No();
    } else {
        sort(all(col));
        if(col[n-1] - col[0] != 1) {
            No();
            return 0;
        }
        int large = count(col.begin(), col.end(), col[n-1]);
        if(col[n-1] > (n - large) && large >= 2 * (col[n-1] - (n - large))) Yes();
        else No();
    }
}

Measured memory_bytes: 5376
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long u64;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  int from[2*m], to[2*m], c[2*m];
  bool visited[2*m];
  for (int i = 0; i < m; ++i) {
    int a, b, d;
    cin >> a >> b >> d;
    from[2*i] = a-1; to[2*i] = b-1; c[2*i] = d;
    from[2*i+1] = b-1; to[2*i+1] = a-1; c[2*i+1] = d;
    visited[2*i] = false; visited[2*i+1] = false;
  }
  for (int i = 0; i < n; ++i) {
    int cost[n];
    int n_visited = 1;
    for (int j = 0; j < n; ++j) {
      cost[j] = -1;
    }
    cost[i] = 0;
    while (n_visited < n) {
      vector< int > path;
      vector< int > bnode;
      int best = 100001;
      for (int j = 0; j < 2*m; ++j) {
        if (cost[from[j]] >= 0 && cost[to[j]] < 0) {
          if (best > cost[from[j]] + c[j]) {
            best = cost[from[j]] + c[j];
            path.clear();
            path.push_back(j);
            bnode.clear();
            bnode.push_back(to[j]);
          } else if (best == cost[from[j]] + c[j]) {
            path.push_back(j);
            bnode.push_back(to[j]);
          }
        }
      }
      for (int j = 0; j < path.size(); ++j) {
        if (cost[bnode[j]] == -1) {
          cost[bnode[j]] = best;
          n_visited++;
        }
        visited[path[j]] = true;
      }
    }
  }
  int cnt = 0;
  for (int i = 0; i < m; ++i) {
    if (!visited[2*i] && !visited[2*i+1]) {
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		ArrayList<String> list = new ArrayList<String>();
		int y=0;
		while (scanner.hasNextLine()) {
			String sc = scanner.nextLine();
			y++;
			if(y>=2){
			list.add(sc);
			}
		}
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size();) {
                if (list.get(i).equals(list.get(j))){
                    System.out.print("No");
	    	        System.exit(0);
                } else {
                    ++j;
                }
            }
        }
	    char last;
	    char first;
	    String[] list3 = list.toArray(new String[list.size()]);
		for(int k=1;k<list.size();k++){
	    	first = list3[k].charAt(0);
	    	last = list3[k-1].charAt(list3[k-1].length()-1);
	    	if(last!=first){
	    		System.out.print("No");
	    		System.exit(0);
	    	}
		}
        System.out.print("Yes");
	}
}
	    

Measured memory_bytes: 21716
//2018年  3月 22日 木曜日 17:00:05 JST
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;

void solve() {
	cin >> N;
	int ren = 0, ans = 0;
	rep(i, 0, N) {
		int a;
		cin >> a; a--;
		if(a == i) {
			ren++;
		}
		else {
			ans += (ren + 1) / 2;
			ren = 0;
		}
	}
	ans += (ren + 1) / 2;
	cout << ans << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



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

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

	int max = h[0];
	int cnt = 1;
	for (int i = 1; i < n; i++) {
		if (max <= h[i]) {
			max = h[i];
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;

public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

    ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,d,a;
    cin >> n >> d >> a;
    vector<pair<ll,ll> > xh(n);
    vll x(n);
    REP(i,n){
        ll h;
        cin >> x[i] >> h;
        xh[i] = make_pair(x[i],h);
    }
    sort(ALL(xh));
    sort(ALL(x));
    LazySegmentTree seg( vector<ll>(n, 0) );
    ll ans = 0;
    REP(i,n){
        auto now = xh[i];
        ll nh = seg.getsum(i,i+1);
        if(nh<now.se){
            ll need = ((now.se-1)/a)+1LL;
            need*=a;
            ans += (need-nh)/a;
            ll next = now.fi+d*2LL;
            ll ok = i-1;
            ll ng = n;
            while(abs(ok-ng)>1){
                ll mid = (ok+ng)/2;
                if(x[mid]<=next){
                    ok = mid;
                }else{
                    ng = mid;
                }
            }
            seg.add(i,ok+1,(need-nh));
        }
    }
    cout << ans << endl;
    return 0;
}

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

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

	int ans = 0;
	for( int i = 0; i < N - 2; i++ ) {
		if( S.substr( i, 3 ) == "ABC" ) ans++;
	}

	cout << ans << endl;
}


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

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<long long int,long long int> pll;
typedef vector<int> vi;
typedef vector<long long int> vl;
#define pb push_back
#define mp make_pair

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	
	int n;
	cin >> n;
	multiset<ll> st;

	vl v;
	for(int i=0;i<n;i++){
		ll a;
		cin >> a;
		v.pb(a);
		st.insert(a);
	}

	sort(v.rbegin(),v.rend());
	
	ll ans = 0;
	for(int i=0;i<n;i++){
		ll a = v[i];
		if(st.find(a)==st.end()) continue;
		auto it = st.find(a);
		st.erase(it);
		ll b = 0;
		ll c = 0;
		
	//	if(a%2==1) c=1;
		while(a%2==0) a/=2, c++;
		b = (1<<c);
		a/=2;
		c++;

		for(;c<=32 && a>0;c++, a/=2)
			if(a%2==0) b |= (1<<c);
		
//		cout << b << " " << st.size()<< endl;

		if(st.find(b)!=st.end()) ans++, it = st.find(b), st.erase(it);
		else st.insert(v[i]);
	}
	
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 11248
#include<bits/stdc++.h>
    using namespace std;
    int main(){
      	string s;
      	cin>>s;
      	long long ans=0;
      	for(int i=0;i<s.size()/2;i++){
        	if(s[i] != s[s.size()-i-1])
              ans++;
        }
      	cout<<ans;
    }

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

using namespace std;

int dp[10005];

int main() {
    int h, n;
    scanf("%d%d", &h, &n);

    memset(dp, -1, sizeof(dp));
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);

        for (int j = 0; j < h; j++) {
            if (dp[j] == -1) continue;
            if (dp[min(h, j + x)] == -1 || dp[min(h, j + x)] > dp[j] + y) dp[min(h, j + x)] = dp[j] + y;
        }
    }

    printf("%d\n", dp[h]);
}


Measured memory_bytes: 3872
class Problem
  attr_accessor :a, :b, :c, :k, :n, :m, :h, :w, :s, :x, :y
  def initialize
    @n = gets.to_s.to_i
    @s = gets.chomp
    @left = Array.new(n,0)
    @right = Array.new(n,0)
  end

  # WEST <- -> EAST
  def solve
    left
    right
    @left.zip(@right).map{|a,b|a+b}.min
  end

  def left
    1.upto(n-1) do |i|
      if s[i-1] == "W"
        @left[i] = @left[i-1] + 1
      else
        @left[i] = @left[i-1]
      end
    end
  end

  def right
    (n-2).downto(0) do |i|
      if s[i+1] == "E"
        @right[i] = @right[i+1] + 1
      else
        @right[i] = @right[i+1]
      end
    end
  end

  def show(ans)
    puts ans
  end
end

Problem.new.instance_eval do
  show(solve)
end

Measured memory_bytes: 36552
import java.util.*;

public class Main {
    public static void main(final String[] args) {
        final Scanner sc = new Scanner(System.in);
        // 整数の入力
        // final int a = sc.nextInt();
        // 文字列の入力
        // final String s1 = sc.next();
        final int parN = Integer.parseInt(sc.next());
        int result = 0;
        int cur = 0;

        for (int i = 1; i <= parN; i++) {
            cur = Integer.parseInt(sc.next());
            if ((cur * i) % 2 == 1) {
                result++;
            }
        }

        sc.close();

        System.out.println(result);
    }
}

Measured memory_bytes: 35548
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>

#define int long long

using namespace std;

class Solver {
};
signed main() {
	while (true) {
		int w, h;
		cin >> w >> h;
		if (w == 0)break;

		tuple<int, int> start;
		vector<vector<bool>> grid(h, vector<bool>(w, true));
		map<tuple<int,int>,int> points;
		int cnt = 0;

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				char c;
				cin >> c;
				if (c == '.')continue;
				if (c == 'x') {
					grid[i][j] = false;
					continue;
				}
				if (c == 'o')start = make_tuple(i, j);
				if (c == '*') {
					cnt++;
					points.emplace(make_tuple(i, j), points.size() + 1);
				}
			}
		}
		points.emplace(start, 0);

		vector<map<int, int>> graph(points.size());
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (points.find(make_tuple(i, j)) == points.end())continue;

				int st_i = points[make_tuple(i, j)];

				vector<vector<int>> dist(h, vector<int>(w, 1e9));
				queue<tuple<int, int, int>> que;
				que.push(make_tuple(i, j, 0));
				while (que.size() > 0) {
					int y = get<0>(que.front());
					int x = get<1>(que.front());
					int d = get<2>(que.front());
					que.pop();
					if (dist[y][x] <= d)continue;

					dist[y][x] = d;
					if (points.find(make_tuple(y,x))!=points.end()
						&& (i != y || j != x)) {
						int index = points[make_tuple(y, x)];
						graph[st_i].emplace(index, d);
					}

					if (y > 0 && grid[y - 1][x]) {
						que.emplace(make_tuple(y - 1, x, d + 1));
					}
					if (y + 1 < h && grid[y + 1][x]) {
						que.emplace(make_tuple(y + 1, x, d + 1));
					}
					if (x > 0 && grid[y][x - 1]) {
						que.emplace(make_tuple(y, x - 1, d + 1));
					}
					if (x + 1 < w && grid[y][x + 1]) {
						que.emplace(make_tuple(y, x + 1, d + 1));
					}
				}
			}
		}

		int length = graph[0].size();
		if (length != cnt) {
			cout << -1<<endl;
			continue;
		}

		vector<int> pats;
		for (int i = 1; i < points.size(); i++)pats.emplace_back(i);

		int res =1e9;
		do {
			int tmp = 0;
			int prev = 0;
			for (int i = 0; i < pats.size(); i++) {
				tmp += graph[prev][pats[i]];
				prev = pats[i];
			}
			res = min(res, tmp);
		} while (next_permutation(pats.begin(), pats.end()));

		cout << res << endl;
	}
}


Measured memory_bytes: 3184
#include <stdio.h>
#include <stdlib.h>

int A[100000];

int Cmp(const void *a, const void *b){
  return *(int *)a - *(int *)b;
}

void Do(int N){
  int i, j, c;
  for(i = 0;i < N;i++) scanf("%d", &A[i]);
  qsort(A, N, sizeof(int), Cmp);
  for(i = A[1];i >= 1;i--){
    c = 0;
    for(j = 0;j < N;j++){
      if(A[j] % i != 0) c++;
      if(c == 2) break;
    }
    if(j == N) break;
  }
  printf("%d\n", i);
}

int main(void){
  int N;
  scanf("%d", &N);
  Do(N);
  return 0;
}


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

typedef long long ll;
using namespace std;

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

	while(true){
		int a; cin >> a;
		if(a == 0) break;
		a = 1000 - a;

		int ans = 0;
		ans += a/500;
		a %= 500;
		ans += a/100;
		a %= 100;
		ans += a/50;
		a %= 50;
		ans += a/10;
		a %= 10;
		ans += a/5;
		a %= 5;
		ans += a;

		cout << ans << endl;
	}

	return 0;

}



Measured memory_bytes: 3144
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
int n, m, a[200005], b, c;
int main(){
	scanf("%d%d", &n, &m);
	rep(i,m){
		scanf("%d%d", &b, &c);
		if((b==1 && a[c]++) || (c==n && a[b]++)) return 0*puts("POSSIBLE");
	}
	puts("IMPOSSIBLE");
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define M1 1000000007
#define M2 998244353

#define fl(i,a,b)  for(ll i=a;i<b;i++)
#define bfl(i,a,b) for(ll i=b-1;i>=a;i--)
#define f(i,n)     for(int i=0;i<n;i++)
#define bf(i,n)    for(int i=n-1;i>=0;i--)
#define f1(i,n)    for(int i=1;i<=n;i++)
#define bf1(i,n)   for(int i=n;i>=1;i--)

#define all(v) v.begin(),v.end()
#define pll pair<long,long>
#define pii pair<int,int>



#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl

#define bn "\n"

//------------------------------------------------------------------------ 
// #define V(a) vector<a>
// #define vt() vector< tuple < int ,int ,int > > ;
// #define vector< int ,int > pv;
// vector< pair <int,int> > vect;


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

ll modI(ll a,ll m);
ll gcd(ll a,ll b);
ll powM(ll x,ll y,ll m);
ll swap(ll a,ll b);

void swap(ll& a,ll& b)
{
    ll tp=a;
    a=b;
    b=tp;
}

ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}

ll powM(ll x,ll y,ll m)
{
    ll ans=1,r=1;
    x%=m;
    while(r>0&&r<=y)
    {
        if(r&y)
        {
            ans*=x;
            ans%=m;
        }
        r<<=1;
        x*=x;
        x%=m;
    }
    return ans;
}
 
ll modI(ll a, ll m)
{
    ll m0=m,y=0,x=1;
    if(m==1) return 0;
    while(a>1)
    {
        ll q=a/m;
        ll t=m;
        m=a%m;
        a=t;
        t=y;
        y=x-q*y;
        x=t;
    }
    if(x<0) x+=m0;
    return x;
}

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

// variable = Expression1 ? Expression2 : Expression3
// max = (n1 > n2) ? n1 : n2; 
// (n>m) ? cout<<"True"<<endl:cout<<"false"<<endl ;

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

// int n;cin>>n;int a[n];for(int i=0;i<n;i++)cin>>a[i];    
// for(int i=0;i<n;i++)cout<<a[i];
// int a,b;cin>>a>>b;   

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

// vector< tuple < int ,int ,int > > tv;
// vector< int ,int > pv;


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

const int N=2e5+7;
int a[N];
int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
	int tt=1;
   // cin>>tt;
	while(tt--)
	{
	    int n,k;
	    cin>>n>>k;
	    
	    f(i,n)cin>>a[i];
	    f(i,n-k)
	    {
	        if(a[i]<a[i+k])
	        cout<<"Yes"<<bn;
	        else
	        cout<<"No"<<bn;
	    }
	   
	   
	   
	    
	}
	
	return 0;
}


Measured memory_bytes: 4344
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#include <numeric>
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
const double EPS = 1e-10;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)


//ntt
ll mod = 998244353;
ll root = 3;
ll wlist[30];

ll modpow(ll a, ll n) {
	ll res = 1;
	a %= mod;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

vector<ll>dft(vector<ll>A,int N){
	//bit reverse
	int h = 0;
	for (int i = 0; (1 << i) < N; i++)h++;
	for (int i = 0; i < N; i++) {
		int j = 0;
		for (int k = 0; k < h; k++) j |= (i >> k & 1) << (h - 1 - k);
		if (i < j) swap(A[i], A[j]);
	}
	//

	//butterfly 
	int cnt = 1;
	for (int b = 1; b < N; b *= 2) {
		ll w = wlist[cnt];
		ll cur = 1;
		ll mul = modpow(w, b);
		for (int j = 0; j < b; j++) {
			for (int k = 0; k < N; k += 2 * b) {
				ll p = cur;
				ll q = (cur*mul) % mod;
				ll pre1 = A[j + k];
				ll pre2 = A[j + k + b];
				A[j + k] = (pre1 + p * pre2)%mod;
				A[j+k+b] = (pre1 + q * pre2)%mod;
			}
			cur = (w * cur)%mod;
		}
		cnt++;
	}
	//

	return A;
}
vector<ll>inv_dft(vector<ll>A,int N) {
	vector<ll>arranged = dft(A, N);
	vector<ll>swapped(N);
	for (int i = 0; i < N; i++)swapped[i] = arranged[(N - i) % N];
	vector<ll>ret(N);
	ll rev = modpow(N,mod-2);
	for (int i = 0; i < N; i++)ret[i] = (rev*swapped[i]) % mod;
	return ret;
}

vector<ll>ntt(vector<ll>A,vector<ll>B){
	//calculate Nth root
	ll P = mod;
	P--;
	int N = 1;
	int cnt = 0;
	while (P % 2 == 0) {
		N *= 2;
		cnt++;
		P /= 2;
		if (A.size() + B.size() <= N)break;
	}
	ll Nroot = modpow(root,P);
	//

	//make list of root
	ll cur = Nroot;
	for (int i = cnt; i >= 0; i--) {
		wlist[i] = cur;
		cur = (cur*cur) % mod;
	}
	//

	A.resize(N);
	B.resize(N);

	A = dft(A,N);
	B = dft(B,N);

	vector<ll>F(N);
	for (int i = 0; i < N; i++) {
		F[i] = (A[i] * B[i]) % mod;
	}
	return inv_dft(F,N);
}
//nttここまで

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

	int N, M;
	cin >> N >> M;
	vector<ll>A(N), B(M);
	for (int i = 0; i < N; i++)cin >> A[i];
	for (int i = 0; i < M; i++)cin >> B[i];

	vector<ll>ans = ntt(A, B);
	for (int i = 0; i < N + M - 1; i++)cout << ans[i] << " ";
	puts("");


	return 0;
}

Measured memory_bytes: 68508
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3e5+5;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,x;cin>>n>>x;
    cout<<3*(n-__gcd(n,x));
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var R = int.Parse(Console.ReadLine());
            if (R < 1200)
            {
                Console.WriteLine("ABC");
            }else if (R < 2800)
            {
                Console.WriteLine("ARC");
            }
            else
            {
                Console.WriteLine("AGC");
            }

        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

void countingSort(vector<int> a,  vector<int> &b, int max_num) {
  vector<int> c(max_num+1, 0);

  for (int i = 0; i < a.size(); i++)
    c[a[i]]++;

  for (int i = 1; i < c.size(); i++)
    c[i] += c[i-1];

  for (int i = a.size()-1; i >= 0; i--) {
    b[c[a[i]]-1] = a[i];
    c[a[i]]--;
  }
}

int main() {
  int n, k = numeric_limits<int>::min();
  cin >> n;

  vector<int> a(n), b(n);

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

  countingSort(a, b, k);

  for (int i = 0; i < n; i++) {
    if (i) cout << ' ';
    cout << b[i];
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 24632
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;
int main(int argc, char const *argv[])
{
  int n, k, q;
  cin >> n >> k >> q;
  int a[q], b[n];
  rep(i, q)
  {
    cin >> a[i];
    a[i]--;
  }
  rep(i, n) b[i] = 0;
  rep(i, q)
  {
    b[a[i]]++;
  }
  rep(i, n)
  {
    //    cerr << b[i] << endl;
    if (k - q + b[i] <= 0)
    {
      cout << "No" << endl;
    }
    else
    {
      cout << "Yes" << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 1408
while True:
    N, M, s, g1, g2 = map(int, input().split())
    if N == M == s == g1 == g2 == 0:
        break
    s, g1, g2 = s - 1, g1 - 1, g2 - 1
    INF = 10 ** 5
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        b1, b2, c = map(int, input().split())
        b1, b2 = b1 - 1, b2 - 1
        D[b1][b2] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    print(min(D[s][i] + D[i][g1] + D[i][g2] for i in range(N)))

Measured memory_bytes: 8028
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=2000005;
int n,a[N],pos[N],ans,f[N];

int main(){
	scanf("%d",&n);
	ans=1e9;
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),pos[a[i]]=i;
	for(int i=1;i<=n;++i){
		if(i>pos[a[i]-1])f[i]=f[pos[a[i]-1]]+1;
		else f[i]=1;
		ans=min(ans,n-f[i]);
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 9216
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	ll N,K; cin>>N>>K;
	vector<int> p(N+1);
	for (int i=1; i<=N; i++)
		cin>>p[i];
	map<int,int> mp;
	set<int> done;
	vector<int> ord;
	int cur=0, start, period, idx=1;
	while(1) {
		if(done.count(idx)) {
			start=mp[idx];
			period=cur-mp[idx];
			break;
		} else {
			ord.push_back(idx);
			mp[idx]=cur++;
			done.insert(idx);
			idx=p[idx];
		}
	}
	if(K<start) cout<<ord[K]<<"\n";
	else cout<<ord[(K-start)%period+start]<<"\n";
	return 0;
}

Measured memory_bytes: 23264
#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int a[5];
    for(int i=0;i<5;i++)
    {
        cin>>a[i];
        
    }
    for(int i=0;i<5;i++)
    {
        if(a[i]==0)
        {
            cout<<i+1;
            break;
        }
        
    }

return 0;
}


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

using ll = long long;
using pii = pair<int, int>;

template <typename T> constexpr T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;
template <> constexpr double inf<double> = 1e18;

int main() {
    int N, M;
    cin >> N >> M;
    vector<double> a(N), sum(N + 1);
    for(int i = 0; i < N; ++i) {
        cin >> a[i];
        sum[i + 1] = sum[i] + a[i];
    }
    

    auto calc = [&](int l, int r) { // [l..r]
        double w = r - l + 1;
        double vol = sum[r + 1] - sum[l];
        return vol / w;
    };

    vector<vector<double>> dp(N + 1, vector<double>(N + 1, -inf<double>));
    dp[0][0] = 0;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j <= M; ++j) {
            if(j + 1 <= M) {
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[i]);
            }
            if(j - 1 >= 0) {
                for(int k = 0; k < i; ++k) {
                    dp[i + 1][j] = max(dp[i + 1][j], dp[k][j - 1] + calc(k, i));
                }
            }
        }
    }

    cout << fixed << setprecision(10) << *max_element(begin(dp[N]), end(dp[N])) << endl;
}


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

int k[3];
signed main(){
	string a;cin>>a;
	for(char i:a){
		k[i-'a']++;
		}
	sort(k,k+3);
	if(k[2]-k[0]<=1)puts("YES");
	else puts("NO");	
	}

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

int main() {
    int a, b, c; cin >> a >> b >> c;
    if (a == b and b != c) cout << c << endl;
    if (b == c and c != a) cout << a << endl;
    if (c == a and a != b) cout << b << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <deque>
#include <set>
#include <numeric>
using namespace std;
using ll = long long;

#define next '\n'
#define sp " "
#define print(x) cout << (x)
#define println(x) cout << (x) << next
#define stop return(0)
#define rep(i, n) for(int (i) = (0); (i) < (n); (++i))
#define FOR(i, start, end) for(int (i) = (start); (i) < (end); (++i))
#define foreach(elem, _list) for(auto& (elem) : (_list))
#define view(_list) foreach(e, _list){ cout << e << sp; } cout << next
#define FAST ios::sync_with_stdio(false); cin.tie(nullptr)
#define size(s) (s).size()
#define ALL(vec) (vec).begin(), (vec).end()
#define pb(e) push_back(e)
#define INF 1e+8
#define PI acos(-1)
#define TAU PI * 2
const ll MOD = 1000000007;

set<string> st;

int main(){
    int n;
    cin >> n;
    rep(i, n){
        string s;
        cin >> s;

        st.insert(s);
    }

    println(size(st));
}

Measured memory_bytes: 19224
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>

using namespace std;

int main() {
    int s;
    int mod = 1e9+7;
    cin >> s;
    vector<int> dp(s+1, 1);
    
    for (int i = 0; i <= s; ++i) {
        if (i < 3) 
            dp[i] = 0;
        for (int j = 3; j <= i; ++j) {
            dp[i] += dp[i-j];
            dp[i] %= mod;
        }
    }
    cout << dp[s];
}

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

int main()
{
    long long int n,a,b;
    cin>>n>>a>>b;
    long long int rem;
    long long int count;
    count=n/(a+b);
    count=count*a;
    
    rem=n%(a+b);
    if(rem<a)
    count=count+rem;
    else
    count=count+a;
    
    cout<<count;
    
    return 0;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <set>
#include <queue>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define pb(x) push_back(x)
typedef long long ll;
typedef unsigned long long ull;
const int mod=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=100+5;
int dxy[8][2]= {1,0,0,1,-1,0,0,-1,-1,-1,-1,1,1,1,1,-1};
int cnt;
char a[N][N];
int n,m;
bool in(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<m) return true;
    return false;
}
void dfs(int x,int y)
{
    for(int i=0; i<8; i++)
    {
        int nx=x+dxy[i][0];
        int ny=y+dxy[i][1];
        if(in(nx,ny)&&a[nx][ny]=='#')
            cnt++;
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                scanf(" %c",&a[i][j]);
       /* for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
                printf("%c",&a[i][j]);
            puts("");
        }*/
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
            {
                if(a[i][j]=='.')
                {
                    cnt=0;
                    dfs(i,j);
                    a[i][j]=cnt+'0';
                }
            }
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
                printf("%c",a[i][j]);
            puts("");
        }
    }
    return 0;
}


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

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++) 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

mt19937 rnd(time(NULL));

const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = INF + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int N = 51;

int n;
li k;

struct mat{
	int a[N][N];
	mat(){
		memset(a, 0, sizeof(a));
	};
	int* operator [](int x){
		return a[x];
	}
};

mat a;

bool read () {
	if (scanf("%d%lld", &n, &k) != 2)
		return false;
	forn(i, n) forn(j, n)
		scanf("%d", &a[i][j]);
	return true;
}

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	return a;
}

int mul(int a, int b){
	return a * li(b) % MOD;
}

mat mul(mat a, mat b){
	mat c;
	forn(i, n) forn(j, n) forn(k, n)
		c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
	return c;
}

mat binpow(mat a, li b){
	mat res;
	forn(i, n) res[i][i] = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

void solve(){
	a = binpow(a, k);
	int ans = 0;
	forn(i, n) forn(j, n)
		ans = add(ans, a[i][j]);
	printf("%d\n", ans);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	int tt = clock();
	
#endif
	
	cerr.precision(15);
	cout.precision(15);
	cerr << fixed;
	cout << fixed;

	while(read()) {	
		solve();
		
#ifdef _DEBUG
	cerr << "TIME = " << clock() - tt << endl;
	tt = clock();
#endif

	}
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vll=vector<ll>;
using vvll=vector<vll>;


int main(void)
{
	char s[100000+2], t[100000+2];

	while(scanf("%100000[a-z]\n%100000[a-z]\n", s, t)==2)
	{
		vvi cs(26);
		vi ct(26);
		ll ls=0;

		for(int i=0;s[i];i++)
		{
			cs[s[i]-'a'].push_back(i);
			ls++;
		}

		int p=0;
		int loop=0;
		for(int i=0;t[i];i++)
		{
			int x=t[i]-'a';

			if(cs[x].size()==0)
			{
				loop=-1;
				break;
			}
			auto it=lower_bound(cs[x].begin(), cs[x].end(), p);
			if(it==cs[x].end())
			{
				loop++;
				p=0;
				i--;
			}
			else
			{
				p=*it+1;
			}
		}

		ll ans=-1;
		if(loop>=0)
		{
			ans=loop*ls+p;
		}

		printf("%lld\n", ans);
	}
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  string w;
  cin >> w;

  map<char, int> m;
  for (int i = 0; i < w.length(); i++)
  {
    m[w[i]]++;
  }

  for (auto ele : m)
  {
    if (ele.second % 2 == 1)
    {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  int n;
  ll W;
  ll w0;
  cin >> n >> W;
  vector<vector<int>> b(4);
  rep(i, n) {
    int w, v;
    cin >> w >> v;
    if(i == 0) w0 = w;
    b[w-w0].emplace_back(v);
  }
  vector<vector<int>> d(4);
  rep(i, b.size()) {
    if(b[i].size() == 0) {
      d[i].emplace_back(0);
      continue;
    }
    sort(b[i].rbegin(), b[i].rend());
    d[i].resize(b[i].size()+1);
    rep(j, b[i].size()+1) {
      if(j == 0) continue;
      d[i][j] = d[i][j-1] + b[i][j-1];
    }
  }
  int ans = 0;
  rep(i, d[0].size()) {
    rep(j, d[1].size()) {
      rep(k, d[2].size()) {
        rep(l, d[3].size()) {
          ll w1 = w0 * (ll)i;
          ll w2 = (w0+1) * (ll)j;
          ll w3 = (w0+2) * (ll)k;
          ll w4 = (w0+3) * (ll)l;
          if(w1+w2+w3+w4 > W) continue;
          chmax(ans, d[0][i] + d[1][j] + d[2][k] + d[3][l]);
        }
      }
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;


int rev(int bit, int i) {
    return bit ^ (1 << i);
}

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

    int n = s.size();

    vector<int> dp(n + 1, INT_MAX / 10);
    vector<int> mval(1ll << 26, INT_MAX / 10);

    dp[0] = 0;
    mval[0] = 0;

    int par = 0;
    for (int i = 1; i <= n; i++) {
        par = rev(par, s[i - 1] - 'a');
        cmin(dp[i], mval[par] + 1);
        for (int j = 0; j < 26; j++) {
            par = rev(par, j);
            cmin(dp[i], mval[par] + 1);
            par = rev(par, j);
        }
        cmin(mval[par], dp[i]);
    }
    cout << dp[n] << endl;
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N, M;
std::priority_queue<P> pq;
std::set<int> se;

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

  std::cin >> N >> M;

  for(int i=0;i<N;++i){
      int A, B;
      std::cin >> A >> B;

      if(M - A >= 0){
          pq.emplace(B, M - A);
      }
  }

  for(int i=0;i<M;++i){
      se.emplace(-i);
  }

  int res = 0;

  until(pq.empty()){
      int B, A;
      std::tie(B, A) = pq.top();
      pq.pop();

      auto it = se.lower_bound(-A);
      
      if(it != se.end()){
          res += B;
          se.erase(it);
      }
  }

  std::cout << res << std::endl;
}


Measured memory_bytes: 5748
# -*- coding: utf-8 -*-
from collections import Counter
def inpl(): return tuple(map(int, input().split()))

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

C = Counter(A)
if C[-2] % 2 == 0:
    ans = [i+1 for i, a in enumerate(A) if abs(a) == 2]
    print(len(ans))
    if len(ans):
        print(*ans, sep="\n")
elif C[-1] > 0:
    ans = [i+1 for i, a in enumerate(A) if abs(a) == 2] + [A.index(-1) + 1]
    print(len(ans))
    if len(ans):
        print(*sorted(ans), sep="\n")
else:
    d = N -A[::-1].index(-2)
    ans = [i+1 for i, a in enumerate(A) if abs(a) == 2]
    del ans[ans.index(d)]
    print(len(ans))
    if len(ans):
        print(*ans, sep="\n")


Measured memory_bytes: 6020
#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAX_STRING 100

	char sInput[MAX_STRING+1]="";

int main() {
	char* psInput;

	long nA=0;
	long nB=0;
	long nTemp=0;
	long nAnswer=0;

	// read line 1
	gets(sInput);
	psInput = strtok(sInput," ");
	nA = atol(psInput);
	psInput = strtok(NULL," ");
	nB = atol(psInput);

	if(nA>nB){
		nTemp=nA;
		nA=nB;
		nB=nTemp;
	}

	switch(nA){
	case 1:
		if(nB==1){
			nAnswer=1;
		} else {
			nAnswer=nB-2;
		}
		break;
	case 2:
		// do nothing
		break;
	default:
		nAnswer=(nA-2)*(nB-2);
		break;
	}

	printf("%ld\n",nAnswer);

    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define lg long long int
#define loop(i,s,e) for(lg i=s;i<=e;i++)
#define iloop(i,s,e) for(lg i=e;i>=s;i--)
#define pb push_back
#define mp make_pair
#define mod 1000000007


using namespace std;

lg min(lg a,lg b)
{return a<b?a:b;}
lg max(lg a,lg b)
{return a>b?a:b;}
lg lcm(lg a ,lg b)
{
    return (a*b)/__gcd(a,b);
}
lg n,m,k,ans;
lg bin_search(vector<lg>& a,lg start,lg end,lg num)
{
    if(a[end]<=num) return end;
    else if(a[start]>num) return start-1;
    else if(a[start]==num) return start;
    else if(start+1>=end) return start;
    else
    {
        lg mid = (start+end)/2;
        if(a[mid]==num) return mid;
        else if(a[mid]>num) return bin_search(a,start,mid-1,num);
        else return bin_search(a,mid+1,end,num);
    }
}

int main()
{
    cin>>n>>m>>k;
    vector<lg>a(n,0);
    vector<lg>b(m,0);
    ans=0;
    lg h=0;
    for(lg i=0;i<n;i++)
    {
        cin>>a[i];
        a[i]+=h;
        h=a[i];
        if(h<=k) ans=i+1;
    }
    for(lg i=0;i<m;i++)
        cin>>b[i];

    lg time=0;
    for(lg i=0;i<m;i++)
    {
        time+=b[i];
        if(time>k) break;
        lg ind = bin_search(a,0,n-1,k-time)+1;
        ans=max(ans,i+ind+1);
    }
    cout<<ans<<endl;

}


Measured memory_bytes: 6368