akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mt make_tuple
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector <long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector <long long int, long long int> 
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

ll add(ll x, ll y) {ll res=x+y; return(res>=MOD?res-MOD:res);}
ll mul(ll x, ll y) {ll res=x*y; return(res>=MOD?res%MOD:res);}
ll sub(ll x, ll y) {ll res=x-y; return(res<0?res+MOD:res);}
ll lcm(ll x, ll y) {ll res=(x*y)/__gcd(x,y); return res;}
ll power(ll x, ll y) {ll res=1; x%=MOD; while(y){if(y&1)res=mul(res,x); y>>=1; x=mul(x,x);} return res;}
const int inf = 1e9 + 5;
const ll inf64 = 1e18 + 5;

bool cmpr(pii p1, pii p2)
{
	if(p1.s == p2.s)
	return(p1.f < p2.f);
	return(p1.s < p2.s);
}
int main()
{
	boost;
	int n, i, j, x, l;
	cin >> n;
	vpii v;
	fo(i, 0, n){
		cin >> x >> l;
		v.pb({x - l, x + l - 1}); 
	}
	sort(all(v), cmpr);
	int ans = 1, curr = v[0].s;
	fo(i, 1, n){
		if(curr < v[i].f){
			ans++;
			curr = v[i].s;
		}
	}
	cout << ans;
}


Measured memory_bytes: 1400
#include<bits/stdc++.h>
#define IOFAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define ll long long
#define fo(i,n) for(int i=0;i<n;i++)

#define pb push_back  


int main(){
    int s,w;
    cin>>s>>w;
    if(w>=s){
        cout<<"unsafe"<<endl;
    }
    else{
        cout<<"safe"<<endl;
    }

}

Measured memory_bytes: 3572
#include <iostream>
#include <climits>
#include <stack>
#include <queue>
#include <string>
#include <utility>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int INF = 1<<29;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする

long long int i,j;

long long int de(long long int a){
	for(int k=1;k<=100;k++){
		a=a/10;
		if(a==0){
			return k;
			break;
		}
	}
}



int main(){
	long long int n;
	long long int ans=INF;
	cin>>n;
	for(i=0;i<n;i++){
		if(i*i>n)break;
	}
	i-=1;
	for(j=1;j<=i;j++){
		if(n%j==0){
			ans = min(ans,de(n/j));
		}
	}
	//output
	if(n==1)ans=1;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
// 5_abc133_e
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define INF (1e16)
#define MOD (1000000007)
typedef long long ll;

const int MAX = 100001;

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

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

vector<vector<int>> g;
vector<int> color;
ll n, k;
ll ans = 0;

void dfs(int nd){
    color[nd] = 1;
    int deg = g[nd].size();
    ans = ans * PERM(k - 2, deg - 1) % MOD;
    rep(i, deg){
        if(color[g[nd][i]] == 0) dfs(g[nd][i]);
    }
}

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

    COMinit();
    cin >> n >> k;
    g.resize(n + 1);
    color.resize(n + 1);
    rep1(i, n){
        color[i] = 0;
    }
    rep(i, n - 1){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    ans = k % MOD;
    color[1] = 1;
    ans = ans * PERM(k - 1, g[1].size()) % MOD;
    rep(i, g[1].size()){
        if(color[g[1][i]] == 0) dfs(g[1][i]);
    }

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


Measured memory_bytes: 10752
from collections import deque

s = input()

ns = ""

for s_i in s:
    if s_i != "x":
        ns += s_i

if ns != ns[::-1]:
    print(-1)
    exit()

if ns == "":
    print(0)
    exit()

if len(ns) % 2 == 1:
    cnt = -1
    for i,s_i in enumerate(s):
        if s_i != "x":
            cnt += 1
        if cnt == len(ns)//2:
            note = i
            break
    left = deque(s[:note][::-1] + "@")
    right = deque(s[note+1:] + "@")
else:
    cnt = -1
    f = 1
    for i,s_i in enumerate(s):
        if s_i != "x":
            cnt += 1
        if cnt == len(ns)//2 - 1 and f:
            l = i
            f = 0
        if cnt == len(ns)//2:
            r = i
            break
    left = deque(s[:l][::-1] + "@")
    right = deque(s[r+1:] + "@")

ans = 0

while left or right:
    if left[0] == right[0]:
        left.popleft()
        right.popleft()
    elif left[0] == "x":
        left.popleft()
        ans += 1
    elif right[0] == "x":
        right.popleft()
        ans += 1

print(ans)

Measured memory_bytes: 4340
import java.util.Scanner;

public class Main {

	static int MOD = 1000000007;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		long xSum = 0;
		long ySum = 0;
		for (int i=0;i<n;i++) {
			xSum = (xSum + (2*i-n+1)*sc.nextLong())%MOD;
		}
		for (int i=0;i<m;i++) {
			ySum = (ySum + (2*i-m+1)*sc.nextLong())%MOD;
		}

		System.out.println((((xSum * ySum) % MOD)+MOD)%MOD);
	}

}


Measured memory_bytes: 64716
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
using ll = long long;

int main(){
    int n,m,c,ans;cin>>n>>m>>c;
    vector<int>b(m);
    rep0(i,m){
        cin>>b[i];
    }
    vector<vector<int>>a(n,vector<int>(m));
    rep0(i,n){
        rep0(j,m){
            cin>>a[i][j];
        }
    }
    rep0(i,n){
        int sum=0;
        rep0(j,m){
            sum+=b[j]*a[i][j];
        }
        if(sum+c>0){
            ans++;
        }
    }
    cout << ans <<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <inttypes.h>

#define N_MAX 300000
#define M_MAX 300000
#define SCORE_MAX 1000000

int N;
uint64_t a[N_MAX];
int M;
uint64_t b[M_MAX];
uint64_t c[M_MAX];

uint64_t score[SCORE_MAX + 1];

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%"SCNu64, &a[i]) != 1) return 1;
	}
	if (scanf("%d", &M) != 1) return 1;
	for (i = 0; i < M; i++) {
		if (scanf("%"SCNu64, &b[i]) != 1) return 1;
	}
	for (i = 0; i < M; i++) {
		if (scanf("%"SCNu64, &c[i]) != 1) return 1;
	}

	for (i = 0; i < N; i++) {
		score[a[i]] += a[i];
	}
	for (i = 1; i <= SCORE_MAX; i++) {
		score[i] += score[i - 1];
	}

	for (i = 0; i < M; i++) {
		puts(c[i] <= score[b[i]] ? "Yes" : "No");
	}

	return 0;
}

