akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <utility>
#include <climits>
#include <iomanip>
using namespace std;
#define MAXSIZE 100005
#define MAXL 100
#define MOD 998244353
typedef long long int lli;

void swap(lli &a, lli &b);

int main(){
    lli a, b;
    cin >> a >> b;
    if(a < b) swap(a, b);

    lli ans = a / __gcd(a, b) * b;
    cout << ans << endl;
    return 0;
}

void swap(lli &a, lli &b){
    lli tmp = a;
    a = b;
    b = tmp;
}

Measured memory_bytes: 256
a,b= map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
ar.append(a+ar[0])
count = 0
mx = 0
for i in range(len(ar)-1):
    count += ar[i+1] - ar[i]
    if mx < ar[i+1] - ar[i]:
        mx = ar[i+1] - ar[i]
print(count - mx)

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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define debug_print(var) cerr << #var << "=" << var <<endl;
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "
#define fi first
#define se second

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

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

ll modinv(ll a, ll mod){
  ll b=mod, u=1, v=0;
  while(b){
    ll t=a/b;
    a-=t*b; swap(a, b);
    u-=t*v; swap(u, v);
  }
  u%=mod;
  if(u<0)u+=mod;
  return u;
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}
/**************************************
** A main function starts from here  **
***************************************/
int main(){
  string S;
  cin >> S;
  if(S[S.size()-1]=='s'){
    cout << S+"es";
  }else{
    cout << S+"s";
  }
  
  return 0;
}


Measured memory_bytes: 3468
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public string A;
        public int[] C;
        public void Run()
        {
            A = Console.ReadLine();
            C = new int[26];
            long L = A.Length;

            for (int i = 0; i < L; i++)
            {
                int c = A[i] - 'a';
                C[c]++;
            }
        
            long ret = L * (L - 1) / 2 + 1;

            for (int c = 0; c < 26; c++)
            {
                long x = C[c];
                ret -= x * (x - 1) / 2;
            }

            Console.WriteLine(ret);

        }
    }

    // libs ----------
    

    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();            
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }
    
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

Measured memory_bytes: 13112
#include <bits/stdc++.h>
#define PRECISION(x) cout << fixed << setprecision(x); 
#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(i,n) for (int i = 0; i < n; ++i)
#define DO(X) while(X--)
#define DRI(X) int (X); cin >> X
#define DRII(X, Y) int X, Y; cin >> X >> Y
#define DRIII(X, Y, Z) int X, Y, Z; cin >> X >> Y >> Z
#define read(X) for(int &ele : (X)) cin >> ele
#define readI(X) for(int idx = 1; idx < SZ((X)); ++idx) cin >> (X)[idx]
#define debug(x) cerr << '>' << #x << ':' << x << endl
#define MP make_pair
#define PB push_back
#define F first
#define S second

using namespace std;
typedef long long LL;
const int INF = 1<<29;
inline int in() { int x; cin >> x; return x; }
template<class T> void max_self(T & a, const T & b) { if(a < b) a = b; }
template<class T> void min_self(T & a, const T & b) { if(a > b) a = b; }

int main(){
	FAST_IO 
	LL taka, aoki, K; cin >> taka >> aoki >> K;
	LL takaS = min(taka, K);
	taka -= takaS;
	K -= takaS;
	aoki = max(0LL, aoki - K);
	cout << taka << " " << aoki << "\n";
	return 0;
}

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

int main() {
  long long num;
  string str;
  cin >> num;
  int one = 0;
  int kurisage = 0;
  int other = 0;
  
  num++;
  str = to_string(num);
  int len = str.size();
  
  int cnt;
  
  one = stoi(str.substr(0,1)) - 1;
  other = (len - 1) * 9;
  cout << one + other;  
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iomanip>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

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;}
int l[10];

// dp[i] := 長さiの丈を作るのに必要な最小MP
int dp[1010];
const int INF = 1e9;
int n, A, B, C;  

ll dfs(int cur,int a, int b, int c){
  if(cur == n){
    if(min(min(a, b), c) > 0){
      return abs(a-A)+abs(b-B)+abs(c-C)-30;
    }
    else return INF;
  }
  ll ret0 = dfs(cur+1, a, b, c);
  ll ret1 = dfs(cur+1, a+l[cur], b, c)+10;
  ll ret2 = dfs(cur+1, a, b+l[cur], c)+10;
  ll ret3 = dfs(cur+1, a, b, c+l[cur])+10;
  return min(min(ret0, ret1), min(ret2, ret3));
}

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

  cin >> n;
  cin >> A >> B >> C;
  REP(i, n) cin >> l[i];

  cout << dfs(0, 0, 0, 0) << endl; 
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<bitset>
using namespace std;
int main()
{
    bitset<64>  b(0);
  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int t,x=-1;
    cin>>t;
    if(t<4) cin>>x;
    if(t==0) cout<<b[x]<<endl;
    if(t==1) b.set(x);
    if(t==2) b.reset(x);
    if(t==3) b.flip(x);
    if(t==4) cout<<b.all()<<endl;
    if(t==5) cout<<b.any()<<endl;
    if(t==6) cout<<b.none()<<endl;
    if(t==7) cout<<b.count()<<endl;
    if(t==8) cout<<b.to_ullong()<<endl;
  }
}


