akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP (i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back

using namespace std;

typedef long long ll;

const int INF = 1 << 29;

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

    ll ans = x;
    ll a = x;
    ll b = n - x;
    ll t = 0;
    while (1) {
        // cout << a << ' ' << b << endl;
        if (t % 2 == 0) {
            if (a % b == 0) {
                ans += a / b * 2 * b;
                if (t != 0) ans -= b;
                break;
            } else {
                ans += a / b * 2 * b + b;
                if (t != 0) ans -= b;
                ll _a = a;
                a = b;
                b = _a % b;
            }
        } else {
            if (a % b == 0) {
                ans += a / b * 2 * b - b;
                break;
            } else {
                ans += a / b * 2 * b;
                ll _a = a;
                a = b;
                b = _a % b;
            }
        }
        // cout << ans << " --- " << endl;
        t++;
    }

    cout << ans << endl;
}


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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

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

	ll s;cin >> s;
	ll syou = s / INF;
	ll amari = s % INF;

	if(amari == 0){
		cout << 0 << " " << 0 << " " << INF << " " << 0 << " " << INF << " " << syou;
	}
	else {
		syou++;
		cout << 0 << " " << 0 << " " << INF << " " << 1 << " " << INF - amari << " " << syou << endl;
	}

	return 0;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    while (n > 0) {
        int x = n % 10;
        if (x == 7) {
            cout << "Yes";
            return 0;
        }
        n = n / 10;
    }
    cout << "No";
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
int main() {
  int n;
  string s,t;
  cin >> n >> s >> t;
  string u(2*n,'0');
  for(int i = 0; i < 2*n; i++){
    if(i%2 == 0){
      u.at(i) = s.at(i/2);
    }else{
      u.at(i) = t.at(i/2);
    }
  }
  cout << u << endl;
  
  }


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define INF 1LL << 62
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i, m) for (long i = 0; i < m; i++)
#define FOR(i, n, m) for (long i = n; i < m; i++)
#define ALL(v) v.begin(),v.end() 
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef long double ld;

int main(){
  int n;
  cin >> n;
  int a[n], b[n], p[n];
  REP(i, n) cin >> p[i];
  int s[n];
  REP(i, n){
    s[p[i]-1] = i;
  }
  int t = s[0];
  REP(i, n) s[i] -= t;
  a[0] = 0;
  b[0] = 0;
  FOR(i, 1, n){
    if(s[i] > s[i-1]){
      b[i] = b[i-1] - 1;
      a[i] = s[i] - b[i];
    }
    else{
      a[i] = a[i-1] + 1;
      b[i] = s[i] - a[i];
    }
  }
  int ma = 0, mb = 0;
  REP(i, n){
    ma = min(ma, a[i]);
    mb = min(mb, b[i]);
  }
  REP(i, n){
    a[i] -= ma-1;
    b[i] -= mb-1;
  }
  REP(i, n){
    cout << a[i];
    if(i == n-1) cout << endl;
    else cout << " ";
  }
  REP(i, n){
    cout << b[i];
    if(i == n-1) cout << endl;
    else cout << " ";
  }
  return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>

#define INF 1e09

using std::cin;
using std::cout;
using std::endl;
using std::setprecision;
using std::fixed;
using std::pair;
using std::make_pair;
using std::min;
using std::max;
using std::string;
using std::vector;
using std::list;
using std::map;
using std::set; // insert erase find count
using std::queue;
using std::priority_queue;
using std::stack;

typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, pair<int, int> > PIII;

int main(void) {
    int n;
    cin >> n;
    VI input(n + 1, 0);
    int count = 0;
    VI list;
    for (int i = 1; i <= n; i++) {
        cin >> input[i];
        if (input[i] == i) {
            count++;
            list.push_back(i);
        }
    }
    int list_size = (int)list.size();
    int ans = list_size;
    for (int i = 0; i < list_size - 1; i++) {
        if (list[i + 1] - list[i] == 1) {
            i++;
            ans--;
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 1276
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 105;
const int MAXW = 1e5 + 5;
const long long int neg_inf = -1e18;
int N, W;
long long int DP[MAXN][MAXW];
long long wt[MAXN];
long long V[MAXN];

long long rec(int idx, int weight)
{
    if(idx == N)
    {
        if(weight <= W)
            return 0;
        return neg_inf;
    }
    if(weight > W)
        return neg_inf;
    if(DP[idx][weight] != -1)
        return DP[idx][weight];
    return DP[idx][weight] = max(V[idx] + rec(idx + 1, weight + wt[idx]), rec(idx + 1, weight));
}

int main()
{
    cin >> N >> W;
    for(int i = 0; i < N; ++i)
        cin >> wt[i] >> V[i];
    for(int i = 0; i < MAXN; ++i)
        for(int j = 0; j < MAXW; ++j)
            DP[i][j] = -1;
    cout << rec(0, 0) << endl;
    return 0;
}

Measured memory_bytes: 82304
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
bitset<2010*2010> dp;
int main(){
    dp[0]=1;
    int n;
    cin>>n;
    int  sum=0;
    V<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=0;i<n;i++){
        dp|=(dp<<a[i]);
    }
    for(int i=(sum+1)/2;i<=2000*2000;i++){
        if(dp[i]){
            cout<<i<<"\n";
            return 0;
        }
    }
}

Measured memory_bytes: 1792
import heapq
INF = float('inf')

def dijkstra(g, s):
    n = len(g)
    dist = [INF] * n
    dist[s] = 0
    hq = []
    heapq.heappush(hq, (dist[s], s))
    while hq:
        cost, u = heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v, c in g[u]:
            if dist[v] <= dist[u] + c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq, (dist[v], v))
    return dist

V, E, r = map(int, input().split())
g = [[] for _ in range(V)]
# cost = [[m for _ in range(V)] for _ in range(V)]
for i in range(E):
    s,t,d = map(int, input().split())
    g[s].append((t, d))
    # cost[s][t] = d

res = dijkstra(g, r)
for i in res:
    print('INF' if i == INF else i)




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

int main(){
  int n; cin>>n;
  map<int,int> mp;
  rep(i,n){
    int a,b; cin>>a>>b;
    mp[b]+=a;
  }
  int time=0;
  bool ans=1;
  for(auto x : mp){
    time+=x.second;
    if(time>x.first) ans=0;
  }
  if(ans) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}




Measured memory_bytes: 12952
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cout << H << " "; debug_out(T...); }
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n;
  cin >> n;
  vector<ll> a(n);
  int numneg = 0;
  ll sum = 0, mini = 1LL<<60;
  rep(i,n) {
    cin >> a[i];
    if (a[i] < 0) {
      numneg++;
      chmin(mini, -a[i]);
    }
    else chmin(mini, a[i]);
    sum += fabs(a[i]);
  }
  debug(sum, mini);
  if (numneg % 2 == 1) sum -= mini*2;
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char c[20];
int i,n,t1,t2;

int main()
{
	scanf("%s",c+1);
	n=strlen(c+1);
	for (i=1;i<=n;i++)
		t1=t1+c[i]-48;
	t2=c[1]-49+(n-1)*9;
	printf("%d",max(t1,t2));
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>

using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1 << 30;

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

	vector<int> dp(n + k, INF);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= k; j++) {
			chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
		}
	}

	cout << dp[n - 1] << endl;

	return 0;
}