Measured memory_bytes: 15336
from queue import Queue as que
q=que()
n,m=map(int,input().split())
e=[[] for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    e[a-1].append(s-1);e[s-1].append(a-1)
table=[0]*(n)
table[0]=1
ok=0
q.put(0)
while not q.empty():
    now=q.get()
    for to in e[now]:
        if table[to]==0:
            table[to]=now+1
            q.put(to)
            ok+=1
if n-1==ok:
    print("Yes",*table[1:],sep="\n")
else:print("No")

Measured memory_bytes: 39348
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in));
		String str="";

		str=bfr.readLine();
		String[] wake=str.split(" ");
		int a=Integer.parseInt(wake[0]);
		int b=Integer.parseInt(wake[1]);
		int c=Integer.parseInt(wake[2]);

		int baisu=b*10+c;

		if(baisu%4==0) {
			System.out.println("YES");
		}
		else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 21204
K = int(input())
A = [int(_) for _ in input().split()]

A.reverse()
maximum = 2
minimum = 2
able = True

for i in range(K):
  maximum = (maximum // A[i]) * A[i] + A[i] - 1
  minimum = ((minimum - 1) // A[i] + 1) * A[i]
  if minimum > maximum:
    able = False
    break

if able:
  print(str(minimum) + ' ' + str(maximum))
else:
  print(-1)

Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll a,b,c,d,e,i,j,k,x,y,l=0,lt=0;
cin>>a>>b>>c>>x>>y;
if(c*2<a+b)
{
k=min(x,y);
  l=l+(k)*2*c;
l=l+(a*(x-k))+(b*(y-k));
lt=max(x,y)*2*c;
cout<<min(l,lt)<<endl;
}
else
{
l=a*x+b*y;
cout<<l<<endl;
}


}

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = INT_MAX;

int main() {
  int N; cin >> N;
  vector<int> B(N + 1);
  REP(i, 1, N) cin >> B[i];
  B[0] = B[N] = inf;
  int ans = 0;
  rep(i, N) ans += min(B[i], B[i + 1]);
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
using namespace std;
#define int long long int
//#define double long double
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> new_data_set;
bool isprime(int n)
	{
    	if(n==1) return true;
    	for(int i = 2;i*i<=n;i++){
    		if(n%i==0) return false;
		}
		return true;
	}
int lcm(int a,int b){
	return (a*b)/__gcd(a,b);
}
int gcd(int a, int b) 
{ 
    if (b == 0){
    	return a;
	} 
    return gcd(b, a % b);  
      
} 
unsigned int factorial(unsigned int n) 
{ 
    if (n == 0) 
    return 1; 
    return n * factorial(n - 1); 
} 
const int inf=1e17+7;
int dsu[1000001],s[100005];
void init(int n,int m){
	for(int i=1;i<=n;i++){
		dsu[i]=i;
		s[i]=1;
	}
}
int root(int x){
	while(dsu[x]!=x){
		x = dsu[x];
	}
	return x;
}
void uni(int x,int y){
	int p = root(x);
	int q = root(y);
	if(p==q){
		return;
	}
	else{
		if(s[p]<s[q]){
			s[q]+=s[p];
			dsu[p] = q;
		}
		else{
			s[p]+=s[q];
			dsu[q] = p;
		}
	}
}
int power(int x, unsigned int y)  
{  
    int res = 1;
    x = x ; 
    if (x == 0) return 0;  
    while (y > 0)  
    {  
        if (y & 1)  
            res = (res*x);   
        y = y>>1;  
        x = (x*x);  
    }  
    return res;  
}
bool visited[100001]={false};
vector<int>graph[100001];
void dfs(int x){
	if(visited[x])return;
	visited[x]=true;
	for(auto &child:graph[x]){
		if(!visited[child]){
			dfs(child);	
		}
		//dp[x]=max(dp[x],dp[child]+1);
	}
}
signed main(){
	FAST
	int n,m;
	cin>>n>>m;
	int dp[n+1][m+1];
	for(int i=0;i<=n;i++)dp[i][0]=0;
	for(int i=0;i<=m;i++)dp[0][i]=0;
	char arr[n][m];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>arr[i][j];
			if(arr[i][j]=='#'){
				dp[i+1][j+1]=0;
			}
			else{
				dp[i+1][j+1]=1;
			}
		}
	}
//	for(int i=0;i<=n;i++){
//		for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";
//		cout<<endl;
//	}
	dp[1][1]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(dp[i][j]!=0){
				dp[i][j]=(dp[i-1][j]%mod+dp[i][j-1]%mod)%mod;
				if(i==1 && j==1){
					dp[i][j]=1;
				}
			}
			//cout<<dp[i][j]<<" ";	
		}
		//cout<<endl;
	}