Measured memory_bytes: 3108
import java.awt.Polygon;
import java.awt.geom.Area;
import java.awt.geom.PathIterator;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) throws Exception
	{
		new Main().run();
	}
	
	public void run() throws Exception
	{
		Scanner file = new Scanner(System.in);
		int N = file.nextInt();
		double[] inv = new double[N];
		for(int i = 0;i<N;i++)
		{
			inv[i] = 1/file.nextDouble();
		}
		double sum = 0;
		for(double x:inv)
			sum+=x;
		System.out.println(1/sum);
	}
}


Measured memory_bytes: 23120
#include <cstdio>
using namespace std;

int main() {
  char x, y, b='A';
  while (scanf("%c,%c\n", &x, &y) == 2) {
    if (x==b) b=y;
    else if (y==b) b=x;
  }
  printf("%c\n", b);
  return 0;
}

Measured memory_bytes: 976
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <vector>
#include <fstream>
#include <sstream>
#include <time.h>
#include <queue>
#include <set>
#include <iomanip>
#include <cmath>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)
#define inf 1000000007
#define mod 1000000007
#define x first
#define y second
#define pi acos(-1.0)
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
//#define dprintf(...) 
#define hash _hash
#define next _next
//#define dprintf(...) fprintf(outFile,__VA_ARGS__)
 
#define FOREACH(it,x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define ull unsigned long long
#define ll long long
#define N 200005
 
template <class T,class U>inline void Max(T &a,U b){if(a<b)a=b;}
template <class T,class U>inline void Min(T &a,U b){if(a>b)a=b;}
 
//FILE* outFile;
inline void add(int &a,int b){a+=b;while(a>=mod)a-=mod;}


int pow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*(ll)a%mod;
        a=(ll)a*a%mod;b>>=1;
    }
    return ans;
}

int a[110],cnt[110];
int main(){
    //freopen("1.txt","w",stdout);
    //cout<<setprecision(3)<<fixed;
    int T,i,j,k,n,m=0;
    scanf("%d",&n);
    rep(i,0,n)scanf("%d",&a[i]),cnt[a[i]]++;
    sort(a,a+n);
    int d=a[n-1];
    if(d!=a[n-2]){
        puts("Impossible");return 0;
    }
    cnt[d]-=2;
    rep(i,1,d)cnt[max(i,d-i)]--;
    rep(i,1,d+1)if(cnt[i]<0){puts("Impossible");return 0;}
    int x=d/2;
    if(d&1)x++;
    if(a[0]<x||cnt[a[0]]){puts("Impossible");return 0;}
    puts("Possible");
    return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter

val br = System.`in`.bufferedReader()
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
    val n = readInteger()
    var AC = 0
    var WA = 0
    var TLE = 0
    var RE = 0
    repeat(n) {
        when (br.readLine()) {
            "AC" -> AC++
            "WA" -> WA++
            "TLE" -> TLE++
            else -> RE++
        }
    }
    out.println("AC x $AC")
    out.println("WA x $WA")
    out.println("TLE x $TLE")
    out.println("RE x $RE")
}

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 42876
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val count = Array(128) {0}
    sc.next().forEach { count[it - 'a']++ }
    val isNo = count.any { it % 2 == 1 }
    println(if (isNo) "No" else "Yes")
}

Measured memory_bytes: 31388
h,w=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
ans=0
for _ in range(h):
    for i in map(int,input().split()):
        if i!=-1:
            ans+=c[i][1]
print(ans)

Measured memory_bytes: 9204
#include<iostream>
#include<cstring>
using namespace std;
long long dp[105][100005];
long long knapsack(long long n,long long W,long long wt[],long long pri[])
{
    if(W==0 or n==0)
    {
        return dp[n][W]=0;
    }
    if(dp[n][W]!=-1)
    {
        return dp[n][W];
    }
    if(wt[n-1]<=W)
    {
        return dp[n][W]=max(pri[n-1]+knapsack(n-1,W-wt[n-1],wt,pri),knapsack(n-1,W,wt,pri));
    }
    else
    {
        return dp[n][W]=knapsack(n-1,W,wt,pri);
    }
}
int main()
{
    long long n,i,W;
    cin>>n>>W;
    long long wt[n];
    long long price[n];
    for(i=0;i<n;i++)
    {
        cin>>wt[i];
        cin>>price[i];
    }
    memset(dp,-1,sizeof dp);
    cout<<knapsack(n,W,wt,price)<<endl;
    return 0;
}


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