Measured memory_bytes: 4044
n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

q, k = map(int, input().split())

dists = {}
def build(x, d=0):
    ss = [(x, 0)]
    while ss:
        x, d = ss.pop()
        if x not in dists:
            dists[x] = d
            for c in edges.get(x, []):
                ss.append((c, d + lens[(min(x,c), max(x,c))]))

build(k)

for _ in range(q):
    [x, y] = map(int, input().split())
    print(dists[x] + dists[y])

Measured memory_bytes: 71212
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let N: usize = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };
    let H: Vec<i64> = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    };

    let (ans, _, _) = H.iter().fold((0, 0, 0), |(res, c, p), &h| {
        if h <= p {
            (std::cmp::max(res, c + 1), c + 1, h)
        } else {
            (res, 0, h)
        }
    });

    println!("{}", ans);
}


Measured memory_bytes: 8444
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <utility>
using namespace std;

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

  int cnt = 0;
  int before = 0;
  int ans = 0;

  for(int i=0; i<n; i++){
    if(a[i] == before){
      cnt++;
    }
    else{
      ans += cnt/2;
      cnt = 1;
      before = a[i];
    }
  }

  cout << ans + cnt/2 << endl;

  return 0;
}

Measured memory_bytes: 256
N = int(input())
S = input()
d1 = {}
d2 = {}
d3 = {}
for i in range(N):
    s = S[i]
    for x in d2:
        d3[x+s] = 1
    for x in d1:
        d2[x+s] = 1
    d1[s] = 1
print(len(d3))

Measured memory_bytes: 41708
a=input()
b=input()
c=input()
l='a'
while(1):
  if(l=='a'):
    if(len(a)<1):
      print('A')
      break
    l=a[0]
    a=a[1:]
  elif(l=='b'):
    if(len(b)<1):
      print('B')
      break
    l=b[0]
    b=b[1:]
  else:
    if(len(c)<1):
      print('C')
      break
    l=c[0]
    c=c[1:]

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