//	for(int i=0;i<=n;i++){
//		for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";
//		cout<<endl;
//	}
	cout<<dp[n][m];
}

Measured memory_bytes: 13184
#include <stdio.h>

#define MAX 46

int fibonacci(int);

int F[MAX];

int main(){
  int n, f, a;

  scanf("%d",&n);
  F[0] = F[1] = 1;
  for(a = 2; a <= n; a++) F[n] = -1;
  f = fibonacci(n);

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

int fibonacci(int n){
  if(n == 0) return F[n] = 1;
  else if(n == 1) return F[n] = 1;
  else return F[n] = fibonacci(n-1) + F[n-2];
}



Measured memory_bytes: 2112
D,N = map(int,input().split())

if D==0:
    if N == 100:
        print(101)
    else:
        print(N)
if D==1:
    if N == 100:
        print(10100)
    else:
        print(N*100)

if D == 2:
    if N == 100:
        print(1010000)
    else:
        print(N*10000)



Measured memory_bytes: 9088
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
p = [0] + LI()

g = [i for i in range(N+1)]
g_num = [1 for _ in range(N+1)]

def find(x):
    if g[x] == x : return x
    g[x] = find(g[x])
    return g[x]

def union(x,y):
    if find(x) == find(y): return
    if g_num[g[x]] < g_num[g[y]]: x,y = y,x
    g_num[g[x]] += g_num[g[y]]
    g[g[y]] = g[x]

for _ in range(M):
    x,y = LI()
    union(x,y)

ans = 0
for i in range(1,N+1): ans += (find(i)==find(p[i]))
print(ans)

Measured memory_bytes: 87596
while line = gets
  n = line.chomp.to_i
  count = 0
    10.times do | a |
      10.times do | b | 
        10.times do | c |
          10.times do | d |
            if a + b + c + d == n
               count = count + 1
            end
          end
        end
      end 
    end
    p count
end


Measured memory_bytes: 6868
#include <bits/stdc++.h>
using namespace std;
long long n,i,a,b,c;
int main(){
  cin>>a>>b>>c>>n;
  i+=min(n,a);
  n-=(a+b);
  if(n>0)i+=-1*min(c,n);
  cout<<i;
}

Measured memory_bytes: 3592
# input
n = int(input())
A = [[-1] * n for i in range(n)]
for _ in range(n):
    line = list(map(int, input().split()))
    u = line.pop(0)
    k = line.pop(0)
    for i in range(k):
        v = line.pop(0)
        c = line.pop(0)
        A[u][v] = c
    
# 変数定義
inf = 100 * 100000 + 1
M = A.copy()
M = [[a if a > -1 else inf for a in line] for line in M]
d = [inf] * n
V = set([i for i in range(n)]) #nodeの一覧
T = set() #探索済みnodeの一覧

# 探索
start = 0
target = start
d[target] = 0
T.add(target)
while V != T:
    for i in (V - T):
        if d[target] + M[target][i] < d[i]:
            d[i] = d[target] + M[target][i]

    min_wheght = min([d[i] for i in (V - T)])
    min_path = [i for i in (V - T) if d[i] == min_wheght][0]
    target = min_path
    T.add(target)

# 出力
for i in range(n):
    print(f"{i} {d[i]}")


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

int main(){
 int sum;
 string x;

 while(1){
  cin >> x;
  if(x=="0")break;
  sum=0;
  for(int i=0;i<x.size();i++){
   sum+=x[i]-'0';
  }
  cout << sum << endl;
 }
 return 0;
}

Measured memory_bytes: 3152
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_N 366
#define MAX_C 9
#define MAX_R 2402
 
struct State{
    int d,c,r[4];
    State(int d,int c,int r[4]) : d(d),c(c) {
	for(int i = 0 ; i < 4 ; i++){
	    this->r[i] = r[i];
	}
    }
};
 
int N,arr[MAX_N];
bool visited[MAX_N][MAX_C][MAX_R];
const int d[5] = {-1,-3,1,3,0};
 
int next(int c,int dir){
    if(c%3 == 0 && dir == 0) return -1;
    if(c/3 == 0 && dir == 1) return -1;
    if(c%3 == 2 && dir == 2) return -1;
    if(c/3 == 2 && dir == 3) return -1;
    return c + d[dir];
}
 
bool check(int d,int c){
    c += c/3;
    for(int i = 0 ; i < 16 ; i++){
	if((arr[d] >> i & 1) && i == c) return true;
	if((arr[d] >> i & 1) && i == c+1) return true;
	if((arr[d] >> i & 1) && i == c+4) return true;
	if((arr[d] >> i & 1) && i == c+5) return true;
    }
    return false;
}
 
void calc(int c,int *r){
    if(c == 0){ r[0] = 0; }else{ r[0]++; }
    if(c == 2){ r[1] = 0; }else{ r[1]++; }
    if(c == 6){ r[2] = 0; }else{ r[2]++; }
    if(c == 8){ r[3] = 0; }else{ r[3]++; }
}
 
int getValue(int *r){
    int res = 0;
    for(int i = 0 ; i < 4 ; i++){
	res *= 7; res += r[i];
    }
    return res;
}
 
int solve(){
    int r[4] = {0}; calc(4,r);
    memset(visited,false,sizeof(visited));
    visited[0][4][getValue(r)] = true;
    queue<State> Q;
    Q.push(State(0,4,r));
    while(!Q.empty()){
	State s = Q.front(); Q.pop();
	int day = s.d,cloud = s.c;
	if(check(day,cloud)) continue;
	if(day == N-1) return 1;
	for(int i = 0 ; i < 5 ; i++){
	    int cc = cloud,nr[4];
	    for(int j = 0 ; j < 2 ; j++){
		int nc = next(cc,i);
		if(nc == -1) break;
		memcpy(nr,s.r,sizeof(nr)); calc(nc,nr);
		if(*max_element(nr,nr+4) >= 7){
		    cc = nc;
		    continue;
		}
		int value = getValue(nr);
		if(!visited[day+1][nc][value]){
		    visited[day+1][nc][value] = true;
		    Q.push(State(day+1,nc,nr));
		}
		cc = nc;
		if(i == 4) break;
	    }
	}
    }
    return 0;
}
 
int main(){
    while(cin >> N,N){
	for(int i = 0 ; i < N ; i++){
	    int x,bit = 0;
	    for(int j = 0 ; j < 16 ; j++){
		cin >> x;
		if(x == 1){ bit |= (1<<j); }
	    }
	    arr[i] = bit;
	}
	cout << solve() << endl;
    }
    return 0;
}

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

int main()
{
    int n,x;
    cin>>n;
    set<int,greater<int>>s;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        s.insert(x);
    }
    if(n==s.size())
        cout<<"YES"<<"\n";
    else
        cout<<"NO"<<"\n";
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define INF 1000000000
#define MOD 1000000007

void solve() {
    int n;
    cin >> n;
    vi a(n+1);
    rep(i,1,n+1) {
        cin >> a[i];
    }
    int ans = 1, i = 1;
    set<int> s{1};
    while (a[i] != 2) {
        if (i == a[i]) {
            cout << -1;
            return;
        }
        i = a[i];
        if (i != 2 && s.find(i) != s.end()) {
            cout << -1;
            return;
        }
        s.emplace(i);
        ++ans;
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}



Measured memory_bytes: 8096
#include "bits/stdc++.h"
using namespace std;
#define int long long

signed main(){
	int N, K, L, R; cin >> N >> K >> L >> R;
	vector<int> a(N);
	int k2 = N/2;
	for(int i = 0; i < k2; i++) cin >> a[i];
	vector<int > p[N];
	for(int i = 0; i < (1 << k2); i++){
		int counter = 0, s = 0;
		for(int j = 0;j < k2; j++){
			if(i & (1 << j)) counter++, s += a[j];
		}
		p[counter].push_back(s);
	}
	for(int i = 0; i < N; i++) sort(p[i].begin(), p[i].end());
	
	int ans = 0;
	k2 = N - k2;
	for(int i = 0; i < k2; i++) cin >> a[i];
	for(int i = 0; i < (1 << k2); i++){
		int s = 0, counter = 0;
		for(int j = 0; j < k2; j++){
			if(i & (1 << j)) counter++, s += a[j];
		}
		if(K < counter) continue;
		ans += upper_bound(p[K - counter].begin(), p[K - counter].end(), R - s) - lower_bound(p[K - counter].begin(), p[K - counter].end(), L - s);
	}
	cout << ans << endl;
}


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

int main() {
	int n,k;
	cin >> n >> k;
	int dp[n];
	int val[n];
	for(int i = 0;i < n;i++)
	cin >> val[i];
	dp[0] = 0;
	dp[1] = abs(val[0] - val[1]);
	for(int i = 2;i < n;i++)
	{
		dp[i] = INT_MAX;
		for(int j = i-1; j >= max(0,i-k);j--)
		dp[i] = min(dp[i],dp[j] + abs(val[i] - val[j]));
	}
	cout << dp[n-1] << "\n";
	return 0;
}

Measured memory_bytes: 1152
import bisect
n = int(input())
#nを受け取り、nを素因数分解した形で返す
if n == 1:
    print(0)
    exit()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
acc = [0 for i in range(1000)]
acc[1] = 1
for i in range(2,1000):
    acc[i] = acc[i-1] + i
array = factorization(n)
ans = 0
for num, count in array:
    index = bisect.bisect_right(acc, count)
    ans += (index - 1)
print(ans)


Measured memory_bytes: 9512
import java.util.*;
// i hate myself
public class Main{
	public static long cdiv(long a, long b)
	{
		if(a <= 0) return 0;
		return (a/b)+(a%b==0 ? 0 : 1);
	}
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long k = in.nextLong();
        long[] a = new long[n];
        long[] b = new long[n];
        long max_a = -1L;
        for( int i = 0; i < n; i++ ) {
            a[i] = in.nextLong();
            b[i] = in.nextLong();
            max_a = Math.max(max_a, a[i]);
        }
        long ct = 0L;
        Arrays.sort(b);
        for( int i = n-1; i >= 0 && k > 0; i-- ) {
            if(b[i] > max_a) {k -= b[i]; ct += 1L;}
            else break;
        }
        ct += cdiv(k,max_a);
        System.out.println(ct);
    }
}

Measured memory_bytes: 82208
N = int(input())
A = list(map(int,input().split()))
ans = 1
if 0 in A:
    print(0)
    exit()
for i in range(N):
    if ans <= 10**18:
        ans *= A[i]
    else:
        ans = -1
        break
if ans > 10**18:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 84812
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define showmap(is, js, x) {rep(i, is){rep(j, js){cout << x[i][j] << " ";}cout << endl;}}
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> llP;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}