using namespace std;

int vocToNum(char s)
{
	char voc[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
	for (int i = 0; i < 26; i++) {
		if (s == voc[i]) {
			return i;
		}
	}
}

void printStr(string str, int n)
{
	for (int i = 0; i < n; i++) {
		cout << str[i];
	}
}

int main(void)
{
	char voc[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
	int vocFlag[26] = { 0 };
	string str;
	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		vocFlag[vocToNum(str[i])] = 1;
	}
	for (int i = 0; i < 26; i++) {
		if (vocFlag[i] == 0) {
			cout << str << voc[i] << endl;
			return 0;
		}
	}
	for (int i = str.length() - 1; i >= 0; i--) {

		for (int j = vocToNum(str[i]) + 1; j < 26; j++) {
			if (vocFlag[j] == 0) {
				printStr(str, i);
				cout << voc[j] << endl;;
				return 0;
			}
		}
		vocFlag[vocToNum(str[i])] = 0;
	}
	cout << -1 << endl;
	return 0;
}


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

using ll = long long;

int main() {
    int n, W; cin >> n >> W;
    vector<int> w(n), v(n);
    for(int i = 0; i < n; ++i) {
        cin >> w[i] >> v[i];
    }

    vector<ll> dp(W + 1);
    for(int i = 0; i < n; ++i) {
        for(int j = W - w[i]; j >= 0; --j) {
            dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]);
        }
    }

    cout << dp[W] << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
// atoi : atoi(変数名.c_str())
// to_string(数値)
// %0桁数d とすると表示桁数が「桁数」に満たない場合に0埋めされる
// find(): int i = 変数名.find(“文字列”) 何番目にあるかを得る
// cout << (条件 ? "Yes" : "No") << endl;
// printf("%02d:%02d:%02d",hour,minute,second);
// 降順 sort(a.begin(),a.end(),greater<int>());
// bitset<ビット数> 変数名;  // すべてのビットが0の状態で初期化される
// bitset<ビット数> 変数名("ビット列");  // 指定したビット列で初期化される
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
#define fix10 cout << fixed << setprecision(10);
#define rep(i,n) for(int i=0; i<(int)(n);i++)

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if(a == b) cout << c << endl;
  else if(a == c) cout << b << endl;
  else cout << a << endl;
}


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

int count=0;

void mergeSort(int A[],int left,int right){
  int i,mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}



void merge(int A[],int left,int mid,int right){
  int n1,n2,i,j,k;
  int *L,*R;
  n1=mid-left;
  n2=right-mid;
  L=(int *)malloc(sizeof(int)*(n1+1));
  R=(int *)malloc(sizeof(int)*(n2+1));
  for(i=0;i<=n1-1;i++){
    L[i]=A[left+i];
  }
  for(j=0;j<=n2-1;j++){
    R[j]=A[mid+j];
  }
  L[n1]=1000000000;
  R[n2]=1000000000;
  i=0;
  j=0;
  for(k=left;k<=right-1;k++){
   if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
      count++;
    }
    else{
      A[k]=R[j];
      j++;
      count++;
    }
  }
  free(L);
  free(R);
}

int main(){

    int N;
    scanf("%d", &N);

    int d[N];
    for (int i = 0; i < N; i++){
        scanf("%d", &d[i]);
    }

    mergeSort(d, 0, N);

    int ans = 0;

    if(d[N/2 - 1] != d[N/2]){
        ans = d[N / 2] - d[N / 2 - 1];
    }

    printf("%d", ans);

    return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=205,M=3e4,inf=1e8;
int n,m,i,j,S,T;
int et,he[N];
struct edge{int l,to,flow;}e[M];
char get(){
	char c=getchar();
	for (;c!='.'&&c!='o'&&c!='S'&&c!='T';c=getchar());
	return c;
}
void line(int x,int y,int flow){
	e[++et].l=he[x];he[x]=et;
	e[et].to=y;e[et].flow=flow;
}
void add(int x,int y,int flow){
	line(x,y,flow);line(y,x,flow);
}
int h,t,q[N],d[N];
bool build(){
	for (int i=1;i<=T;i++) d[i]=0;
	h=0;q[t=1]=S;d[S]=1;
	while (h!=t) for (int x=q[++h],y,i=he[x];i;i=e[i].l)
		if (e[i].flow&&!d[y=e[i].to]){
			d[y]=d[x]+1,q[++t]=y;if (y==T) return 1;
		}
	return 0;
}
int dfs(int x,int flow){
	if (x==T) return flow;
	int rest=flow,use,i,y;
	for (i=he[x];i&&rest;i=e[i].l) if (e[i].flow&&
 		d[y=e[i].to]==d[x]+1&&(use=dfs(y,min(rest,e[i].flow))))
			e[i].flow-=use,e[i^1].flow+=use,rest-=use;
	if (rest==flow) d[x]=0;return flow-rest;
}
int dinic(){
	int res=0;
	while (build()) res+=dfs(S,inf);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);S=n+m+1;T=S+1;et=1;
	for (i=1;i<=n;i++) for (j=1;j<=m;j++){
		char c=get();
		if (c=='o') add(i,j+n,1);
		if (c=='S') line(S,i,inf),et++,add(i,j+n,inf);
		if (c=='T') line(i,T,inf),et++,add(i,j+n,inf);
	}
	int ans=dinic();
	if (ans>=inf) puts("-1"); else printf("%d",ans);
}

