akhauriyash/Code-Regression huggingface dataset:
import sys
import numpy as np
from numba import njit, void, i8
input = sys.stdin.buffer.readline

def main():
    R, C, K = map(int, input().split())
    cell = np.full((R+1, C+1), 0, dtype=np.int64)
    for i in range(K):
        x, y, c = map(int, input().split())
        cell[x-1, y-1] = c
    print(calc(cell, R, C))

@njit(i8(i8[:,:],i8,i8))
def calc(cell, R, C):
    L_INF = int(1e17)
    dp = np.full((R+1, C+1, 4), -L_INF, dtype=np.int64)
    dp[0, 1, 0] = dp[1, 0, 0] = 0
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            for k in range(4):
                if k > 0:
                    dp[i, j, k] = max(dp[i, j, k], dp[i, j, k-1])
                dp[i, j, k] = max(dp[i, j, k], dp[i, j-1, k])
                if k > 0:
                    dp[i, j, k] = max(dp[i, j, k], dp[i, j-1, k-1] + cell[i-1, j-1])
                if k == 1:
                    dp[i, j, k] = max(dp[i, j, 1], dp[i-1, j, 3] + cell[i-1, j-1])
    return dp[R, C, 3]

if __name__ == "__main__":
    main()


Measured memory_bytes: 464960
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    vvi dp(n + 1, vi(m + 1, 0));
    vector<vector<pii>> p(n + 1, vector<pii>(m + 1));
    for (int i = 0; i <= m; ++i) dp[0][i] = 0;
    for (int i = 0; i <= n; ++i) dp[i][0] = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1, p[i][j] = {i - 1, j - 1};
            else {
                if (dp[i - 1][j] >= dp[i][j - 1]) dp[i][j] = dp[i - 1][j], p[i][j] = {i - 1, j};
                else dp[i][j] = dp[i][j - 1], p[i][j] = {i, j - 1};
            }
        }
    }
    string ans;
    pii x = {n, m};
    while(x.ff != 0 && x.ss != 0){
        if (p[x.ff][x.ss].ff == (x.ff - 1) && p[x.ff][x.ss].ss == (x.ss - 1)) {
            ans += a[x.ff - 1];
            // cout << x.ff << " " << x.ss << " " << a[x.ff] << endl;
        }
        x = p[x.ff][x.ss];
    }
    // for (int i = 0; i <= n; ++i){
    //     for (int j = 0; j <= m; j++){
    //         printf("%d ", dp[i][j]);
    //     }
    //     printf("\n");
    // }
    reverse(ans.begin(), ans.end());
    // cout << dp[n][m] << " ";
    cout << ans << "\n";
    return 0;
}

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

using namespace std;
typedef long long ll;

#define N 10000005

int main()
{
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < s.size(); i++)
    {
        int j;
        for (j = 0; j < t.size(); j++)
        {
            if (s[(i + j) % s.size()] != t[j])
                break;
        }
        if(j==t.size())
        {
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> x(n), y(n), h(n);
  rep(i, n) cin >> x[i] >> y[i] >> h[i];

  rep(cx, 101) rep(cy, 101) {
    int i = 0;
    while (h[i] <= 0) i++;
    ll H = h[i] + abs(x[i] - cx) + abs(y[i] - cy);

    bool flag = true;
    rep(j, n) flag &= (h[j] == max(H - abs(x[j] - cx) - abs(y[j] - cy), 0LL));
    if (flag) {
      cout << cx << " " << cy << " " << H << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 3632
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vector<int> > vvi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b, a%b);
}
int main(){
    int n, x;
    cin >> n >> x;
    vi v;
    for(int i = 0; i < n; i++){
        int d;
        cin >> d;
        v.pb(abs(d-x));
    }
    sort(rall(v));
    int s = v[0];
    for(int i = 1; i < v.size(); i++){
        s = gcd(s, v[i]);
    }
    cout << s;
}   

Measured memory_bytes: 892
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int a = Integer.valueOf(s.substring(0,2));
        int b = Integer.valueOf(s.substring(2, 4));
        if(0 < a && a < 13){
            if(0 < b && b < 13) System.out.println("AMBIGUOUS");
            else System.out.println("MMYY");
        }else{
            if(0 < b && b < 13) System.out.println("YYMM");
            else System.out.println("NA");
        }
        sc.close();

    }

}


Measured memory_bytes: 21716
INFTY = 10**9

N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [INFTY] * N
dp[0] = 0
for i in range(1,N):
    j = 1
    while j <= K and i-j >= 0:
        dp[i] = min(dp[i], dp[i-j]+abs(H[i-j]-H[i]))
        j += 1

print(dp[N-1])

Measured memory_bytes: 52448
require 'pp'

t = gets.chomp!.chars
n = t.length

n.times do |i|
    if t[i] == '?'
        if t[i-1] == 'P'
            print 'D'
        elsif t[i+1] == '?'
            print 'P'
            t[i+1] = 'D'
        elsif t[i+1] == 'D'
            print 'P'
        else
            print 'D'
        end
    else
        print t[i]
    end
end

puts ""


Measured memory_bytes: 31524
using System;

public class Test
{
	public static void Main()
	{
		// your code goes here
		int N = int.Parse(Console.ReadLine());
		int A = int.Parse(Console.ReadLine());
		
		if(A>=N%500)
		{
			Console.WriteLine("Yes");
		}
		else
		{
			Console.WriteLine("No");
		}
	}
}

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

int64_t gcd(int64_t a, int64_t b)
{
  if(b == 0)
  {
    return a ;
  }
  else
  {
    return gcd(b, a % b) ;
  }
  
}

int64_t lcm(int64_t a, int64_t b)
{
  return a * b / gcd(a, b) ;
}