/*
setwise coprimeのはんてい　＝＞愚直にやる
pairwise coprimeのはんてい　＝＞　setで判定


*/

template<class X> void factorization(X input, set<X>& Pnumber){
    for(X i = 2; i*i <= input; i++)
    {
        if (input % i == 0){
            while (input % i == 0){
                input /= i;
                Pnumber.insert(i);
            }
        }
    }
    if (input != 1) Pnumber.insert(input);
}



int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n){ cin >> a[i]; }

    bool setc = false;
    ll s1 = a[0];
    for (int i = 1; i < n; i++)
    {
        s1 = gcd(s1, a[i]);
    }
    if (s1 == 1) setc = true;

    set<int> yakusu;
    bool pairc = true;
    rep(i, n){
        set<int> tmp;
        factorization(a[i], tmp);

        for (auto t: tmp){
            if (yakusu.find(t) == yakusu.end()){
                yakusu.insert(t);
            } else {
                pairc = false;
                break;
            }
        }
    }

    if (pairc) cout << "pairwise coprime" << endl;
    else if (setc) cout << "setwise coprime" << endl;
    else cout << "not coprime" << endl;
}



Measured memory_bytes: 10692
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repd(i, n) for (int i = n; i >= 1; i--)
#define mod 1000000007
#define MOD 998244353
#define inf 1e20
typedef long long int ll;
typedef pair<ll, ll> p;