int main(){
    string s;
    cin >> s;
    int N = s.size();
    int ans = N-1;
    for (int i = 0; i < 26; i++) {
        char target = 'a'+i;
        if (count(s.begin(), s.end(), target) == 0) continue;
        string t = s;
        int M = N;
        while (count(t.begin(), t.end(), target) < M) {
            M--;
            for (int i = 0; i < M-1; i++) {
                if (t[i+1] == target) t[i] = target;
            }
            t.resize(M);
        }
        ans = min(ans, N-M);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define mod 1000000007
#define FT() int t; scanf("%d",&t); while(t--)
#define pb push_back
#define nl printf("\n")
#define fi(i,start,end) for(int i=start; i < (int)end ; ++i)
#define ip(n)   scanf("%d",&n)
#define mz(a)   memset(a,0,sizeof(a))
#define inpArr(A,n) fi(i,0,n)   ip(A[i]);
#define print(a)  for(auto i : a)   cout<<i<<" "; nl;
#define Fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
ll max(ll a,ll b) { return a>b?a:b;}
ll min(ll a,ll b) { return a<b?a:b;}

void solve()
{
    
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #endif
    //std::cout << std::fixed;
    //std::cout << std::setprecision(6);
    int l,d,r;
    cin>>l>>d>>r;
    vector<int> v;
    for(int i = r;i<=d;i+=r)
      v.pb(i);
    int c=0;
    for(auto i : v)
      if(i>=l && i<=d)
        c++;
    cout<<c;

    #ifndef ONLINE_JUDGE
    cout<<"\nTime Elapsed : " << 1.0*clock() / CLOCKS_PER_SEC << " s";
    #endif
    
    return 0;
}


Measured memory_bytes: 3596
#include <stdio.h>
#include<math.h>
int main()
{
    int a,i,j,count=0;
    scanf("%d",&a);
    int arr[100000];
    arr[1]=a;
    for(i=2;;i++)
    {
        if(arr[i-1]%2==0)
        arr[i]=arr[i-1]/2;
        else
        arr[i]=3*arr[i-1]+1;
        for(j=1;j<i;j++)
        {
            if(arr[j]==arr[i])
            {
                printf("%d",i);
                count++;
                break;
            }
        }
        if(count!=0)
        break;
    }
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstdlib>

using namespace std;

int main(){
  int X,A,B;
  cin >> X >> A >> B;
  X-=A;
  X%=B;
  cout << X << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <stdio.h>
using namespace std;
int n,m,deck[4][14];
char s;
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
	cin>>s>>m;
	if(s=='S'){
	deck[0][m]=1;}else
	if(s=='H'){
	deck[1][m]=1;}else
		if(s=='C'){
	deck[2][m]=1;}else{
		deck[3][m]=1;}}
	for(int i=0;i<4;i++){
	for(int ii=1;ii<14;ii++){
		if(deck[i][ii]<=0&&i==0){cout<<"S "<<ii<<endl;}else
	if(deck[i][ii]<=0&&i==1){cout<<"H "<<ii<<endl;}else
	if(deck[i][ii]<=0&&i==2){cout<<"C "<<ii<<endl;}else
	if(deck[i][ii]<=0){cout<<"D "<<ii<<endl;}}}
	return 0;}


Measured memory_bytes: 1160
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC060
{
    public class QuestionB
    {
        public static void Main(string[] args)
        {
            var abc = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var (a, b, c) = (abc[0], abc[1], abc[2]);

            for (int i = 0; i < b; i++)
            {
                if (a * i % b == c)
                {
                    Console.WriteLine("YES");
                    return;
                }
            }

            Console.WriteLine("NO");
        }
    }
}


Measured memory_bytes: 28192
n,k = map(int,input().split())
mod = 10**9+7
ans = 0
nums = [i for i in range(n+1)]
for i in range(k,n+2):
    res1 = i*(i-1)//2
    res2 = i*(2*n-i+1)//2
    ans += res2 - res1+1
    ans %= mod
print(ans)
    
    
    

Measured memory_bytes: 16892
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;
 
int main(){

    int M,D,ans=0;
    cin>>M>>D;

    for(int m=1;m<=M;m++){
        for(int d=1;d<=D;d++){
            int m10=d/10;
            int m1=d%10;
            if(m==(m10*m1)&&m10>=2&&m1>=2)ans++;
        }
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>
#include <cmath>
#include <stack>
#include <random>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

vector<int> graph[100001];
vector<int> color(100001);

vector<int> dist(100001);

void dfs(int v, int d, int c) {
  if (color[v] == 0) {
    color[v] = c;
  }
  if (dist[v] >= d) {
    return;
  }
  dist[v] = d;
  for(auto& e: graph[v]) {
    dfs(e, d-1, c);
  }
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; scanf("%d%d",&n,&m);
  rep(i, m) {
    int a, b; scanf("%d%d",&a,&b);
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  int q; scanf("%d",&q);
  vector<pair<int, P>> vec(q);
  rep(i, q) {
    int v, d, c; scanf("%d%d%d",&v,&d,&c);
    vec[i] = make_pair(v, P(d,c));
  }

  for(int i=q-1; i>=0; i--) {
    int v = vec[i].first;
    int d = vec[i].second.first;
    int c = vec[i].second.second;
    dfs(v, d, c);
  }

  for(int i=1; i<=n; i++) {
    cout << color[i] << '\n';
  }
}


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

using namespace std;

typedef long long int64;
const int64 mod = 1e9 + 7;

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

  int sum = 0, low = 0;
  for(auto &c : S) {
    sum += c == '(' ? 1 : -1;
    low = min(low, sum);
  }

  while(low < 0 || sum < 0) S = "(" + S, ++low, ++sum;
  while(sum > 0) S += ")", --sum;
  cout << S << endl;
}


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

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

const int MOD = 1e9+7;

using Vec = std::vector<int>;
using Mat = std::vector<Vec>;

Mat add(Mat a, Mat b) {
	rep(i,a.size()) rep(j,a[0].size()) {
		a[i][j]+=b[i][j];
	}
	return a;
}

Mat mul(Mat a, Mat b) {
	int n = a.size();
	Mat c = a;
	rep(i,n) rep(j,n) c[i][j]=0;
	rep(i,n) rep(j,n) rep(k,n) {
		c[i][j]+=a[i][k]*b[k][j]%MOD;
		c[i][j]%=MOD;
	}
	return c;
}

Mat pow(Mat a, int k) {
	int n = a.size();
	Mat b = a;
	Mat I = a;
	rep(i,n) rep(j,n) I[i][j]=(i==j);
	while(k) {
		if(k&1) I=mul(I,b);
		b=mul(b,b);
		k>>=1;
	}
	return I;
}

signed main() {
	int n,k;
	std::cin >> n >> k;
	Mat g(n,Vec(n));
	rep(i,n) rep(j,n) std::cin >> g[i][j];
	Mat x = pow(g,k);
	int sum = 0;
	rep(i,n) rep(j,n) sum=(sum+x[i][j])%MOD;
	std::cout << (sum) << '\n';
	return 0;
}



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

int main()
{
  string s;
  cin>>s;
  int i,j;
  int l=0,r=s.size()-1,c=0;
  while(l<=r)
  {
    if(s[l]==s[r])
    {
      l++,r--;
    }
    else
    {
      c++;
      l++,r--;
    }
  }
  cout<<c;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back
template<class T> inline int chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline int chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1<<29;
const ll LINF = 1LL<<58;
const int mod = 1000000007;

void solve() {
    int n;
    cin >> n;
    int A[202020];
    rep(i, n - 1) {
        int a;
        cin >> a;
        A[a - 1]++;
    }
    rep(i, n) {
        cout << A[i] << endl;
    }

}

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


Measured memory_bytes: 4484
#include <iostream>
#include <map>
using namespace std;
typedef pair<int, int> P;

int par[2][200100];
int treerank[2][200100];

void init(int n, int i){
  for(int j=0; j<n; j++){
    par[i][j] = j;
    treerank[i][j] = 0;
  }
}

int find(int x, int i){
  if(par[i][x] == x) return x;
  return par[i][x] = find(par[i][x], i);
}

void unite(int x, int y, int i){
  x = find(x, i); y = find(y, i);
  if(x == y) return;
  if(treerank[i][x] > treerank[i][y]){
    par[i][y] = x;
  }
  else{
    par[i][x] = y;
    if(treerank[i][x] == treerank[i][y]) treerank[i][y]++;
  }
}

int main(){
  int N, K, L;
  cin >> N >> K >> L;
  init(N, 0);
  for(int i=0; i<K; i++){
    int p, q;
    cin >> p >> q;
    unite(p-1, q-1, 0);
  }
  init(N, 1);
  for(int i=0; i<L; i++){
    int r, s;
    cin >> r >> s;
    unite(r-1, s-1, 1);
  }
  P con[N];
  map<P, int> map;
  for(int i=0; i<N; i++){
    con[i] = P(find(i, 0), find(i, 1));
    map[con[i]]++;
  }
  for(int i=0; i<N; i++){
    cout << map[con[i]] << " " << flush;
  }
}

Measured memory_bytes: 16640
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <cmath>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for (int i = (int)(k); i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rREP(i, k, n) for (int i = (int)(n)-1; i >= k; i--)

#define debug(x) cerr<<#x<<": "<<x<<'\n'

#define fi first
#define se second

#define vi vector<int>
#define pb push_back
#define mp make_pair

#define pcnt __builtin_popcount

typedef long long ll;

const int inf = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int a[1000000] = {};
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<pair<int,int> > a(n);
    vector<pair<int,int> > c(n);
    rep(i,n) cin >> a[i].fi >> a[i].se;
    rep(i,n) cin >> c[i].se >> c[i].fi;
    sort(a.begin(),a.end());
    sort(c.begin(),c.end());
    int ans = 0;
    while(!a.empty()){
      rep(i,c.size()){
        if(a.back().fi < c[i].se && a.back().se < c[i].fi){
          // cout << "debug : " << a.back().fi << " " << a.back().se << " "<< c[i].se << " " << c[i].fi << endl;
          c.erase(c.begin()+i);
          ans++;
          break;
        }
      }
      a.pop_back();
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
a = list(input())
b = list(input())

aa = len(a)
bb = len(b)
c = 0

def co(pp,qq,p):
	for i in range(p):
		if pp[i] != qq[i]:
			return 0
	return 1 

if aa != bb:
	print("No")

else:
	for i in range(aa):
		k = a[-1]
		a = a[:aa-1]
		a.insert(0,k)
		if c == 0:
			c = co(a,b,aa)


if c == 1:
	print("Yes")
else:
	print("No")



Measured memory_bytes: 38384
#include<iostream>
using namespace std;
class Doubling{
    public:
    int state_num,max_k;
    int** table;

    Doubling(int sz,int64_t mx):state_num(sz),max_k(64-__builtin_clzll(mx))
    {table=new int*[max_k];for(int i=0;i<max_k;i++)table[i]=new int[state_num];}

    ~Doubling(){for(int i=0;i<max_k;i++)delete[] table[i];delete[] table;}

    void set_next(int state,int next){table[0][state]=next;}
    void build(){
        for(int k=1;k<max_k;k++){
            for(int i=0;i<state_num;i++){
                table[k][i]=(table[k-1][i]!=-1?table[k-1][table[k-1][i]]:-1);
            };
        }
    }
    int query(int state, int64_t step){
        for(int i=0;i<max_k;i++)if((step>>i)&1)state=table[i][state];
        return state;
    }
};
long long N,K;
int main(){
    cin>>N>>K;
    int A[N];
    for(int i=0;i<N;i++){cin>>A[i];A[i]--;}
    Doubling d(N,K);
    for(int i=0;i<N;i++)d.set_next(i,A[i]);
    d.build();
    cout<<d.query(0,K)+1LL<<endl;
    return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int a,b;
  cin >> a >> b;
  if(b%a){
    cout << b-a << endl;
  }else{
    cout << b+a << endl;
  }
  return 0;
}

Measured memory_bytes: 256
a=list(input())
kekka=[]
for i in range(len(a)):
    if a[i]=="A":
        kekka.append("T")
    elif a[i]=="T":
        kekka.append("A")
    elif a[i]=="C":
        kekka.append("G")
    elif a[i]=="G":
        kekka.append("C")

print(kekka[0])


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

using namespace std;

const int MOD = 1e9+7;

vector<int> adj[100010];
long b[100010], w[100010];

void rec(int v = 0)
{
	b[v] = w[v] = 1;
	for (int nv : adj[v])
	{
		if (b[nv]) continue;
		rec(nv);
		b[v] *= w[nv];
		b[v] %= MOD;
		w[v] *= w[nv] + b[nv];
		w[v] %= MOD;
	}
}

void solve()
{
	int N;
	cin >> N;
	while(--N)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	rec();

	cout << (b[0] + w[0]) % MOD << endl;
}

int main(void)
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 11392
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <cstdio>
#include <set>
#include <stack>
#include <queue>
#include <cassert>
#include <numeric>
//#include <bits/stdc++.h>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
//#define int ll
typedef long long ll;

const int md = 1000000007;
const int INF = 1<<30;
using namespace std;

int main(){
    
    string a[10];
    a[0] = "0111111";
    a[1] = "0000110";
    a[2] = "1011011";
    a[3] = "1001111";
    a[4] = "1100110";
    a[5] = "1101101";
    a[6] = "1111101";
    a[7] = "0100111";
    a[8] = "1111111";
    a[9] = "1101111";

    
    while(true){
        int tmp; cin >> tmp;
        if(tmp == -1) return 0;

        vi x;
        rep(i,tmp){
            int tmp2; cin >> tmp2;
            x.pb(tmp2);
        }
        cout << a[x[0]] << endl;
        rep(i,x.size()-1){
            string ans = "";

            rep(j,7){
                if(a[x[i]][j] == a[x[i+1]][j]){
                    ans += '0';
                }else{
                    ans += '1';
                }
            }
            cout << ans << endl;
        }
    }

    


}


Measured memory_bytes: 3160
n,k=map(int,input().split())
a=list(map(int, input().split()))

logk = k.bit_length()
doubling = []
for _ in range(logk):
  tmp = [0] * n
  doubling.append(tmp)

for i in range(n):
  doubling[0][i] = a[i] - 1

for i in range(1,logk):
  for j in range(n):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]

now = 0
pos = 0
while k:
  if k & 1:
    now = doubling[pos][now]
  k = k >> 1
  pos += 1

print(now+1)


Measured memory_bytes: 182664
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)                                                         

using namespace std;
#define ll long long

int main(){
  int N, M, X;
  cin >> N >> M >> X;
  int A[N+1];
  for(int i=0; i<N; i++)
    A[i] = 0;
  for(int i=0; i<M; i++){
    int in;
    cin >> in;
    A[in] = 1;
  }
  int tmp = 0;
  for(int i=0; i<X; i++){
    tmp += A[i];
  }
  cout << min(tmp, M-tmp) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rng(a) a.begin(),a.end()
#define pb push_back
#define sz(x) (int)(x).size()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;


int main() {
  int n; cin>>n;
  vl v(n);
  for (int i=0; i<n; i++){
    cin >> v[i];
  }
  ll ans=0;
  for (int i=0; i<n-1; i++){
    for (int j=i+1; j<n; j++){
      ll diff = abs(v[i]-v[j]);
      ans = max(ans, diff);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
x = list(map(int, input().split()))
ans = 10**9
for i in range(n-k+1):
    l = x[i]
    r = x[i+k-1]
    if r*l < 0:
        tmp = abs(l)+abs(r)+min(abs(l), abs(r))
    else:
        tmp = max(abs(l), abs(r))
    if tmp < ans:
        ans = tmp
print(ans)

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

int func(int64_t n) {
  if (n < 10) return 1;
  
  int digits = 0;
  
  while (n > 0) {
    n /= 10;
    digits++;
  }
  
  return digits;
}

int main(){
  int64_t N;
  cin >> N;
  
  int ans = 1000;
  
  for (int64_t i = 1; i * i <= N; i++) {
    if (N % i == 0) {
      int64_t j = N / i;
      ans = min(ans, func(j));
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    deque<int> que;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if(i % 2 == 0) {
            que.push_front(a);
        } else {
            que.push_back(a);
        }
    }
    if(n % 2) {
        for(int i = 0; i < n; i++) {
            cout << que[i] << ' ';
        }
    } else {
        for(int i = n - 1; i >= 0; i--) {
            cout << que[i] << " ";
        }
    }
    cout << endl;
}

Measured memory_bytes: 3072
N=int(input())
C=input()
from collections import Counter
count=Counter(C)
#print(count)
countR=count["R"]
countW=count["W"]
missR=0
missW=0
for i in range(N):
    now=C[i]
    if now=="W" and i<N-countW:
        missW+=1
    if now=="R" and i>countR:
        missR+=1
# print(countR, countW)
X=min(missW, missR)

ans=min(missW, missR)+abs(missR-missW)

print(ans)
#print(missR, missW)

Measured memory_bytes: 68676
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

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

    int N;
    cin >> N;

    int sum = 0;
    int target = -1;
    FOR(i, 1, N) {
        sum += i;
        if (N <= sum) {
            target = sum - N;
            break;
        }
    }

    sum = 0;
    FOR(i, 1, N) {
        if (i == target) continue;
        sum += i;
        cout << i << endl;
        if (sum == N) {
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 256
using System;

namespace Dodecagon
{
    class Program
    {
        static void Main(string[] args)
        {
            int a;
            string　num= System.Console.ReadLine();
            a=System.Int32.Parse(num);
            a=a*a;
            int  i=3*a;
            Console.WriteLine(i);
        }
    }
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	cin>>x>>y>>z;
	set<int> S;
	S.insert(x);
	S.insert(y);
	S.insert(z);
	cout<<S.size()<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 256
# coding: utf-8

def popcount(x):
    assert x.bit_length() <= 32
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f


def solve(*args: str) -> str:
    n = int(args[0])
    x = args[1]

    ret = []
    x_dec = int(x, 2)
    x_count = x.count('1')

    x_mod_set = x_dec % (x_count+1)
    xor_set = 1 % (x_count+1)
    if 1 < x_count:
        x_mod_reset = x_dec % (x_count-1)
        xor_reset = 1 % (x_count-1)

    A = [0]
    for i in range(1, x_count+2):
        A.append(A[i % popcount(i)]+1)

    for i in range(n):
        bitcount = x_count + (1 if x[-1-i] == '0' else -1)
        if bitcount == 0:
            ret.append(str(0))
            continue

        m = x_mod_set + xor_set if x[-1-i] == '0' else x_mod_reset - xor_reset
        m %= bitcount

        ret.append(str(1+A[m]))

        xor_set = (xor_set << 1) % (x_count+1)
        if 1 < x_count:
            xor_reset = (xor_reset << 1) % (x_count-1)

    return '\n'.join(ret[::-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Measured memory_bytes: 26304
s = input()
r = 100;
for x in range(97, 97+26):
  cnt = 0
  m = 0
  for c in s:
    if c == chr(x):
      m = max(m, cnt)
      cnt = 0
    else:
      cnt += 1
  m = max(m, cnt)
  r = min(r, m)
print(r)

Measured memory_bytes: 2940
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K = map(int,readline().split())
S = read().rstrip().decode('utf-8')

if K > 30:
    K = 30

SS = S + S[::-1]

if K == 1:
    answer = min(SS[i:i+N] for i in range(N+1))
    print(answer)
    exit()

min_ch = min(S)
run_len = [0] * len(SS)
for i,x in enumerate(SS):
    if x == min_ch:
        run_len[i] = run_len[i-1] + 1

max_len = max(run_len)
I = [i for i,x in enumerate(run_len[N-1:],N-1) if x == max_len]

if (max_len << (K-1)) >= N:
    answer = min_ch * N
    print(answer)
    exit()

L = max_len << (K-1)
cand = []
for i in I:
    T = SS[i-N+1:i+1]
    cand.append(T[-max_len-1:-max_len-(N-L)-1:-1])

answer = min_ch * L + min(cand)
print(answer)

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

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

	ll n;cin >> n;
	vector<ll> v(n);

	ll sum = 0;
	REP(i, n){
		cin >> v[i];
		sum += v[i];
	}

	vector<ll> g(n);
	g[0] = sum;
	for(int i = 1;i < n;i += 2){
		g[0] -= 2 * v[i];
	}

	for(int i = 1;i < n;i++){
		g[i] = 2 * (v[i-1] - (g[i-1] / 2));
	}

	REP(i, n){
		cout << g[i] << " ";
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 2944
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    ll a,b,c,d; cin>>a>>b>>c>>d;
    ll aa=(a+d-1)/d;
    ll bb=(c+b-1)/b;
    if(aa>=bb)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}





Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
int main()
{
  int N, A, B;
  cin >> N >> A >> B;
  int sum = 0;
  for (int i = 1; i <= N; i++)
  {
    string tmp = to_string(i);
    int t = 0;
    rep(j, tmp.size())
    {
      t += tmp.at(j)-48;
    }
    //cout << t << endl;
    if (t >= A && t <= B)
    {
      sum += i;
    }
  }
  cout << sum << endl;
  return 0;
}

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

int fib(int n);

vector<long long> fib_n(100, 0);

int main() {
  int n;
  cin >> n;
  cout << fib(n) << endl;
  return 0;
}

int fib(int n) {
  if (fib_n[0] == 0) {

    fib_n[0] = 1;
    fib_n[1] = 1;
  }
  if (n == 0) {
    return fib_n[0];
  }
  if (n == 1) {
    return fib_n[1];
  }
  if (fib_n[n] == 0) {
    fib_n[n] = fib(n - 1) + fib(n - 2);
  }
  return fib_n[n];
}



Measured memory_bytes: 3092
n = int(input())
s_list = [input() for _ in range(n)]

def str_2_set(string):
    s = set()
    used_dict = {}

    for l in string:
        if l not in used_dict:
            used_dict[l] = 1
            number = 1
        else:
            used_dict[l] += 1
            number = used_dict[l]
        l = l + str(number)
        s.add(l)
    return s

set_list = [str_2_set(s) for s in s_list]
for i,s in enumerate(set_list):
    if i == 0:
        return_set = s
    else:
        return_set = return_set & s

return_list = []
while len(return_set) > 0:
    num = return_set.pop()[0]
    return_list.append(num)

return_list.sort()
print(''.join(return_list))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 998244353;
#define REP(i, n) for (long long i = 0; i < (n); i++)

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}

long long moddiv(long long a, long long b) { return (a * modpow(b, mod - 2)) % mod; }

long long nCkmod(long long n, long long k) {
    long long denomi = 1;
    REP(i, n) {
        denomi *= (i + 1);
        denomi %= mod;
    }
    long long numera = 1;
    for (int i = n - k; i > 0; i--) {
        numera *= i;
        numera %= mod;
    }
    REP(i, k) {
        numera *= (i + 1);
        numera %= mod;
    }
    return moddiv(denomi, numera);
}

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
array<int, 101> factoring(int x) {
    array<int, 101> ret{};
    for (int i = 2; x >= i * i; i++) {
        while (x % i == 0) {
            ret[i]++;
            x /= i;
        }
    }
    if (x > 1) ret[x]++;
    return ret;
}
long long n, a, b, c, d, t;
map<long long, long long> memo;
long long func(long long x) {
    if (memo.count(x)) {
        return memo[x];
    }
    memo[x] = min({func(x / 2) + d * (x % 2) + a, func(x / 3) + d * (x % 3) + b, func(x / 5) + d * (x % 5) + c,
                   func((x + 1) / 2) + d * (x % 2) + a, func((x + 2) / 3) + d * (3 - x % 3) + b,
                   func((x + 4) / 5) + d * (5 - x % 5) + c});
    if (1ll * 1e12 / x > d) {
        memo[x] = min(memo[x], x * d);
    }
    return memo[x];
}
signed main() {
    cin >> t;
    REP(_, t) {
        memo.clear();
        cin >> n >> a >> b >> c >> d;
        memo[0] = 0;
        memo[1] = d;
        cout << func(n) << endl;
    }
}

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

long long dp[100005][13] = { 0 };


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

	dp[0][0] = 1;
	for (int i = 0; i < s.size(); i++) {
		int c = (s[i] == '?' ? -1 : s[i] - '0');
		for (int j = 0; j < 10; j++) {
			if (c == -1 || c == j) {
				for (int k = 0; k < 13; k++) {
					dp[i + 1][(k * 10 + j) % 13] += dp[i][k];
				}
			}
		}
		for (int j = 0; j < 13; j++) {
			dp[i + 1][j] %= 1000000007;
		}
	}
	cout << dp[s.size()][5] << endl;

	return 0;
}

Measured memory_bytes: 10624
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string N;
    cin >> N;
    
    long long ans=0;
    long long len=N.size();
    
    for (int i=0;i<len;i++) {
        ans+=N[i]-'0';
    }
    
    if(ans%9==0) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3736
// Author: Jinhai Chen
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;

const int maxn = 1e5+5;
int a[maxn],b[maxn];
int d[maxn];
int n,m;
int main() {
#ifndef ONLINE_JUDGE	

#endif
	while(scanf("%d",&n)!=EOF) {
		m=0;
		for(int i=0;i<n;i++) scanf("%d",&a[i]);
		for(int i=0;i<n;i++) scanf("%d",&b[i]);
		ll own=0,ans=0;
		for(int i=0;i<n;i++) {
			if(a[i]<b[i]) own+= b[i]-a[i],ans++;
			else {
				d[m++]=a[i]-b[i];
			}
		}
		sort(d,d+m);
		reverse(d,d+m);
		for(int i=0;i<m;i++) {
			if(own<=0) break;
			own-=d[i];
			ans++;
		}
		if(own>0) ans=-1;
		cout<<ans<<endl;
	}
	return 0;
}














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

using i8  = int8_t;using i16 = int16_t;using i32 = int32_t;using i64 = int64_t;using u8  = uint8_t;using u16 = uint16_t;using u32 = uint32_t;using u64 = uint64_t;using f32 = float;using f64 = double;
using vi32 = vector<i32>;using vi64 = vector<i64>;using vvi32 = vector<vi32>;using vvi64 = vector<vi64>;using pi32 = pair<i32,i32>;using pi64 = pair<i64,i64>;

#define FOR(i,a,b) for(i64 i=(a), i##_len=(b); i<i##_len; ++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,x) for(i64 i=1;i<=(i64)(x);i++)
#define RREPS(i,x) for(i64 i=((i64)(x));i>0;i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define SZ(x) ((i64)(x).size())
#define CLR(ar,val) memset(ar, val, sizeof(ar))
#define cauto const auto&
#define pb push_back
#define mp make_pair
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

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

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


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

bool isPrime(i64 x) {
    if (x == 2) return true;
    if (x < 2 || x % 2 == 0) return false;
    i64 i = 3;
    while (i * i <= x) {
        if (x % i == 0) return false;
        i += 2;
    }
    return true;
}

void Main() {
    //-------------------------------------------------------------------------
    i64 n,ans=0; cin >> n;
    REP(i,n) {
        i64 a; cin >> a;
        if (isPrime(a)) ans++; 
    }
    cout << ans << endl;
    //-------------------------------------------------------------------------
}


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

int main(){
  string temp;
  int temp2[3][110], temp3[3][110], temp4[3][110], zikantai[110] = {}, zikantai2[110] = {};
  int n, m, kkk, k, ans = 0;

  cin>>kkk;

  for(int i = 0; i < kkk; i++){
    cin>>temp;
    temp2[0][i] = temp[0] * 36000 + temp[1] * 3600  + temp[3] * 60 + temp[4];
    temp2[1][i] = temp[6] * 36000 + temp[7] * 3600  + temp[9] * 60 + temp[10];
  }

  cin>>n;
  for(int i = 0; i < n; i++){
    cin>>k;
    for(int j = 0; j < k; j++){
      cin>>temp;
      temp3[0][i] = temp[0] * 36000 + temp[1] * 3600  + temp[3] * 60 + temp[4];
      temp3[1][i] = temp[6] * 36000 + temp[7] * 3600  + temp[9] * 60 + temp[10];

      for(int l = 0; l < kkk; l++){
	if(temp3[0][i] <= temp2[0][l] && temp3[1][i] >= temp2[1][l]){
	  zikantai[l]++;
	}
      }
      
    }
  }
  
  cin>>m;
  for(int i = 0; i < m; i++){
    cin>>k;
    for(int j = 0; j < k; j++){
      cin>>temp;
      temp4[0][i] = temp[0] * 36000 + temp[1] * 3600  + temp[3] * 60 + temp[4];
      temp4[1][i] = temp[6] * 36000 + temp[7] * 3600  + temp[9] * 60 + temp[10];

      
      for(int l = 0; l < kkk; l++){
	 if(temp4[0][i] <= temp2[0][l] && temp4[1][i] >= temp2[1][l]){
	  zikantai2[l]++;
	}
      }
    }
  }


  for(int i = 0; i < kkk; i++){
    ans += min(zikantai[i], zikantai2[i]);
  }
  

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



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

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

    int a, b, c;
    cin >> a >> b >> c;
    
    string ans = "No";
    
    if((a <=c && c <= b) || (b <= c && c <= a)){
        ans = "Yes";
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256