int main()
{
  int64_t a, b ;
  cin >> a >> b ;
  if(a > b)
  {
    swap(a, b) ;
  }
  int64_t c = lcm(a,b) ;

  cout << c << endl ;
}


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

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

    int ans = 0;
    for (int i = 0; i < n/4; ++i) {
      int t;
      cin >> t;
      ans += t;
    }

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

Measured memory_bytes: 0
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int main() {
  ios::sync_with_stdio(0); 
  cin.tie(0); 
  
  string o, e;
  cin >> o >> e;

  string res;

  int i = 0, j = 0;
  while (i < o.size() || j < e.size()) {
    if (i < o.size()) {
      res += o[i++];
    }
    if (j < e.size()) {
      res += e[j++];
    }
  }

  cout << res << "\n";
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()

int main(){
  int a,b,k;
  vector<int> co;
  cin >> a >> b >> k;
  for(int i=1;i<=min(a,b);i++){
    if(a%i==0 && b%i==0)co.push_back(i);
  }
  cout << co[co.size()-k];
}


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

int main() {
	queue<int> q;
	int tmp;
	while (1) {
		cin >> tmp;
		if (!tmp) break;
		q.push(tmp);
	}
	int n = q.size();
	for (int i = 1; i <= n; i++ ){
		cout << "Case " << i << ": " << q.front() << endl;
		q.pop();
	}
	return 0;
}

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

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const int inf = 2e9;
const int N = 2e5 + 15;
int n, m, k, q, a[N], dp[N][3];
string s, t, last;
vector <int> now;

int main() {
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	cin >> s; n = s.size();
	dp[0][1] = dp[1][2] = 1;
	for(int i = 1; i < n; ++i) {
		if(s[i] != s[i-1])
			dp[i][1] = max(dp[i][1], dp[i-1][1] + 1);
		if(i > 2 && s[i - 3] + s[i - 2] != s[i - 1] + s[i])
			dp[i][2] = max(dp[i][2], dp[i - 2][2] + 1);
		if(i > 1) {
			dp[i][1] = max(dp[i][1], dp[i-1][2] + 1);
			dp[i][2] = max(dp[i][2], dp[i - 2][1] + 1);
		}
	}
	cout << max(dp[n - 1][1], dp[n - 1][2]);
	return 0;
}

Measured memory_bytes: 2964
#include<iostream>
using namespace std;
int main(){
int n,cntA =0,cntB = 0;
cin >> n;
char c;
for(int i=0;i<n;i++){
cin >> c;
if(c == 'R')cntA++;
else cntB++;
}
if(cntA > cntB)cout << "Yes" << endl;
else cout << "No";
return 0;
}

Measured memory_bytes: 256
N=int(input())
c=[[0]*10 for _ in range(10)]

for A in range(1,N+1):
    Astr=str(A)
    pre=int(Astr[0])
    suf=int(Astr[-1])
    c[pre][suf]+=1
cnt=0
for i in range(10):
    for j in range(10):
        cnt+=c[i][j]*c[j][i]

print(cnt)

Measured memory_bytes: 40428
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 200010
#define INF 1000000005
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000005;
const int MOD = 1000000007;
vector<int>a(N);
int length=1;
stack<P> st;
vector<int> to[N];
vector<int>l(N,INF);
vector<int>ans(N);
    void dfs(int no,int p){
        for(auto s:to[no]){
            if(s==p)continue;
            int t=lower_bound(ALL(l),a[s])-l.begin();
            st.push({t,l[t]});
            if(l[t]==INF)length++;
            l[t]=a[s];
            ans[s]=length;
            dfs(s,no);
            P q=st.top();
        st.pop();
        l[q.first]=q.second;
        if(q.second==INF)length--;
        }
        
        
    }
int main(){
    int n;
    cin>>n;
    REP(i,n)cin>>a[i];
    REP(i,n-1){
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        to[x].push_back(y);
        to[y].push_back(x);
    }
    l[0]=a[0];
    dfs(0,-1);
    ans[0]=1;
    REP(i,n)OUT(ans[i]);
    return 0;
}

Measured memory_bytes: 40820
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include <string>
using namespace std;
int main()
{

    int T;
    cin>>T;
    if(T%2==0)
        printf("%d\n",T/2-1);
    else
        printf("%d\n",T/2);


    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    static class UnionFind {
        int[] size;
        int[] id;

        public UnionFind(int n) {
            size = new int[n];
            id = new int[n];
            for (int i = 0; i < n; ++i) {
                size[i] = 1;
                id[i] = i;
            }
        }

        public void unify(int p, int q) {
            if (connected(p, q)) return;

            int root1 = find(p);
            int root2 = find(q);

            if (size[root1] > size[root2]) {
                size[root1] += size[root2];
                id[root2] = root1;
            } else {
                size[root2] += size[root1];
                id[root1] = root2;
            }
        }

        public int find(int p) {
            int root = p;
            while (root != id[root]) root = id[root];
            while (p != root) {
                int next = id[p];
                id[p] = root;
                p = next;
            }
            return root;
        }

        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
    }

    static class Edge {
        int from, to;

        public Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int e = sc.nextInt();
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < e; ++i) {
            edges.add(new Edge(sc.nextInt() - 1, sc.nextInt() - 1));
        }

        int res = 0;
        for (int i = 0; i < e; ++i) {
            UnionFind uf = new UnionFind(v);
            Edge edge = edges.get(i);
            for (int j = 0; j < e; ++j) {
                if (i == j) continue;
                Edge tmp = edges.get(j);
                uf.unify(tmp.from, tmp.to);
            }
            if (!uf.connected(edge.from, edge.to)) ++res;
        }

        System.out.println(res);
    }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFF 9223372036854775807
#define ll long long
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<n;i++)
#define ALL(N) (N.begin(),N.end())

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<double> A(N);
  REP(i,N) cin >> A[i];
  double a=0;
  REP(i,N) a+=(1/A[i]);
  cout << 1/a << endl;
}

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