int main() {
	string s;
	cin >> s;
	if (s[0] == *"9"||s[1] == *"9") {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

//Ctrl+Aを使わない

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

n,k = map(int,input().split())
a = list(map(int,input().split()))
cnt1 = 0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i] > a[j]:
      cnt1 += 1
cnt1 = cnt1*k

cnt2 = 0
for l in range(n):
  for m in range(n):
    if a[l] > a[m]:
      cnt2 += 1
cnt2 = cnt2*k*(k-1)//2

cnt = cnt1 + cnt2

x = 10**9 + 7
print(int(cnt%x))

Measured memory_bytes: 3188
#include<iostream>
#include<stack>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
  stack<int> S1;
  stack<pair<int, int> > S2;
  char ch;
  int sum = 0;
  for ( int i = 0; cin >> ch; i++ ) {
    if ( ch == '\\' ) S1.push(i);
    else if ( ch == '/' && S1.size() > 0 ) {
      int j = S1.top(); S1.pop();
      sum += i - j;
      int a = i - j;
      while ( S2.size() > 0 && S2.top().first > j ) {
        a += S2.top().second; S2.pop();
      }
      S2.push(make_pair(j, a));
    }
  }

  vector<int> ans;
  while ( S2.size() > 0 ) { ans.push_back(S2.top().second); S2.pop(); }
  reverse(ans.begin(), ans.end());
  cout << sum << endl;
  cout << ans.size();
  for ( int i = 0; i < ans.size(); i++ ) {
    cout << " ";
    cout << ans[i];
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 3212
#include<cstdio>
using namespace std;
int main(void)
{
	int s,s1,s2,s3,i,j,x,y,a,b;
	scanf("%d",&s);
	scanf("%d",&s1);
	scanf("%d",&s2);
	scanf("%d",&s3);
	a=s+s1+s2+s3;
	if(a>=60){
		x=a/60;
		y=a%60;
		printf("%d\n%d\n",x,y);
	}
	else{
		printf("%d\n",a);
	}
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <cctype>
#include <cmath>
#include <cstring>
#include <climits>
#include <complex>
#include <set>
#include <deque>
#define DEBUG(x) cerr<<"line:"<<__LINE__<<", "<<#x" == "<<(x)<<endl;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(it,s) for(__typeof(s.begin()) it=s.begin();it!=s.end();it++)
#define fst first
#define snd second
#define ALL(a) a.begin(),a.end()
#define RI(x) scanf("%d",&(x))
#define RII(x,y) scanf("%d%d",&(x),&(y))
#define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define DRI(x) int (x);scanf("%d",&(x))
#define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y))
#define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d%d",&(x),&(y),&(z))
#define MS0(a) memset((a),0,sizeof((a)))
#define MS1(a) memset((a),-1,sizeof((a)))
#define MS(a,b) memset((a),(b),sizeof((a)))
using namespace std;

typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<vi> vvi;

LL pow(LL a, LL b, LL MOD) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

#define INF (int)1e9
#define EPS (1.0e-8)
// ------------------

const int maxn = 1000;
int a[maxn];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
#endif
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
    sort(a, a + n);
    for (int i = n-1; i >= n-1-(m-1); i--) {
        if (a[i] * 1.0 < (sum*1.0)/(4*m)) {
            // cout <<"a = " << a[i] << endl;
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int a[1000005];
int n;
int main(){
    while(~scanf("%d",&n)){
        long long sum=0;
        map<long long,int>s;
        long long ans=0;
        s[0]=1;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            ans+=a[i];
            sum+=s[ans];
            s[ans]++;
        }
        cout<<sum<<endl;
    }
    return 0;
}


Measured memory_bytes: 13568
/*jai_ganeshdeva*/

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pu push  //  adds the value to the last of the queue 
#define lld long long int
#define ins insert /// used in set to insert the values 
#define adv advance  /// used to increment the iterator
#define mp make_pair
#define fi first
#define se second
#define all(c) c.begin(),c.end()
#define PI 3.1415926
#define INF (lld)1e18
#define vl  vector<long long int >
#define vpll vector< pair<lld ,lld> >
#define vvl vector<vector<lld> > 
#define pll pair <lld,lld>
lld p1=1e9 + 7,p2=998244353;

void judge(){
    #ifndef ONLINE_JUDGE
    // for getting input from input.
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif
    
}

void fastio(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


long long int modp(lld a,lld p,lld n)
{
    lld d[100];
    lld i,j,k,l;
    if(n==0) return 1;
    for(i=0;n>=1;i++)
    {
        d[i]=n%2;
        n/=2;
    }
    l=i;
    long long int e=1;
    if(d[0]==1) e*=(a%p);
    for(i=1;i<l;i++)
    {
        a*=a;
        a=a%p;
        if(d[i]==1) 
        {
            e*=a;
            e=e%p;
        }
    }
    return e%p;
}
lld modInverse(lld n, lld p) 
{ 
    return modp(n, p, p-2); 
}

// lld fac[500005]; 

// void getfac(lld p)
// {
//     fac[0] = 1; 
//     for (lld i=1 ; i<=500005; i++) 
//         fac[i] = fac[i-1]*i%p; 
// }    

// long long int nCrmodp(lld n, lld r,lld p) 
// { 
//    // Base case 
//    if (r==0) 
//       return 1; 
     
//     return (fac[n]* modInverse(fac[r], p) % p * 
//             modInverse(fac[n-r], p) % p) % p; 
// }


lld l,r,mid,ans=0;
lld n,i,j,k,g,m;
lld x,y,n1,n2,h,z,c;
lld aa=1;
lld ss=1;

void solve()
{ 
    cin>>n;
    vector<lld> v1,v2,v3;
    cin>>x>>y>>z;
    v1.pb(x);
    v2.pb(y);
    v3.pb(z);
    for(i=1;i<n;i++)
    {
        cin>>x>>y>>z;
        v1.pb(max(v2[i-1],v3[i-1])+x);
        v2.pb(max(v1[i-1],v3[i-1])+y);
        v3.pb(max(v2[i-1],v1[i-1])+z);
    }
    cout<<max(v1[n-1] , max(v2[n-1], v3[n-1]));
}

int main()
{
    // judge();
    fastio();
    lld t=1;
    // cin>>t;
    // lld p1 = 1e9 + 7;
    // getfac(p1);
    for(int i=0;i<t;i++)
    {
        // cout<<"Case #"<<i+1<<": ";
        solve();
        cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 5764
m = int(input())
S = list(map(int, input().split(" ")))
n= int(input())
T = list(map(int, input().split(" ")))

cnt = 0
al = []
for s in S:
    for t in T:
        if s == t:

            if t not in al: 

                cnt += 1
            
            al.append(t)
print(cnt)


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

using namespace std;

using ll = long long;
using ld = long double;

using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpll = vector<pll>;
using gr = vector<vll>;
using wgr = vector<vpll>;

#define pb push_back
#define FOR(i, m, n) for (ll i(m); i < n; i++)
#define DWN(i, m, n) for (ll i(m); i >= n; i--)
#define REP(i, n) FOR(i, 0, n)
#define DW(i, n) DWN(i, n, 0)
#define F(n) REP(i, n)
#define FF(n) REP(j, n)
#define D(n) DW(i, n)
#define DD(n) DW(j, n)
struct d_ {
    template<typename T> d_ & operator ,(const T & x) { cerr << ' ' <<  x; return *this;}
    template<typename T> d_ & operator ,(const vector<T> & x) { for(auto x: x) cerr << ' ' <<  x; return *this;}
} d_t;
#define dbg(args ...) { d_t,"|",__LINE__,"|",":",args,"\n"; }
#define EPS (1e-10)
#define INF (1LL<<61)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define all(x) begin(x),end(x)
#define IN(n) ll n;cin >> n;
#define x first
#define y second


int main(void) {
    ios_base::sync_with_stdio(false);
    ll x; cin >> x;
    cout << (x*360)/__gcd(x,360ll)/x << endl;
    return 0;
}


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

bool judge(int P,int n,int k,int W[]){//okでtrueを返す
    int tmp=0,i=0,cnt=1;
    while(i<n){
        if(tmp+W[i]>P){
            if(tmp==0)return false;
            tmp=0;
            cnt++;
        }else{
            tmp+=W[i];
            i++;
        }
    }
    if(cnt<=k)return true;
    return false;
}
int main(){
    int n,k;cin>>n>>k;
    int sum=0,W[n];for(int i=0;i<n;i++){cin>>W[i];sum+=W[i];}
    int P,P_m=0,P_M=sum+1;
    //P_mは絶対out
    //P_Mは絶対ok
    while(P_M>P_m+1){
        P=(P_M+P_m)/2;
        if(judge(P,n,k,W)){
            P_M=P;
        }else{
            P_m=P;
        }
    }
    cout<<P_M<<endl;
    return 0;
}


Measured memory_bytes: 3492
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    B = LI()

    c = collections.Counter()
    for x in A:
        c[x] += 1
    for x in B:
        c[x] += 1
        if c[x] > N:
            print('No')
            return

    s = 0
    for i in range(N):
        if A[i] == B[i]:

            p = bisect.bisect_left(B,B[i]+1,i+1)
            if p > N-1:
                p = s
                s += 1
                while B[i] == B[s]:
                    s+=1

            B[i],B[p] = B[p],B[i]
    print('Yes')
    print(*B,sep=' ')

if __name__ == '__main__':
    main()

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

# define ll long long 
# define VI vector<int>
# define VLL vector<ll>
# define PII pair<int,int> 
#define mp make_pair
#define pb push_back
# define PI acos(-1)
# define double long double
const int MxN = 200005 ; 
# define FOR(i,a,b) for(int i = a ; i < b ; ++i) 
# define RFOR(i,a,b) for(int i = b ; i > )
 
bool fun(const PII &a, const PII &b) {
	if(a.first == b.first) {
		return a.second > b.second ; 
	}

	return a.first < b.first ; 
}

ll dp[10][10] ; 


void solve() {
	int h ,w ; 
	ll c[10][10] ; 
	cin >> h >> w ; 
	FOR(i,0,10) {
		FOR(j,0,10) {
			cin >> c[i][j] ; 
			dp[i][j] = c[i][j] ; 
		}
	}

	FOR(i,0,10) {
		FOR(j,0,10) {
			FOR(k,0,10) {
				dp[i][j] = min(dp[i][j] ,(ll) dp[i][k] +(ll) dp[k][j]) ; 
			}
		}
	}

	FOR(i,0,10) {
		FOR(j,0,10) {
			FOR(k,0,10) {
				dp[i][j] = min(dp[i][j] ,(ll) dp[i][k] +(ll) dp[k][j]) ; 
			}
		}
	}
	FOR(i,0,10) {
		FOR(j,0,10) {
			FOR(k,0,10) {
				dp[i][j] = min(dp[i][j] ,(ll) dp[i][k] +(ll) dp[k][j]) ; 
			}
		}
	}

	int x ; 
	ll ans = 0 ; 
	FOR(i,0,h) {
		FOR(j,0,w) {
			cin >>x ; 
			if(x != -1)
			ans += (ll)dp[x][1] ; 
		}
	}
	cout << ans ;


	
 

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ; 
	
	int  t =1; 
	//cin >> t ; 
	while(t--)
		solve() ; 
	return 0 ; 
}



Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int n,m,a[N],l,r,A;
bool C(int k)
{
	for(int i=1;i<=n-k;i++)
		if(a[2*n-i+1]+a[2*k+i]<m)
			return false;
	return true;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=2*n;i++)
		cin>>a[i];
	sort(a+1,a+2*n+1),r=n;
	while(l<r)
		if(C((l+r)/2))
			r=(l+r)/2;
		else
			l=(l+r)/2+1;
	for(int i=1;i<=l;i++)
		A=max(A,a[i]+a[2*l-i+1]);
	for(int i=1;i<=n-l;i++)
		A=max(A,a[2*n-i+1]+a[2*l+i]-m);
	cout<<A;
	return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>

void gcd(int x, int y) {
    if (x < y) {
        int tmp = y;
        y = x;
        x = tmp;
    }

    while (y>0) {
        int r = x % y;
        x = y;
        y = r;
    }

    printf("%d\n", x);
}

int main() {
    int x, y;

    scanf("%d %d", &x, &y);

    gcd(x, y);

    return 0;
}


Measured memory_bytes: 2760
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,c=0,n,p=0,flag=0,j;
    cin>>n;
    char a[n+2];
    for(i=0; i<n; i++)
    {
        cin>>a[i];
    }
    if(n%2!=0)
    {
        cout<<"No"<<endl;
    }
    else if(n%2==0)
    {
        p=n/2;
        for(i=0,j=p; i<p,j<n; i++, j++)
        {
            if(a[i]==a[j])
            {
                flag=0;
            }
            else
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }

    }

}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace Contest
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            var W = Console.ReadLine().Split().Select(int.Parse);
            int S1 = 0;
            int S2 = W.Sum();
            int ans = W.Sum();
            foreach (var item in W)
            {
                S1 += item;
                S2 -= item;
                ans = Math.Min(ans, Math.Abs(S1 - S2));
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13396
#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))
//-------------------------------------------------------

int N,K;
string S;
vector<int> V;
ll mo=1000000007;
ll group[71][71];
int ML[71];
ll fact[72],factr[72],inv[72];

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);};

map<string,int> M[71];
ll tot;
vector<int> G;

void hoge(vector<int> V,vector<ll> C) {
	vector<int> O=V;
	string T=S;
	int TN=T.size(),VN=V.size();
	vector<int> R(VN,-1);
	
	int x=0,y=0,i;
	FOR(i,TN) if(T[i]=='r' && x<VN) {
		R[x]=i;
		V[x]--;
		x++;
		T[i]='_';
		
	}
	if(x!=VN) return;
	x=0;
	FOR(i,TN) if(T[i]=='b') {
		if(x<VN && V[x] && i>R[x]) {
			V[x]--;
			R[x]=i;
			x++;
			T[i]='_';
		}
	}
	if(x<VN && V[x]) return;
	
	x=0;
	FOR(i,TN) if(T[i]!='_') {
		if(x<VN && V[x] && i>R[x]) {
			V[x]--;
			T[i]='_';
			if(V[x]==0) x++;
		}
	}
	if(x<VN && V[x]) return;
	
	map<int,int> M;
	FORR(c,O) M[c]++;
	
	ll ret=0;
	FOR(x,N+1) {
		int left=N-x-(V.size()-1);
		if(left<0) break;
		(ret+=C[x]*hcomb(V.size()+1,left))%=mo;
	}
	
	(ret*=fact[V.size()])%=mo;
	FORR(m,M) (ret*=factr[m.second])%=mo;
	
	(tot+=ret)%=mo;
}

void dfs(int L,int cur,vector<ll> C) {
	if(cur==0) return;
	// not take cur
	dfs(L,cur-1,C);
	
	if(L>=ML[cur]) {
		G.push_back(cur);
		vector<ll> C2(71);
		for(int x=0;x<=70;x++) if(C[x]) {
			for(int y=ML[cur];x+y<=70;y++) {
				(C2[x+y]+=C[x]*group[cur][y])%=mo;
			}
		}
		
		hoge(G,C2);
		dfs(L-(ML[cur]+1),cur,C2);
		G.pop_back();
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=70;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=70;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	for(i=1;i<=70;i++) group[1][i]=1;
	ML[1]=1;
	for(i=2;i<=70;i++) {
		vector<int> cand={(i-1)*2-1,(i-1)*2,(i-1)*2,(i-1)*2+1};
		ML[i]=(i-1)*2-1;
		FORR(l,cand) {
			for(x=l;x<=70;x++) (group[i][x]+=hcomb(l,x-l))%=mo;
		}
	}
	
	
	tot=1;
	vector<ll> C(71);
	C[0]=1;
	dfs(N,70,C);
	cout<<tot<<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);
	cout.tie(0); solve(); return 0;
}


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

int main() {
  string s, t;
  cin >> s >> t;
  int sn = (int)s.size(), tn = (int)t.size();
  string ans;
  rep(i, sn - tn + 1) {
    bool d = false;
    rep(j, tn) {
      if (s[i + j] != '?' && s[i + j] != t[j]) d = true;
    }
    if (d) continue;
    string ss = s;
    rep(j, sn) if (s[j] == '?') ss[j] = j >= i && j < i + tn ? t[j - i] : 'a';
    if (ss < ans || ans.empty()) ans = move(ss);
  }
  cout << (ans.empty() ? "UNRESTORABLE" : ans) << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class A
{
	public static void Main() => (new Solver()).Solve();
}

public class Solver
{
	public void Solve()
	{
		int N = GetInt();
		string[] s = new string[N];
		long[] t = new long[N];
		for(long i = 0; i < N; i++)
		{
			s[i] = GetString();
			t[i] = GetLong();
		}

		string X = GetString();
		long ans = 0;
		bool flag = false;
		for(long i = 0; i < N; i++)
		{
			if(flag)
			{
				ans += t[i];
			}
			else
			{
				if(s[i].Equals(X))
					flag = true;
			}
		}
		WriteLine(ans);
	}
}

public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => Enumerable.Range(0, (int)N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(long N) => Enumerable.Range(0, (int)N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDouble()).ToArray();
	public static decimal[] GetDecimals(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDecimal()).ToArray();
	public static string[] GetStrings(long N) => Enumerable.Range(0, (int)N).Select(_ => GetString()).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) < 0)
			x = y;
	}

	public static void chmin<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) > 0)
			x = y;
	}

	public static void swap<T>(ref T x, ref T y)
	{
		T tmp = x;
		x = y;
		y = tmp;
	}
}