Measured memory_bytes: 384
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)
def debug(x):
    print(x,file=sys.stderr)
def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())


"""
"""

#solution:
#繰り返し自乗法だよ
#これはnのp乗をmで割ったあまりをだすよ
def modular_w_binary_method (n,m,p):
    ans=1 if n>0 else 0
    while(p>0):
        if p%2==1:
            ans=(ans*n)%m
        n=(n**2)%m
        p//=2
    return ans

#mod上でのaの逆元を出すよ
"""
    フェルマーの小定理より a**(p)%p==a isTrue
    これを利用すれば a**(p-2)%p==a**(-1) isTrue
    元と逆元とをかけてpで割れば1が余るよ！
"""
def modular_inverse(a,prime):
    return(modular_w_binary_method(a,prime,prime-2))


#逆元を使うと容易に頑張れるｃ
def conbination(n,a,mod=10**9+7):
    #cはイラない
    res=1 
    for s in range(a):
        res=(res*(n-s)*(modular_inverse(s+1,mod)))%mod

        
    return res
#操作から作れるものの組み合わせは何個かー＞同じものでも違う方法で構成できるかから考える方法もある
        
#input
def resolve():
    a,b=pin()
    print(["Odd","Even"][(a*b+1)%2])
    return
    #print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
#if __name__=="__main__":resolve()
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 4"""
        output = """Even"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1 21"""
        output = """Odd"""
        self.assertIO(input, output)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 83820
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	ps := make([]Pair, n)
	var x, y int
	for i := 0; i < n; i++ {
		fmt.Scan(&x, &y)
		ps[i] = Pair{x, y}
	}

	mx := 0
	for i := 1; i < n; i++ {
		p := ps[0].x - ps[i].x
		q := ps[0].y - ps[i].y
		cnt := 0
		for j := 0; j < n; j++ {
			a := ps[j]
			for k := 0; k < n; k++ {
				b := ps[k]
				if j == k {
					continue
				}
				if a.x-b.x == p && a.y-b.y == q {
					cnt++
				}
			}
		}
		if mx < cnt {
			mx = cnt
		}
	}

	fmt.Println(n - mx)
}

// Pair .
type Pair struct {
	x, y int
}


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

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

    string n;
    cin >> n;
    // output wil either be 10101.. or 01010..
    //string a = ""; string b = "";

    int aCnt = 0; int bCnt = 0;
    // a is 1 in odd, b is 1 in even;
    for(int i = 0; i < n.size(); i++){
        if(i % 2 == 0){
            if(n[i] == '1'){
                bCnt++;
            } else {
                aCnt++;
            }
        } else {
            if(n[i] == '0'){
                bCnt++;
            } else {
                aCnt++;
            }
        }
    }
    //cout << aCnt << " . " << bCnt << endl;
    int result = 0;
    if(aCnt > bCnt){
        result = bCnt;
    } else {
        result = aCnt;
    }
    cout << result;
    return 0;
}


Measured memory_bytes: 512
#!/usr/bin/env python3
import sys


def f(B, d):
    '''
    >>> f(6, 0) # 1, 3, 5
    3
    >>> f(6, 1) # 2, 3, 6
    3
    >>> f(6, 2) # 4, 5, 6
    3
    >>> f(6, 3)
    0
    '''
    r = 2**(d+1)
    rr = 2 ** d
    return B // r * rr + max(B % r - rr + 1, 0)
    
def g(A, B, d):
    '''
    >>> g(0, 6, 0) # 1, 3, 5
    3
    >>> g(0, 6, 1) # 2, 3, 6
    3
    >>> g(0, 6, 2) # 4, 5, 6
    3
    >>> g(2, 6, 0) # 3, 5
    2
    '''
    if A == 0:
        return f(B, d)
    return f(B, d) - f(A-1, d)

def solve(A: int, B: int):
    ans = 0
    for d in range(10000, -1, -1):
        ans <<= 1
        ans += g(A, B, d) % 2
    return ans


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    print(solve(A, B))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()


Measured memory_bytes: 7668
#include<bits/stdc++.h>
#include<string>
#include<cmath>