using namespace std;
long long res=0;
int n,dat[500];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++) scanf("%d",&dat[i]);
	sort(dat+1,dat+2*n+1);
	for(int i=1;i<=2*n;i+=2) res+=dat[i];
	printf("%lld",res);
	return 0;
}

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

int main()
{
    string S;
    cin >> S;
    int zero = 0;
    int one  = 0;
    for (int i = 0; i < S.length(); i++) {
        if (S[i] == '0') zero++;
        else             one++;
    }

    cout << 2 * min(zero, one) << endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
typedef long long ll;
using namespace std;

int main(void)
{
	string c; cin >> c;
	if (c[0] == 'a' || c[0] == 'i' || c[0] == 'u' || c[0] == 'e' || c[0] == 'o' ) cout << "vowel" << endl;
	else cout << "consonant" << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
#include<vector>
struct UF{
	int n;
	vector<int>parent,rank;
	UF(int n_=0):n(n_),parent(n_),rank(n_,0)
	{
		for(int i=0;i<n_;i++)parent[i]=i;
	}
	int find(int a)
	{
		return parent[a]!=a?parent[a]=find(parent[a]):a;
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
	bool unite(int a,int b)
	{
		a=find(a),b=find(b);
		if(a!=b)
		{
			if(rank[a]<rank[b])
			{
				parent[a]=b;
			}
			else
			{
				parent[b]=a;
				if(rank[a]==rank[b])rank[a]++;
			}
		}
		return a!=b;
	}
};
main()
{
	int n,q;cin>>n>>q;
	UF uf(n);
	for(;q--;)
	{
		int p,a,b;cin>>p>>a>>b;
		if(p)cout<<uf.same(a,b)<<endl;
		else uf.unite(a,b);
	}
}



Measured memory_bytes: 3176
#include <iostream>
#include<string>
using namespace std;
int main(){
int k,s;
cin>>k>>s;
int ans=0;
for(int i=0;i<=k;i++)for(int j=0;j<=k;j++)if(i+j<=s&&s-i-j<=k)ans++;
cout<<ans<<endl;
}

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


namespace atc
{

    class Program
    {
        static T Read<T>()
        {
            Func<string, T> convFunc = null;
            if (typeof(T) == typeof(int)) convFunc = (_) => { return (T)(object)(int.Parse(_)); };
            else if (typeof(T) == typeof(Int16)) convFunc = (_) => { return (T)(object)(Int16.Parse(_)); };
            else if (typeof(T) == typeof(UInt16)) convFunc = (_) => { return (T)(object)(UInt16.Parse(_)); };
            else if (typeof(T) == typeof(Int32)) convFunc = (_) => { return (T)(object)(Int32.Parse(_)); };
            else if (typeof(T) == typeof(UInt32)) convFunc = (_) => { return (T)(object)(UInt32.Parse(_)); };
            else if (typeof(T) == typeof(Int64)) convFunc = (_) => { return (T)(object)(Int64.Parse(_)); };
            else if (typeof(T) == typeof(UInt64)) convFunc = (_) => { return (T)(object)(UInt64.Parse(_)); };
            else if (typeof(T) == typeof(float)) convFunc = (_) => { return (T)(object)(float.Parse(_)); };
            else if (typeof(T) == typeof(double)) convFunc = (_) => { return (T)(object)(double.Parse(_)); };
            return convFunc(Console.ReadLine());
        }

        static List<T> ReadVec<T>()
        {
            Func<string, T> convFunc = null;
            if (typeof(T) == typeof(int)) convFunc = (_) => { return (T)(object)(int.Parse(_)); };
            else if (typeof(T) == typeof(Int16)) convFunc = (_) => { return (T)(object)(Int16.Parse(_)); };
            else if (typeof(T) == typeof(UInt16)) convFunc = (_) => { return (T)(object)(UInt16.Parse(_)); };
            else if (typeof(T) == typeof(Int32)) convFunc = (_) => { return (T)(object)(Int32.Parse(_)); };
            else if (typeof(T) == typeof(UInt32)) convFunc = (_) => { return (T)(object)(UInt32.Parse(_)); };
            else if (typeof(T) == typeof(Int64)) convFunc = (_) => { return (T)(object)(Int64.Parse(_)); };
            else if (typeof(T) == typeof(UInt64)) convFunc = (_) => { return (T)(object)(UInt64.Parse(_)); };
            else if (typeof(T) == typeof(float)) convFunc = (_) => { return (T)(object)(float.Parse(_)); };
            else if (typeof(T) == typeof(double)) convFunc = (_) => { return (T)(object)(double.Parse(_)); };
            return Console.ReadLine().Split(' ').Select(s => (T)convFunc(s)).ToList();
        }

        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var t = Console.ReadLine();

            var length = s.Length;
            var count = 0;

            var sa = s.ToCharArray();
            var ta = t.ToCharArray();
            for(var i = 0; i < length; i++)

            {
                if (sa[i] != ta[i]) count++;
            }



            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 28276
a = input()
b = input()
c = input()
x = input()

a = int(a)
b = int(b)
c = int(c)
x = int(x)

# a = 2
# b = 2
# c = 2
# x = 100

cnt = 0
for i1 in range(0,a+1):
    for i2 in range(0,b+1):
        for i3 in range(0,c+1):
            s = 500*i1+100*i2+50*i3
            if(s==x):
                cnt = cnt + 1
print(cnt)


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    while(true){
        int H = sc.nextInt();
        int W = sc.nextInt();

        if(H == 0 && W == 0)
           break;

        for(int i = 0;i<H;i++){
            for(int j = 0;j<W;j++){
                System.out.printf("#");
            }
                System.out.printf("\n");
        }
                System.out.printf("\n");
    }
  }
}



Measured memory_bytes: 65660
#include <bits/stdc++.h>
 
#define A_MAX 1000000
#define A_MAX_HALF 500000
 
using namespace std;
 
int min_factor[A_MAX + 1];
int q[A_MAX + 1];
int a[A_MAX + 1];
vector<int> primes{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 };
int N;

int read_int() {
    int x = 0;
    char c = getchar_unlocked();
    do {
      x = 10 * x + c - '0';
    } while ((c = getchar_unlocked()) >= '0');
    return x;
}
 
int main() {
    for (int i = 2; i <= A_MAX_HALF; ++i) {
        if (!min_factor[i]) {
            min_factor[i] = i;
        }
        int min_factor_i = min_factor[i];
        for (int p : primes) {
            int n = i * p;
            if (n > A_MAX) {
                break;
            }
            min_factor[n] = p;
            if (p == min_factor_i) {
                q[n] = q[i];
                break;
            } else {
                q[n] = i;
            }
        }
    }
 
    N = read_int();
    for (int i = 0; i < N; ++i) {
        ++a[read_int()];
    }
 
    int is_pairwise_coprime = 1;
    for (int n = A_MAX; n > 1; --n) {
        int an = a[n];
        if (an) {
            if (an > 1) {
                if (an == N) {
                    printf("not coprime\n");
                    return 0;
                }
                is_pairwise_coprime = 0;
            }
            a[min_factor[n]] += an;
            a[q[n]] += an;
        }
    }
    if (is_pairwise_coprime) {
        printf("pairwise coprime\n");
    } else {
        printf("setwise coprime\n");
    }
 
    return 0;
}

Measured memory_bytes: 15344
#include<stdio.h>

int main() {
    int a, b;
    int i;

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

    if(a < b){
        for(i = 0; i < b; i++) {
            printf("%d",a);
        }
    } else {
        for(i = 0; i < a; i++) {
            printf("%d",b);
        }
    }

    return 0;
}

Measured memory_bytes: 128
n = int(input())
a, b = map(int, input().split())
p = list(int(x) for x in input().split())
k1, k2, k3 = 0, 0, 0
for i in range(n):
    if p[i] <= a:
        k1 += 1
    elif p[i] <= b:
        k2 += 1
    else:
        k3 += 1
print(min([k1, k2, k3]))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define pi 2*acos(0.0)
#define ll long long int
using namespace std;
int main()
{
    ll i,j,k,n,s=0;
    map<ll,ll>m;
    cin>>n;
    for(i=0;i<n-1;i++)
    {
        cin>>k;
        m[k]++;
    }
    for(i=1;i<=n;i++)
    {
        cout<<m[i]<<endl;
    }





    return 0;
}


Measured memory_bytes: 16132
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long lli;
const int MAXN = 100005;
const int MAXM = 100005;
const int INF = 1<<28;

int main() {
  int N, M;
  lli s[MAXN], t[MAXN];
  lli P[MAXM];
  while(cin >> N >> M) {
    for(int i = 0; i < N; ++i) {
      cin >> s[i] >> t[i];
    }
    for(int i = 1; i <= M; ++i) {
      cin >> P[i];
    }
    P[0] = 0;
    sort(P, P+M+1);

    lli T[2][MAXM];
    fill(T[0], T[2], 0);
    for(int i = 1; i <= M; ++i) {
      T[0][i] += T[0][i-1];
      T[1][i] += T[1][i-1];
      T[(i-1)%2][i] += P[i] - P[i-1];
    }

    lli res = 0;
    for(int i = 0; i < N; ++i) {
      lli p, q;
      bool rev = s[i] > t[i];
      if(rev) swap(s[i], t[i]);
      p = lower_bound(P, P+M+1, s[i]) - P;
      q = ( lower_bound(P, P+M+1, t[i]) - P ) - 1;
      if(rev) {
        swap(s[i], t[i]);
        swap(p, q);
      }

      if((q-p) * (t[i]-s[i]) < 0) {
        res += labs(t[i] - s[i]);
        continue;
      }

      if(p <= q && p % 2 != 0 ||
         p >  q && p % 2 == 0) {
        res += labs(T[0][q] - T[0][p]);
      } else {
        res += labs(T[1][q] - T[1][p]);
      }

      res += labs(P[p] - s[i]);
      if((q-p) % 2  != 0)
        res += labs(t[i] - P[q]);
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 5092
#include<bits/stdc++.h>
#define N 100005
#define ll long long
#define P 1000000007
using namespace std;
int n,fa[N],b[N],rd[N],fl[N],sum[N];
void biu()
{
	puts("0");
	exit(0);
}
void dfs(int x)
{
	if (fl[fa[x]]) biu();
	rd[fa[x]]--;fl[fa[x]]=fl[x]+1;rd[x]=-1;
	if (rd[fa[x]]==0) dfs(fa[x]);
}
int F(int x,int k)
{
	static int f[N];
	f[0]=1;f[1]=2;
	for (int i=2;i<=x;i++)
		f[i]=(f[i-1]*2+(ll)f[i-2]*(i-1)%P*k)%P;
	return f[x];
}
int G(int x,int k)
{
//	cout<<x<<' '<<k<<endl;
	static int g[N];
	g[0]=1;g[1]=1;
	for (int i=2;i<=x;i++)
		g[i]=(g[i-1]+(ll)g[i-2]*(i-1)%P*k)%P;
	return g[x];
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&fa[i]),rd[fa[i]]++;
	for (int i=1;i<=n;i++)
		if (rd[i]==0) dfs(i);
	int Ans=1;
	for (int i=1;i<=n;i++)
		if (rd[i]==1)
		{
			int x=i,y=fa[i],cnt=0,flag=0;
			b[++cnt]=fl[i];
			if (fl[i]) flag=cnt;
			for (;y!=i;y=fa[y],x=fa[x])
			{
				b[++cnt]=fl[y];rd[y]=0;
				if (fl[y]) flag=cnt;
			}
			//cout<<cnt<<' '<<flag<<endl;
			if (!flag) sum[cnt]++;
			else
			{
				flag=flag-cnt;
				for (int j=1;j<=cnt;j++)
				{
					//cout<<b[j]<<endl;
					if (b[j])
					{
						if (b[j]>j-flag) biu();
						if (b[j]<j-flag) Ans=Ans*2%P;
						flag=j;
					}
				}
			}
		}
	//	cout<<Ans<<endl;
	for (int i=1;i<=n;i++)
	{
	//	cout<<i<<' '<<sum[i]<<endl;
		if ((i&1)&&i!=1) Ans=(ll)Ans*F(sum[i],i)%P;
		else Ans=(ll)Ans*G(sum[i],i)%P;
	}
	printf("%d\n",Ans);
}

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

void setup()
{
    //cinでファイルから読込
    ifstream in("./input.txt");
    cin.rdbuf(in.rdbuf());

    //cinの高速化
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int main()
{
    int A, B;
    cin >> A;
    cin >> B;

    int plus = A + B;
    int minus = A - B;
    int multiple = A * B;

    int max = plus;
    if (max < minus)
    {
        max = minus;
    }
    if (max < multiple)
    {
        max = multiple;
    }

    cout << max << endl;

    return 0;
}

Measured memory_bytes: 256
from collections import deque

stack = deque()

for i in input().split():
    if not i in ['+','-','*']:
        stack.append(int(i))
    else:
        num1 = stack.pop()
        num2 = stack.pop()
        if i == "+":
            num = num1+num2
        elif i=="-":
            num = num2-num1
        else:
            num = num1*num2
        stack.append(num)

print(stack[0])


Measured memory_bytes: 6004
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

int main(){
    long long N; std::cin >> N;
    std::vector<long long> a(3 * N);
    for (auto& r : a)std::cin >> r;
    std::sort(a.begin(), a.end());
    long long ans = 0;
    for (int i = 0; i < N; ++i)
        ans += a[(3 * N) - 2 - (2 * i)];
    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 5584
#include<stdio.h>
#include<string.h>
int main()
{
    int i=0,j=0,l;
    char s[100002],odd[100002];
    scanf("%s",s);
    l=strlen(s);
    for(i=0; i<l; i++)
    {
        if(s[i]>='a' && s[i]<='z')
        {
            if(i%2==0)
            {
                odd[j++]=s[i];
            }
        }
        else
        {
            return 0;
        }
    }
    printf("%s\n",odd);
    return 0;
}


Measured memory_bytes: 384
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Book[] books = new Book[n];
		for (int i = 0; i < n; i++) {
		    books[i] = new Book(sc.next(), sc.next(), sc.next());
		}
		int q = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < q; i++) {
		    if (i != 0) {
		        sb.append("\n");
		    }
		    String tQuery = sc.next();
		    String aQuery = sc.next();
		    String from = sc.next();
		    String to = sc.next();
		    for (int j = 0; j < n; j++) {
		        if (books[j].isHit(tQuery, aQuery, from, to)) {
		            sb.append(books[j].title).append("\n");
		        }
		    }
		}
		System.out.print(sb);
	}
	
	static class Book {
	    String title;
	    String author;
	    String date;
	    
	    public Book (String title, String author, String date) {
	        this.title = title;
	        this.author = author;
	        this.date = date;
	    }
	    
	    public boolean isHit(String tQuery, String aQuery, String from, String to) {
	        if (!tQuery.equals("*")) {
	            if (!title.contains(tQuery)) {
	                return false;
	            }
	        }
	        if (!aQuery.equals("*")) {
	            if (!author.contains(aQuery)) {
	                return false;
	            }
	        }
	        if (!from.equals("*")) {
	            if (date.compareTo(from) < 0) {
	                return false;
	            }
	        }
	        if (!to.equals("*")) {
	            if (date.compareTo(to) > 0) {
	                return false;
	            }
	        }
	        return true;
	    }
	}
}



Measured memory_bytes: 29564
#include <bits/stdc++.h>
// e.g. sort(all(a), [](int a1, int a2) { return a1 < a2; });
#define all(a) (a).begin(),(a).end()
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

int main() {
  string s;
  cin >> s;
  if (s[2] == s[3] && s[4] == s[5]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
n, m = list(map(int, input().split()))
hs =  list(map(int, input().split()))
ans = [1]*n
for i in range(m):
    road = list(map(int, input().split()))
    if hs[road[0]-1] <= hs[road[1]-1]:
        ans[road[0]-1] = 0
    if hs[road[0]-1] >= hs[road[1]-1]:
        ans[road[1]-1] = 0
print(ans.count(1))


Measured memory_bytes: 19992
n = int(input())
a = map(int,input().split())

point_Alice = 0
point_Bob = 0

b = sorted(a,reverse=True)

while True:
    point_Alice += b.pop(0)
    if b == []:
        break
    point_Bob += b.pop(0)
    if b == []:
        break

ans = point_Alice - point_Bob
print(ans)


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

using namespace std;

int main(){
    string o;
    string e;
    cin >> o >> e;
    for(int i=0;i<e.length();i++){
        cout << o[i] << e[i];
    }
    if(o.length()!=e.length()){
        cout << o[o.length()-1];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>

using namespace std;

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


int main(){
    string s, t;
    cin >> s >> t;
    s += t[t.size()-1];
    if(s == t) cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

int main(){
    int n,ans=1e8;
    cin >> n;
    vector<int> s(n);
    for(int i = 0;i < n;i ++){
        int w;
        cin >> w;
        if(i==0) s[i] = w;
        else s[i] = s[i-1] + w;
    }
    for(int i = 0;i < n-1;i ++){
        ans = min(ans,abs(s[i] - (s[n-1]-s[i])));
    }
    cout << ans << endl;
    return 0;
}

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

typedef long long ll;

int n, a[maxn];

ll dp[maxn][2]; // 0 no change, 1 change

int main()
{
    //freopen("a.inp","r",stdin);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];

    dp[1][1] = -1e18;

    for(int i=2;i<=n;i++)
    {
        dp[i][0] = max(dp[i-1][0] + a[i-1], dp[i-1][1] - a[i-1]);
        dp[i][1] = max(dp[i-1][0] - a[i-1], dp[i-1][1] + a[i-1]);
    }
    cout << max(dp[n][0] + a[n], dp[n][1] - a[n]);
}


Measured memory_bytes: 2176
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]

A.sort()
S_BC = sorted(BC,key=lambda x:x[1],reverse=True)

index = 0
flag = 0
for Bj,Cj in S_BC:
    for k in range(Bj):
        if len(A) >= index+1:
            if A[index] < Cj:
                A[index] = Cj
                index += 1
            else:
                flag = 1
                break
        else:
            flag = 1
            break
        
    if flag == 1:
        break

print(sum(A))


Measured memory_bytes: 33728
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using llong = long long;
using P = pair<int, int>;
const int inf = 1 << 20;
const int mod = 1e9 + 7;

int main() {
   int n;
   cin >> n;
   vector<bool> S(14), H(14), C(13), D(13);
   rep(i, n) {
      char s;
      int num;
      cin >> s >> num;
      if (s == 'S')
         S[num] = true;
      else if (s == 'H')
         H[num] = true;
      else if (s == 'C')
         C[num] = true;
      else if (s == 'D')
         D[num] = true;
   }
   for (int i = 1; i < 14; i++) {
      if (!S[i])
         printf("S %d\n", i);
   }
   for (int i = 1; i < 14; i++) {
      if (!H[i])
         printf("H %d\n", i);
   }
   for (int i = 1; i < 14; i++) {
      if (!C[i])
         printf("C %d\n", i);
   }
   for (int i = 1; i < 14; i++) {
      if (!D[i])
         printf("D %d\n", i);
   }
   return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
#define REP(i,n) for(int i = 0;i < n; i++)
#define all(a) a.begin(),a.end()
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const long long MOD = 1000000007, INF = 1e18;
 
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
 
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>vector<T>
make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}
 
template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}

struct DATA{
	int l,r,num;
};
vector<DATA>v;

void WRITE(int a,int b){
	rep(i,1,v.size()){
		int haba = min(b,v[i].l-v[i-1].r);
		if(haba==0)continue;
		b-=haba;
		v.insert(v.begin()+i,{v[i-1].r,v[i-1].r+haba,a});
		if(b==0)break;
	}
}

void DELETE(int a){
	for(auto itr = v.begin();itr != v.end();){
		if(itr->num==a)v.erase(itr);
		else itr++;
	}
}
int READ(int a){
	rep(i,0,v.size()){
		if(v[i].l<=a&&a<v[i].r){
			return v[i].num;
		}
	}
	return -1;
}

int N;
void solve(vector<int>&ans){
	v.clear();
	v.push_back({-1,0,-1});
	v.push_back({1000000001,1000000002,-1});
	rep(i,0,N){
		char c;
		cin>>c;
		if(c=='W'){
			int a,b;
			cin>>a>>b;
			WRITE(a,b);
		}else if(c=='D'){
			int a;
			cin>>a;
			DELETE(a);
		}else{
			int a;
			cin>>a;
			ans.push_back(READ(a));
		}
	}
}
 
signed main(){
	IOS();
	vector<int>ans;
	while(cin>>N,N){
		solve(ans);
		ans.push_back(-INF);
	}
	for(auto e:ans){
		if(e==-INF)cout<<endl;
		else cout<<e<<endl;
	}
}


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

int main() {
    unsigned int n, w = 0;
    std::cin>>n>>w;
    std::vector<std::vector<int>> dp(n,std::vector<int>(w+1,0));
    std::vector<std::pair<int,int>> it;
    for (int i = 0; i < n; ++i) {
        int f, s = 0;
        std::cin>>f>>s;
        it.emplace_back(f,s);
    }
    dp[0][0]=0;
    for (int i = 0; i <= w; ++i) {
        if(i>=it[0].second)dp[0][i]=it[0].first;
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= w; ++j) {
            if(j<it[i].second)dp[i][j]=dp[i-1][j];
            else dp[i][j]=std::max(dp[i-1][j-it[i].second]+it[i].first,dp[i-1][j]);
        }
    }
    std::cout<<dp[n-1][w]<<std::endl;
    return 0;
}


Measured memory_bytes: 6832
n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
def f(x):
    return t-x*0.006
for i in range(n):
    h[i]=abs(f(h[i])-a)
m=min(h)
for i in range(n):
    if h[i]==m:
        print(i+1)


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define Edge pair< i_i, int>
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Endl endl
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    Int(n);
    string st; cin >> st;

    int sum = 0, add = 0;

    rep(i, n) {
        if (st[i] == ')') {
            if (add) {
                add--;
            } else {
                sum++;
            }
        } else {
            add++;
        }
    }

    rep(i, sum) {
        cout << "(";
    }
    cout << st;
    rep(i, add) {
        cout << ")";
    }
    cout << endl;

    return 0;
}



Measured memory_bytes: 256
// Program.cpp

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

typedef long long           ll;
typedef pair<int, int>      pii;
typedef vector<int>         vi;

#define fr(i, n)            for(int i=0; i<(n); ++i)
#define frC(i, n)           for(int i=0; (i<(n)) && (c); ++i)
#define frA(i, a, n)        for(int i=a; i<=(n); ++i)
#define frD(i, a, n)        for(int i=a; i>=(n); --i)
#define fill(a)             memset(a, 0, sizeof(a))
#define revsort(a, b)       sort(a, b, greater<int>())
#define dout                if(DEBUGGING) cout
#define dbg                 if(DEBUGGING) 
#define endl                "\n"

int DEBUGGING    =          0;
const int INF    =          1000000000;
const int MOD    =          1000000007;
const double PI  =          3.1415926535897932;
const double EPS =          1e-7;

void dfs(int s,vector<int>& used,vector<int>& dp, vector<int> adj[]){
	if(used[s] == 1)
		return;
	int max = -1;
	for(int i:adj[s]){
		dfs(i,used,dp,adj);
	}
	for(int i:adj[s]){
		if(max<dp[i])
			max = dp[i];
	}
	dp[s] = 1+max;
	used[s] = 1;
	return;
}

void solve(int TEST_CASE){
	int n,m;
	cin >> n >> m;
	vector<int> adj[n];
	int p,q;
	fr(i,m){
		cin >> p >> q;
		adj[p-1].push_back(q-1);
	}
	vector<int> used(n);
	vector<int> dp(n);
	fr(i,n){
		if(used[i] == 0){
			dfs(i,used,dp,adj);
		}
	}
	cout << *max_element(dp.begin(),dp.end()) << " ";
}

int main(int argc, char* argv[]){
    if(argc==2 && argv[1][1]=='v') DEBUGGING = 1;
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin.exceptions(cin.failbit);
    int nTestCases=1;
    //cin >> nTestCases;
    frA(i,1,nTestCases) solve(i);
    return 0;
}

Measured memory_bytes: 12796
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
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; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;
void swap(ll *x,ll *y){
  ll tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}

int main(){
  ll n;
  ll k;
  cin >> n >> k;
  vector<double> vec(n);
  rep(i,n){
    cin >> vec[i];
  }
  rep(i,n){
    vec[i] = (vec[i] + 1) / 2;
  }
  double sum = 0;
  rep(i,k){
    sum += vec[i];
  }
  double ans = sum;
  rep(i,n-k){
    sum -= vec[i];
    sum += vec[k+i];
    chmax(ans,sum);
  }
  printf("%.10f\n",ans);
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#include <atcoder/all>
#define InfL 2000000000
#define InfLL 4000000000000000000LL
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;
vb is_prime;
void p_ini(int n) {
	is_prime.resize(n, true);
	is_prime[0] = false;
	is_prime[1] = false;
	for (int i = 2; i < n; i++) {
		if (!is_prime[i])
			continue;
		for (int j = i * 2; j < n; j += i)
			is_prime[j] = false;
	}
	return;
}

vector<pll> prime_factor(ll n) {
	vector<pll> prime_factor_n;
	ll sqrt_n = sqrt(n) + 10;
	p_ini(sqrt_n);
	rep(i, sqrt_n) {
		if (!is_prime[i])
			continue;
		if (n % i == 0) {
			ll count = 0;
			while (1) {
				n /= i;
				count++;
				if (n % i != 0)
					break;
			}
			prime_factor_n.push_back(make_pair(i, count));
		}
	}
	if (n > 1)
		prime_factor_n.push_back(make_pair(n, 1));
	return prime_factor_n;
}

int main() {
	ll N;
	ll ans = InfLL;
	cin >> N;
	N *= 2;
	vector<pll> pl = prime_factor(N);
	int n = pl.size();
	ll bb = 1;
	rep(i, n)
		bb *= 2;
	rep(b, bb) {
		ll x = 1;
		rep(i, n) {
			if ((b >> i) % 2) {
				rep(j, pl[i].second)
					x *= pl[i].first;
			}
		}
		ll y = N / x;
		vl r(2), m(2);
		r[0] = 0;
		r[1] = y - 1;
		m[0] = x;
		m[1] = y;
		pll anstmp = crt(r, m);
		if (anstmp.first != 0)
			ans = min(ans, anstmp.first);
	}

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

Measured memory_bytes: 8712
#include <stdio.h>
 
int main(void)
{
    int n, m, l, i, j, k;
    int a[100][100] = { 0 }, b[100][100] = { 0 };
    long int c;
 
    scanf("%d %d %d", &n, &m, &l);
 
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
 
    for (i = 0; i < m; i++)
        for (j = 0; j < l; j++)
            scanf("%d", &b[i][j]);
 
    for (i = 0; i < n; i++)
        for (j = 0; j < l; j++) {
            c = 0;
            for (k = 0; k < m; k++) 
                c += a[i][k] * b[k][j];
 
            printf("%ld%s", c, j == l - 1 ? "\n" : " ");
        }
 
 
    return 0;
}

Measured memory_bytes: 688
#include <iostream>
#include <algorithm>

using namespace std;
int main() {
    int N, K;
    cin >> N >> K;
    long long x[N], y[N];
    long long ans = -1;
    for(int i = 0; i < N; i++)
        cin >> x[i] >> y[i];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            for(int k = 0; k < N; k++){
                for(int l = 0; l < N; l++){
                    if(x[i] - x[j] < 0)
                        continue;
                    if(y[k] - y[l] < 0)
                        continue;
                    int cnt = 0;
                    for(int m = 0; m < N; m++) {
                        if(x[j] <= x[m] && x[m] <= x[i] && y[l] <= y[m] && y[m] <= y[k]){
                            cnt++;
                        }
                    }
                    if(cnt >= K) {
                        long long tmp = (x[i] - x[j]) * (y[k] - y[l]);
                        if(tmp < ans || ans == -1)
                            ans = tmp;
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

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

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#include <map>
#include <set>
#define all(x) (x).begin(),(x).end()

const int MOD = 1e9 + 7;

void solve(){

}
int main(){
    int N,A;
    cin >> N >> A;
    cout << N * N - A << endl;

    return 0;
}


Measured memory_bytes: 256
c = []
for i in range(3):
    c1,c2,c3 = map(int,input().split())
    c.append([c1,c2,c3])

a1 = c[0][0] - c[0][1]
a2 = c[0][0] - c[0][2]
b1 = c[0][0] - c[1][0]
b2 = c[0][0] - c[2][0]

ans = "No"
if c[1][1] + a1 == c[1][0] and c[1][1] + b1 == c[0][1]:
    if c[1][2] + a2 == c[1][0] and c[1][2] + b1 == c[0][2]:
        if c[2][1] + a1 == c[2][0] and c[2][1] + b2 == c[0][1]:
            if c[2][2] + a2 == c[2][0] and c[2][2] + b2 == c[0][2]:
                ans = "Yes"

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(i=0;i<N;i++)
typedef long long ll;
typedef pair<int, int> P;
typedef struct{
  int first;
  int second;
  int third;
}T;
#define split 1000000007
#define N_MAX 2e5
//昇順
bool comp_Se(T& l, T& r){
  return l.second < r.second;
}

int N;

int main(void){
  cin >> N;
  vector<int> C(N);
  int i,j,pre=-1;
  REP(i,N){
    cin >> C[i];
    if(pre==C[i]){
      i--;
      N--;
    }else{
      pre = C[i];
    }
  }
  vector<ll> dp(N+1,0);
  vector<ll> L(N_MAX,0);
  dp[0] = 1;
  REP(i,N){
    dp[i+1] = (dp[i]+L[C[i]])%split;
    L[C[i]] = dp[i+1];
  }
  cout << dp[N] << endl;
  return 0;
}

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

using namespace std;

long long a[110];
long long dp[110][100010];
long long sum[110][100010];
long long modul = 1000000007;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        sum[i][0] = 1;
        dp[i][0] = 1;
    }
    for(int j = 1; j <= a[1]; j++)
    {
        dp[1][j] = 1;
        sum[1][j] = sum[1][j-1] + dp[1][j];
    }
    for(int j = a[1] + 1; j <= k; j++)
    {
        sum[1][j] = sum[1][a[1]];
    }
    
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            if(j <= a[i]) dp[i][j] = (sum[i-1][j])%modul;
            else dp[i][j] = (sum[i-1][j] - sum[i-1][j-a[i]-1])%modul;
            sum[i][j] = (dp[i][j] + sum[i][j-1])%modul;
        }
    }
    if(dp[n][k] < 0) dp[n][k] += modul;
    cout <<dp[n][k];
    
    
    
    return 0;
}

Measured memory_bytes: 159232
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  rep(i, n) cin >> p[i];
  int ans = 0;
  int m = INF;
  rep(i, n) {
    m = min(m, p[i]);
    if(m >= p[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}

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

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

using namespace std;

int main(){
	string s,t; cin>>s>>t;
	rep(i,1000) if(i*i==stoi(s+t)) { cout<<"Yes"<<endl; return 0; }
	cout<<"No"<<endl;
	return 0;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef pair<ll, ll> pint;
ll inf = 1000000000 + 7;

//bool operator< (pint a, pint b) {
	//return a.second < b.second;

//}



ll gcd(ll a, ll b) {

	if (b == 0)
		return a;

	return gcd(b, a % b);


}

ll max(ll a, ll b) {
	if (a < b) {
		return b;
	}
	else
		return a;

}

ll min(ll a, ll b) {
	if (a < b)
		return a;

	return b;
}




ll pow(ll a, ll b) {


	if (b == 0) return 1;

	if (a % 2 == 1) {
		a * pow(a, b - 1);
	}
	else {
		ll ret = pow(a, b / 2);
		return ret * ret;
	}
}









vector<pint> a;
vector<ll> diff_m;

ll A[100005], B[100005];
int main() {
	ll N, K;
	

	cin >> N;

	
	ll ans = 0;
	ll sum_A = 0, sum_B = 0;
	ll sum_m  =0;

	rep(i, N)
		cin >> A[i];

	rep(i, N)
		cin >> B[i];



	rep(i, N) {
		

		if (A[i] - B[i] < 0) {
			sum_m += B[i] - A[i];
			ans += 1;
		}
		else if(A[i] - B[i] > 0)
			diff_m.push_back(A[i] - B[i]);

		sum_A += A[i];
		sum_B += B[i];
		
	
	}



	if (sum_B > sum_A) {
		cout << -1 << endl;
		return 0;
	}




	sort(diff_m.begin(), diff_m.end());
	
	ll sum = 0;

	if (sum_m != 0) {
		rep(i, diff_m.size()) {

			sum += diff_m[diff_m.size() - i - 1];
			ans += 1;
			if (sum >= sum_m) {
				break;
			}

		}

	}


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

Measured memory_bytes: 2428