Measured memory_bytes: 13268
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

int main(void){
    int A,B;
    char S[10];
    
    scanf("%s",S);
    
    if(strcmp(S,"SUN") == 0){
        printf("7\n");
    }else if(strcmp(S,"MON") == 0){
        printf("6\n");
    }else if(strcmp(S,"TUE") == 0){
        printf("5\n");
    }else if(strcmp(S,"WED") == 0){
        printf("4\n");
    }else if(strcmp(S,"THU") == 0){
        printf("3\n");
    }else if(strcmp(S,"FRI") == 0){
        printf("2\n");
    }else if(strcmp(S,"SAT") == 0){
        printf("1\n");
    }
  
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cmath>
#include <map>
#include <utility>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

#define LL long long


int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << min(c, b / a);

    return 0;
}


Measured memory_bytes: 384
import math

def is_prime(n):
  if n == 1: 
    return False

  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False

  return True

n = int(input())
for i in range(n, 10**6):
  if is_prime(i):
    print(i)
    exit()

Measured memory_bytes: 3316
n,a,b = list(map(int, input().split()))
if n == 1:
    if a==b:
        print(1)
    else:
        print(0)
elif a>b:
    print(0)
else:
    MIN = a * (n-1) + b
    MAX = a * 1 + b * (n-1)
    print(MAX-MIN+1)

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