using namespace std;

#define ll long long int
#define loop(i, n) for (int i = 0; i < n; i++)
#define loops(i, s, n) for (int i = s; i < n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define MOD 1000000007

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;

    map<int,int> m;
    for(int i = 0; i<n-1; i++){
        int x;
        cin>>x;
        m[x]++;
    }
    
    for(int i = 1; i<=n; i++){
        cout<<m[i]<<"\n";
    }

}

Measured memory_bytes: 13044
#include <stdio.h>

int main(){
  char s[10];
  scanf("%s",s);
  if(s[2]==s[3]){
    if(s[4]==s[5]){
      printf("Yes\n");
    }else{
      printf("No\n");
    }
  }else{
    printf("No\n");
  }
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct apple
{
	int k;
	ll ans;
}a[300150];
int cmp(apple A,apple B)
{
	if(A.ans==B.ans)
	{
		return A.k>B.k;
	}
	else
	{
		return A.ans>B.ans;
	}
}
int main()
{
	int x,y,u,v,w;
	scanf("%d%d%d%d%d",&x,&y,&u,&v,&w);
	for(int i=1;i<=u;i++)
	{
		ll n;
		scanf("%lld",&n);
		a[i].ans=n;
		a[i].k=1;
	}
	for(int i=1;i<=v;i++)
	{
		ll n;
		scanf("%lld",&n);
		a[i+u].ans=n;
		a[i+u].k=2;
	}
	for(int i=1;i<=w;i++)
	{
		ll n;
		scanf("%lld",&n);
		a[i+u+v].ans=n;
		a[i+u+v].k=0;
	}
	int o=u+v+w;
	sort(a+1,a+o+1,cmp);
	int num3=0;
	ll res=0;
	ll resl=0;
	for(int i=1;i<=o;i++)
	{
		if(num3>=x+y)
		{
			res+=resl;
			break;
		}
	//	printf("%lld\n",res);
		if(a[i].k==1)
		{
			if(x)
			{
				x--;
				res+=a[i].ans;
			}
		}
		if(a[i].k==2)
		{
			if(y)
			{
				y--;
				res+=a[i].ans;
			}
		}
		if(a[i].k==0)
		{
			num3++;
			resl+=a[i].ans;
		}
	}
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 4992
#include <iostream>
#include <cassert>
#include <limits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <array>
#include <map>
#include <set>
#include <deque>
#include <list>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cstring>
#include <bitset>
#include <stack>
#include <queue>

using namespace std;

void dfs(const vector<vector<int>>& G, int vertex, vector<bool>& visited, vector<int>& degree_of_vertex, vector<int>& distances) {
    visited[vertex] = true;
    for (int v : G[vertex]) {
        distances[v] = max({distances[v], distances[vertex] + 1});
        --degree_of_vertex[v];
        if (degree_of_vertex[v] == 0) {
            dfs(G, v, visited, degree_of_vertex, distances);
        }
    }
}

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

    int N, M;
    cin >> N >> M;

    vector<vector<int>> G(N + 1, vector<int>());
    vector<int> degree_of_vertex(N + 1);
    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        ++degree_of_vertex[y];
    }

    vector<bool> visited(N + 1);
    vector<int> distances(N + 1);
    for (size_t i = 1; i <= N; ++i) {
        if (not visited[i] and degree_of_vertex[i] == 0) {
            dfs(G, i, visited, degree_of_vertex, distances);
        }
    }
    cout << *max_element(distances.begin(), distances.end());
}


Measured memory_bytes: 14336
// g++ .cpp && ./a.out
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

typedef pair<int, int> p;
typedef long long ll;

const int mod = 1000000007;
const int inf = 1000000007;

int main() {
  int n;
  cin >> n;
  int pay = 1000;
  while (pay < n) {
    pay += 1000;
  }
  cout << pay - n << endl;
}


Measured memory_bytes: 3560
//submitted by HimJ
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define fr(i,s,e) for(i=s;i<e;i++)
#define ms(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
int main(){
  int t=1;
  //cin>>t;
    while(t--){
            int a,b,c;
            cin>>a>>b>>c;
            c=a*b;
            if(c&1)
                cout<<"Odd";
            else
                cout<<"Even";
    

  }
  return 0;
  }



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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