long l, r, m, t;

int main(){
	cin >> l >> r;
	m = 2019;
	for (int i = l; i <= min(l + 2019, r-1); ++i){
		for (int j = l+1; j <= min(l+2020, r); ++j){
			t = ((i % 2019) * (j % 2019)) % 2019;
			if (t < m) m = t;
		}
	}
	cout << m;
}

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

int main()
{
   int N;
   int a[100];
   int i,count=0;
   scanf("%d\n",&N);
   for(i=1;i<N+1;i++)
   {
       scanf("%d",&a[i]);
   }
   for(i=1;i<N+1;i++)
   {
       if((i%2!=0)&&a[i]%2!=0)
      count++;
   }
   printf("%d",count);
    return 0;
}


Measured memory_bytes: 2152
#include <iostream>
#define N 200000
#define INF 1000000001

using namespace std;

int main() {
	int n;
	int r[N], max = -INF, min = INF;

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

	for(int i = 0; i < n; ++i) {
		if(i >= 1 && r[i] - min > max) {
			max = r[i] - min;
		}

		if(r[i] < min) {
			min = r[i];
		}
	}

	cout << max << endl;

	return 0;
}

Measured memory_bytes: 1940
#include <iostream>
#include <vector>
typedef long long ll;

const ll N_MAX = 1e5 + 5;

using namespace std;

struct UnionFind {
    vector< ll > par;
    vector< ll > sizes;

    UnionFind(ll n) : par(n), sizes(n, 1) {
        for (ll i = 1; i < n; i++) {
            par[i] = i;
        }
    }

    ll find(ll x) {
        if (x == par[x]) return x;
        return par[x] = find(par[x]);
    }

    void unite(ll x, ll y) {
        x = find(x);
        y = find(y);

        if (x == y) return;
        if (sizes[x] < sizes[y]) swap(x, y);
        par[y] = x;
        sizes[x] += sizes[y];
    }

    bool same(ll x, ll y) { return find(x) == find(y); }

    ll size(ll x) { return sizes[find(x)]; }
};

int main() {
    ll N, M;

    cin >> N >> M;
    vector< ll > A(M), B(M);
    UnionFind uf(N);

    for (ll i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }

    vector< ll > ans;
    ll cur_ans = N * (N - 1) / 2;
    for (ll i = M - 1; i >= 0; i--) {
        ans.push_back(cur_ans);
        if (!uf.same(A[i], B[i])) {
            ll size1 = uf.size(A[i]);
            ll size2 = uf.size(B[i]);
            cur_ans -= size1 * size2;
            uf.unite(A[i], B[i]);
        }
    }

    for (ll i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 5364