int main(){
    string s;
    cin >> s;
    sort(all(s));
    if (s[0] == s[1] && s[1] != s[2] && s[2] == s[3]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3612
N = gets.chomp.to_i
H = gets.chomp.split.map(&:to_i)

count = 0
H.each_with_index do |h, i|
  if i == 0
    count += 1
    next
  end
  (0..i).each do |j|
    break if H[j] > H[i]
    count += 1 if i == j
  end
end

puts count

Measured memory_bytes: 1788
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

// ここまで

use std::collections::HashMap;
use std::cmp::min;

fn calc(l: usize, r: usize, x: u64, y: u64, a: &Vec<u64>, mut memo: &mut HashMap<(usize, usize, u64, u64), u64>) -> u64 {
    if l > r {
        return 0;
    }
    if let Some(&v) = memo.get(&(l, r, x, y)) {
        return v;
    }
    let mut ans = 1_000_000_000_000_000_000;
    for i in l..(r + 1) {
        let mut v = a[i] * (x + y);
        v += calc(l, i - 1, x, x + y, &a, &mut memo);
        v += calc(i + 1, r, x + y, y, &a, &mut memo);
        ans = min(ans, v);
    }
    memo.insert((l, r, x, y), ans);
    ans
}

fn run() {
    input! {
        n: usize,
        a: [u64; n],
    }
    let mut memo = HashMap::new();
    let ans = calc(1, n - 2, 1, 1, &a, &mut memo) + a[0] + a[n - 1];
    println!("{}", ans);
}

fn main() {
    run();
}


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

int main(){
  string str;
  int ab[26]={0};

  while(getline(cin,str)){
    for(int i=0;i<str.size();i++){
      if(str[i]>='a'&&str[i]<='z')
        ab[str[i]-'a']++;
      else if(str[i]>='A'&&str[i]<='Z')
        ab[str[i]-'A']++;
    }
  }
  for(int i=0;i<26;i++){
    cout << (char)('a' + i) << " : " << ab[i] << endl;
  }
}



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

int main() 
{
    string S;
    cin >> S;
    
    for (int i = 1; i <= S.length(); i++) {
        if (i % 2 == 1) {
            if (S.at(i-1) == 'L') {
                cout << "No" << endl;
                return 0;
            }
        }else{
            if (S.at(i-1) == 'R') {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

const ll MOD = 1000000007;
const long double EPS = 1e-10;
const int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    ll n,m;
    cin >> n >> m;

    vector<ll> a(n);
    for(int i=0;i<n;++i){
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    vector<Pll> bc(m);
    for(int i=0;i<m;++i){
        cin >> bc[i].second >> bc[i].first;
    }
    sort(bc.rbegin(), bc.rend());

    ll ans = 0;
    int j = 0;
    for(int i=0;i<n;++i) {
        if(j == m || bc[j].first <= a[i]) {
            ans += a[i];
        } else {
            ans += bc[j].first;
            --bc[j].second;
            if(bc[j].second == 0) ++j;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 2560
def areDistinct(arr) : 
  
    n = len(arr) 
    s = set() 
    for i in range(0, n):  
        s.add(arr[i]) 
    return (len(s) == len(arr)) 
N = int(input())
S =  [int(x) for x in input().split()]
  
if (areDistinct(S)):  
    print("YES") 
  
else :  
    print("NO")

Measured memory_bytes: 25936
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 0x7fffffff;
const ll LINF = 0x7fffffffffffffff;
const int maxn = 1e6;
const int modn = 1e9 + 7;



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

	int n,k;
	string s;
	cin>>n>>k>>s;
	for (int i=0;i<n;++i){
        if (i!=k-1)
            printf("%c",s[i]);
        else
            printf("%c",s[i]+32);
	}
	cout<<endl;

	return 0;
}


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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define toRad(deg) (deg*M_PI/180.0)
#define EPS (1e-5)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
// 0.001
int main() {
  double d;
  cin >> d;
  double maxi = d;
  maxi = max(maxi,sqrt(2.0)*d);
  REP(_x,1,10) {
    double x = _x;
    if( equals(x,d) || x < d ) {
      double y = max(1.0,sqrt(d*d-x*x));
      maxi = max(maxi,x+y);
    }
  }
  printf("%.10f\n",maxi);
  return 0;
}

Measured memory_bytes: 1236
/* Generated by powerful Codeforces Tool
 * You can download the binary file in here https://github.com/xalanq/cf-tool (win, osx, linux)
 * Author: step_by_step
 * Time: 2020-03-19 17:35:03
**/

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
  
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <assert.h>
#include <memory.h>
#include <time.h>
#include <bitset>

#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define rank qwertyuio
#define next dfghjk
#define prev fhsgfhjf
#define plus fsghsf
#define minus ytryr
  
using namespace std;
  
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
  
const int N = 10;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
//const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MOD = 998244353;
const ld eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    //ll TL = 10.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    int n, m;
    cin >> n >> m;
    cout << n * (n - 1) / 2 + m * (m - 1) / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
from fractions import gcd

def solve(a, b, c, d):
    if d < b: return False
    g = gcd(d, b)
    a, ar = divmod(a, g)
    c, cr = divmod(c, g)
    d /= g
    b /= g
    if ar > cr: c -= 1
    if a < b: return False
    return c >= b - 1

for cas in xrange(input()):
    print 'Yes' if solve(*map(int, raw_input().split())) else 'No'


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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    int a,b,c,k; cin >> a >> b >> c >> k;
    int m = max(a,max(b,c));
    cout << (m << k) + a+b+c-m<< endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define ll long long
#define PL pair<long long, long long>
#define P pair<int,int>
#define mk make_pair
#define en endl;
#define WHITE 0
#define BLACK 2
#define GRAY 1
#define RE return 0;


int main(){
  int a,b;
  cin>>a>>b;
  int c;
  if(a<=b) c=a;
  else c=a-1;
  cout<<c<<en
}

Measured memory_bytes: 256
/*


*/
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 500000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=2e5+5;

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now;
}

int main()
{
	int n=read(); LL f[5]={0};
	for(int i=1; i<=n; ++i)
	{
		int ai=read();
		LL mn=f[0]; f[0]=f[0]+ai;
		mn=std::min(mn,f[1]), f[1]=mn+(ai?ai&1:2);
		mn=std::min(mn,f[2]), f[2]=mn+(ai?ai+1&1:1);
		mn=std::min(mn,f[3]), f[3]=mn+(ai?ai&1:2);
		mn=std::min(mn,f[4]), f[4]=mn+ai;
	}
	printf("%lld\n",std::min(f[2],std::min(f[3],f[4])));

	return 0;
}

Measured memory_bytes: 640
def factorize(n):
  fct=[]
  b,e=2,0
  while b*b<=n:
    while n%b==0:
      n=n//b
      e+=1
    if e>0:
      fct.append(e)
    b,e=b+1,0
  if n>1:
    fct.append(1)
  return fct

n=int(input())
ans=0
for i in factorize(n):
  count=1
  while i>=count:
    ans+=1
    i-=count
    count+=1
print(ans)

Measured memory_bytes: 9120
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int N;
int A[200005];
int table[1000005];

int main(){

	for(int i = 1; i <= 1000000; i++){

		table[i] = 0;
	}

	scanf("%d",&N);

	for(int i = 0; i < N; i++){

		scanf("%d",&A[i]);
		table[A[i]]++;
	}

	if(table[1] > 0){

		if(table[1] == 1){

			printf("1\n");
		}else{

			printf("0\n");
		}

		return 0;
	}

	int ans = 0;

	for(int i = 0; i < N; i++){
		if(table[A[i]] > 1)continue;

		bool FLG = true;
		for(int k = 2; k*k <= A[i]; k++){
			if(A[i]%k != 0)continue;
			if(table[k] > 0 || table[A[i]/k] > 0){

				FLG = false;
				break;
			}
		}
		if(FLG){

			ans++;
		}
	}

	printf("%d\n",ans);

	return 0;
}


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

#define watch(x) cerr << (#x) << ": " << (x) << endl

typedef long long LL;

const int N = 1000007;
int n;
string s[N];

struct bseq {
    int tot, mx;

    bseq(int _t, int _m) {
        tot = _t; mx = _m;
    }

    bool operator<(const bseq& other) const {
        if(mx != other.mx) return mx < other.mx;
        return tot > other.tot;
    }
};

vector<bseq> open, closed;

bool verify(vector<bseq>& vb) {
    int cur = 0;
    for(bseq b : vb) {
        if(b.mx > cur) return false;

        cur += b.tot;
    }
    return true;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    int overall = 0;
    for(int i = 0; i < n; ++i) {
        bseq b(0, 0);
        for(char c : s[i]) {
            if(c == '(') {
                b.tot++;
            } else {
                b.tot--;
            }
        }
        if(b.tot < 0) {
            reverse(s[i].begin(), s[i].end());
            for(char& c : s[i]) {
                if(c == '(') c = ')';
                else c = '(';
            }
        }

        int tmp = 0;
        for(char c : s[i]) {
            if(c == '(') tmp--;
            else tmp++;

            b.mx = max(b.mx, tmp);
        }

        overall += b.tot;
        
        if(b.tot > 0) {
            open.push_back(b);
        } else {
            b.tot = -b.tot;
            closed.push_back(b);
        }
    }

    sort(open.begin(), open.end());
    sort(closed.begin(), closed.end());

    if(overall == 0 && verify(open) && verify(closed)) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    
    return 0;
}


Measured memory_bytes: 42436
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007




class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n


    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def same(self, x, y):
        return self._root(x) == self._root(y)


    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2



n, m = LI()
p = LI()
U = UnionFind(n)
for x, y in LIR(m):
    U.union(x-1, y-1)


cnt = 0
for i in range(n):
    cnt += U.same(i, p[i]-1)



print(cnt)

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

using namespace std;

int main(void) {
  int n;
  cin >> n;

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

  vector<int> b(1, 0);
  int l = 0, r = 0;
  while (l < n) {
    while (r + 1 < n && a[r] != a[r + 1]) r++;
    b.push_back(r - l + 1);
    l = ++r;
  }
  b.push_back(0);

  int ans = 0;
  for (int i = 0; i + 2 < b.size(); i++) {
    ans = max(ans, b[i] + b[i + 1] + b[i + 2]);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3524
#include<stdio.h>
#include<math.h>
using namespace std;
int main(){
	int a,b,f;
	float c;
	scanf("%d %d %f",&a,&b,&c);
	float d[a],e=1000;
	for(int i=0;i<a;i++){
		scanf("%f",&d[i]);
		d[i]=b-d[i]*0.006;
	}
	for(int i=0;i<a;i++){
		if(fabsf(d[i]-c)<e){
	e=fabsf(d[i]-c);
	f=i+1;
		}
	}
	printf("%d\n",f);
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int a[9],ans=0,used[10];
void check(){
    int temp,now;
    now=a[0]+a[2]+a[5];
    temp=now/10;
    now%=10;
    if(now!=a[8])return ;
    now=temp+a[1]+a[4];
    temp=now/10;
    now%=10;
    if(now!=a[7])return ;
    now=temp+a[3];
    temp=now/10;
    now%=10;
    if(temp>0)return ;
    if(now!=a[6])return ;
    ans++;
    return ;
}
void dfs(int now){
    if(now>=9)check();
    else{
        if(a[now]==-1){
            for(int i=1;i<10;i++)if(used[i]==0){
                used[i]=1;
                a[now]=i;
                dfs(now+1);
                used[i]=0;
            }
            a[now]=-1;
        }
        else dfs(now+1);
    }
    return ;
}
int main(){
    for(int i=0;i<10;i++)used[i]=0;
    for(int i=0;i<9;i++){
        scanf("%d",&a[i]);
        if(a[i]>0)used[a[i]]++;
    }
    dfs(0);
    printf("%d\n",ans);
}


Measured memory_bytes: 2748
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
 
using namespace std;    
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 	int n,sum=0;
  cin>>n;
  if(n%2==0) cout<<n/2-1<<'\n';
  else cout<<n/2<<'\n';
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int MAX=30000;
vector<ll> prime;
bool isprime[MAX];
void sieve(){
	for(ll i=3; i<MAX; i+=2){
		isprime[i]=1;
	}
	isprime[2]=1;
	prime.push_back(2);
	for(ll i=3; i<MAX; i++){
		if(isprime[i]){
			prime.push_back(i);
			for(ll j=2*i; j<MAX; j+=i){
				isprime[j]=0;
			}
		}
	}
	return;
}
int main()
{
	int n;
	cin>>n;
	sieve();
	ll x[1010];
	for(int i=0; i<n; i++){
		x[i]=prime[i+1];
	}
	ll a[505][505];
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if((i+j)%2==0){
				if(j<n/2) a[i][j]=x[(n-1+i-j)/2]*x[(i+j)/2];
				else a[i][j]=2*x[(n-1+i-j)/2]*x[(i+j)/2];
			}else{
				if(j<n/2) a[i][j]=1+2*x[(n-1+i-j-1)/2]*x[(n-1+i-j+1)/2]*x[(i+j-1)/2]*x[(i+j+1)/2];
				else a[i][j]=1+4*x[(n-1+i-j-1)/2]*x[(n-1+i-j+1)/2]*x[(i+j-1)/2]*x[(i+j+1)/2];
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 4992
#include <stdio.h>

using namespace std;

int main(){
	int n,m,l;
	scanf("%d %d %d",&n,&m,&l);
	int A[n][m],B[m][l];
	long long int C[n][l];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < l; j++){
			C[i][j] = 0;
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			scanf("%d",&A[i][j]);
		}
	}
	for(int i = 0; i < m; i++){
		for(int j = 0; j < l; j++){
			scanf("%d",&B[i][j]);
		}
	}

	for(int i = 0; i < n; i++){
		for(int k = 0; k < l; k++){
			for(int j = 0; j < m; j++){
				C[i][k] += A[i][j]*B[j][k];
			}
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < l-1; j++){
			printf("%lld ",C[i][j]);
		}
		printf("%lld\n",C[i][l-1]);
	}
}



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

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int temp;
    long long ans = 0;
    for (int i = 1; i < n; ++i) {
        temp = sqrt(n - i) + 1;
        for (int j = 1; j < temp; ++j) {
            if ((n - i) % j == 0) {
                ans += 2;
                if ((n - i) / j == j) {
                    --ans;
                }
            }
        }
    }
    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 3816
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long int n, d;
    cin >> n >> d;
    long long int x[n], y[n];
    int ans = 0;
    for (int i = 0; i < n; ++i){cin >> x[i] >> y[i];}
    for (int i = 0; i < n; ++i){
        if(x[i]*x[i]+y[i]*y[i] <= d*d){
            ++ans;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 6764