akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using P = pair<ll,ll>;
using um = unordered_map<char,ll>;
#define fl cout<<flush;
#define endl '\n'
template <typename T> inline void prt(T v){cout<<v<<'\n';}
template <typename T> inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> inline bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ld pi=3.14159265358979323846;
const ld eps=1e-10;

#define debug(v) cout<<#v<<": ",prt(v);
template <typename A,typename B>
inline void prt(pair<A,B> p){cout<<"("<<p.first<<", "<<p.second<<")\n";}
template <typename A,typename B,typename C>
inline void prt(tuple<A,B,C> p){cout<<"("<<get<0>(p)<<", "<<get<1>(p)<<", "<<get<2>(p)<<")\n";}
inline void prt(bool p){if(p)cout<<"True"<<'\n';else cout<<"False"<<'\n';}
template <typename T> 
inline void prt(vector<T> v){cout<<'{';for(ll i=0;i<v.size();i++){cout<<v[i];if(i<v.size()-1)cout<<", ";}cout<<'}'<<'\n';}
template <typename T> 
inline void prt(deque<T> v){cout<<'{';for(ll i=0;i<v.size();i++){cout<<v[i];if(i<v.size()-1)cout<<", ";}cout<<'}'<<'\n';}
template <typename A,typename B>
inline void prt(map<A,B> v){cout<<'{';ll c=0;for(auto &p: v){cout<<p.first<<":"<<p.second;c++;if(c!=v.size())cout<<", ";}cout<<'}'<<'\n';}
template <typename A,typename B>
inline void prt(unordered_map<A,B> v){cout<<'{';ll c=0;for(auto &p: v){cout<<p.first<<":"<<p.second;c++;if(c!=v.size())cout<<", ";}cout<<'}'<<'\n';}
template <typename T> 
inline void prt(set<T> v){cout<<'{';for(auto i=v.begin();i!=v.end();i++){cout<<*i;if(i!=--v.end())cout<<", ";}cout<<'}'<<'\n';}
template <typename T> 
inline void prt(multiset<T> v){cout<<'{';for(auto i=v.begin();i!=v.end();i++){cout<<*i;if(i!=--v.end())cout<<", ";}cout<<'}'<<'\n';}

signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    string S;
    cin >> S;
    set<ll> wall;
    um M;
    for(ll i=0;i<N;++i){
        M[S[i]]++;
    }
    ll ans=1;
    for(auto p: M){
        ans*=p.second+1;
        ans%=MOD;
    }
    prt((ans+MOD-1)%MOD);fl


    return 0;
}



Measured memory_bytes: 3736
import math

n = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def main(divisors, o):
    for i in range(o):
        a = divisors[i]
        b = divisors[::-1][i]
        
        if a <= 9 and b <= 9:
            return 'Yes'
    return 'No'


divs = make_divisors(n)

o = int(len(divs)/2 + len(divs) % 2)

print(main(divs, o))


Measured memory_bytes: 38384
q, h, s, d = map(int, input().split())
n = int(input())

q_l, h_l, s_l = q*4, h*2, s
l = min(q_l, h_l, s_l)
q_2l, h_2l, s_2l, d_2l = q*8, h*4, s*2, d
l2 = min(q_2l, h_2l, s_2l, d_2l)

if n % 2 == 0:
    ans = l2 * (n//2)
else:
    ans = l2 * (n//2) + l * 1
print(ans)

Measured memory_bytes: 3064
a,b,c,x,y=map(int, input().split())

ans=0

if a+b>2*c:
    ans+=2*c*min(x,y)
else:
    ans+=a*x+b*y
    print(ans)
    exit()

if x>y:
    if a>2*c:
        ans+=c*2*(x-y)
    else:
        ans+=a*(x-y)
elif x<y:
    if b>2*c:
        ans+=c*2*(y-x)
    else:
        ans+=b*(y-x)

print(ans)




Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
//int a,b;
double o=1.000000000;
double t=2.000000000;
double z=0.00000;
double n,m,d;
cin>>n>>m>>d;
double an=(t*(n-d)*(m-o))/n;
an/=n;
if(d==z){
an/=t;
	
}
printf("%.9f",an);


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define ll long long
#define f first
#define s second
#define int long long
#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define debug(x) cout << "DEBUG " << x << endl
#define debug2(x, y) cout << "DEBUG " << x << " " << y << endl
#define debug3(x, y, z) cout << "DEBUG " << x << " " << y << " " << z<< endl
#define debug4(x, y, z, o) cout << "DEBUG " << x << " " << y << " " << z<< " " << o << endl
using namespace std;
typedef pair<ll, ll> pii;
typedef vector<vector<ll>> mat;
const ll mod = 1e9+7;
const int MAXN = 1e6+5;

int l[MAXN], mx[MAXN];

void crivo() {
	for(int i = 2; i < MAXN; i++)
		if(l[i] == -1) {
			l[i] = i;
			for(int j = i+i; j < MAXN; j += i) {
				if(l[j] == -1) l[j] = i;
				else l[j] = min(l[j], i);
			}
		}
}

ll expo(ll a, ll b){
    if(a == 0 or b == 0) 
		return 1;
    ll x = expo(a, b/2);
    return (b & 1 ? ((x*x)%mod*a)%mod : (x*x) % mod);
}

int32_t main() {
  	FAST;
	memset(l, -1, sizeof l);
	crivo();
	
	int n;
	cin >> n;
	vector<int> v(n);
	for(int &i : v)
		cin >> i;


	for(int i = 0; i < n; i++) {
		int xd = v[i];
		while(xd > 1) {
			int p = l[xd];
			int k = 0;
			while(xd % p == 0) {
				xd /= p;
				k++;
			}
			mx[p] = max(mx[p], k);
		}
	}
	ll mmc = 1;
	
	for(int i = 1; i < MAXN; i++)
		mmc = (mmc*expo(i, mx[i]))%mod;
	
	
	
	
	ll sum = 0;
	for(int i = 0; i < n; i++) 
		sum = (sum + (mmc * expo(v[i], mod-2)) % mod)%mod;
	
	cout << sum << endl;
}


Measured memory_bytes: 15744
/*
for (int i = 0; i < N; ++i){}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
 

int main() {
	// 入力
	string S;
	cin >> S;
	ll N = S.length();
	ll A[N];
	for (ll i = 0; i < N; ++i) A[i] = stoi(S.substr(i,1));
 
	// 解法
	ll ans = 1000;
	REP(i,N-2){
		if (abs(A[i]*100+A[i+1]*10+A[i+2]-753)<ans){
			ans = abs(A[i]*100+A[i+1]*10+A[i+2]-753);
		}
	}
	cout << ans << endl;
		
	
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
class sorter {
  int count;
  int *array;
public:
  sorter(int count){
    this->count = count;
    array = new int[count];
  }
  ~sorter(){
    delete [] array;
  }
  void input();
  void output();
  void sort();
};

void sorter::input(){
  for (int i = 0; i < count; i++) {
    cin >> array[i];
  }
}

void sorter::output(){
  for (int i = 0; i < count; i++) {
    cout << array[i];
    if(i < count - 1){
      cout << " ";
    }else{
      cout << endl;
    }
  }
}

void sorter::sort(){
  for (int i = 1; i < count; i++) {
    output();
    int key = array[i];
    int j = i - 1;
    while (j >= 0 && array[j] > key) {
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = key;
  }
  output();
}
int main(int argc, char const *argv[]) {
  int count;
  cin >> count;
  sorter s = sorter(count);
  s.input();
  s.sort();
  return 0;
}

Measured memory_bytes: 3080
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <bitset>

long long mod = 1e9+7;
class Mint {
public:
  long long x;
  Mint(){}; // 引数なしでも定義できるように引数なしコンストラクタも用意しておく
  Mint(long long a){
    x = a%mod;
    while(x<0){
      x += mod;
    }
  };
  Mint& operator += (const Mint &a){
    x+=a.x;
    x%=mod;
    return *this;
  }
  Mint& operator -= (const Mint &a){
    x += (mod - a.x);
    x%=mod;
    return *this;
  }
  Mint& operator *= (const Mint &a){
    x*=a.x;
    x%=mod;
    return *this;
  }

  // a^n mod を計算する
  // Useaeg: Mint z = Mint(2).pow(n);
  Mint pow(long long n) const {
    if (n==0) return Mint(1);
    Mint y = pow(n>>1); // pow(n/2)を計算する
    y *= y;
    if (n%2==1) y *= *this;
    return y;
  }

  // a^{-1} mod を計算する
  Mint modinv(const Mint &a) const {
    return a.pow(mod-2);
  }

  Mint& operator /= (const Mint &a) {
    x *= modinv(a).x;
    x %= mod;
    return *this;
  }

  Mint operator + (Mint &a) const {
    Mint y(*this);
    y += a;
    return y;
  }

  Mint operator - (Mint &a) const {
    Mint y(*this);
    y -= a;
    return y;
  }

  Mint operator * (Mint &a) const {
    Mint y(*this);
    y *= a;
    return y;
  }

  Mint operator / (Mint &a) const {
    Mint y(*this);
    y/=a;
    return y.x;
  }

  // nCk @mod を計算する
  Mint nCk(Mint &n, const long long k) const {
    Mint y = Mint(1);
    Mint one = Mint(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
      y /= (i + one);
    }
    return y;
  }

  // nPk @mod を計算する
  Mint nPk(Mint &n, long long k) const {
    Mint y(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
    }
    return y;
  }
};

struct edge {
  int src;
  int dst;
  int coin;
};
//bool bomb[300004][300004];
int main() {
  int N;
  std::cin >> N;
  std::string S;
  std::cin >> S;
  int Q;
  std::cin >> Q;
  std::vector<int > k(Q);
  for (int i=0; i<Q; i++) {
    std::cin >> k[i];
  }
  for (int i = 0; i < Q; i++)
  {
    int start = 0;
    int end = 0;
    long long ans = 0, cand = 0;
    int Dnum = 0, Mnum = 0;
    for (int end = 0; end < N; end++)
    {
      // printf("end=%d\n", end);
      if (S[end] == 'D')
      {
        Dnum++;
      }
      else if (S[end] == 'M')
      {
        Mnum++;
        cand += Dnum;
      }
      else if (S[end]=='C')
      {
        ans += cand;
      }
      // printf("Dnum=%d, Mnum=%d, cand=%lld, ans=%lld\n", Dnum, Mnum, cand, ans);
      if (end >= k[i] - 1) {
        int del = end - k[i] + 1;
        // printf("del0=%d\n", del);
        if (S[del]=='D') {
          Dnum--;
          cand -= Mnum;
        } else if (S[del]=='M') {
          Mnum--;
        }
      }
    }
    std::cout << ans << std::endl;
  }
  return 0;
}

Measured memory_bytes: 4476
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define M 998244353
#define INF 1e16
typedef long long ll;
typedef pair<int,int> P;
 
ll A(ll x){
    if(x>=0)return x;
    else return -x;
}
 
ll gcd(ll a, ll b) {
	if (b > a) {
		ll tmp = b;
		b = a;
		a = tmp;
	}
	if (a%b == 0)return b;
	else return gcd(b, a%b);
}

struct edge{
	ll to;
	ll cost;
};

vector<edge>g[100];

int main(void){
	ll L;
	cin>>L;
	ll len = 0;
	ll t = L;
	while(t>0){
		len++;
		t/=2;
	}
	ll tmp = 1;
	t = L-(1<<(len-1));
	for(int i=1;i<len;i++){
		g[i].push_back({i+1,0});
		g[i].push_back({i+1,tmp});
		tmp*=2;
	}
	if(t==0){
		cout<<len<<" "<<2*(len-1)<<endl;
		for(int i=1;i<=len;i++){
			for(int j=0;j<g[i].size();j++){
				cout<<i<<" "<<g[i][j].to<<" "<<g[i][j].cost<<endl;
			}
		}
		return 0;
	}
	ll e = 2*(len-1);
	L--;
	for(int i=len-1;i>=1;i--){
		//cout<<L<<endl;
		if(t>=(1<<(i-1))){
			g[i].push_back({len,L-((1<<(i-1))-1)});
			e++;
			L -= (1<<(i-1));
			t-=(1<<(i-1));
		}
	}
	cout<<len<<" "<<e<<endl;
	for(int i=1;i<=len;i++){
		for(int j=0;j<g[i].size();j++){
			cout<<i<<" "<<g[i][j].to<<" "<<g[i][j].cost<<endl;
		}
	}
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include "bits/stdc++.h"
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(i%2==0)
            cout<<s[i];
    }
    cout<<endl;
}

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

string s;
int res = 0;

int main()
{
    cin >> s;
    string lst = string(1, s[0]);
    res++;
    for (int i = 1; i < s.length(); i++)
        if (lst.length() > 1) { res++; lst = string(1, s[i]); }
        else if (lst[0] == s[i])
            if (i + 1 < s.length()) { res++; lst = s.substr(i, 2); i++; }
            else break;
        else { res++; lst = string(1, s[i]); }
    printf("%d\n", res);
    return 0;
}


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

// 小数点以下桁数
// fixed << setprecision(i)

int gcd(int a,int b){return (a%b==0?b:gcd(b, a%b));}
int lcm(int a,int b){return a*b/gcd(a, b);}

int main()
{
  string s;
  int ans = 0, tmp = 0;

  cin >> s;
  for (int i = 0; i < s.size(); i++)
  {
    if (i % 2 == 0)
    {
      if (s[i] == '1')
        ans++;
    }
    else
    {
      if (s[i] == '0')
        ans++;
    }
  }
  for (int i = 0; i < s.size(); i++)
  {
    if (i % 2 == 1)
    {
      if (s[i] == '1')
        tmp++;
    }
    else
    {
      if (s[i] == '0')
        tmp++;
    }
  }
  cout << min(ans, tmp) << endl;
}


Measured memory_bytes: 3760
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int k = Integer.parseInt(br.readLine());
		String[] sa = br.readLine().split(" ");
		int[] a = new int[k];
		for (int i = 0; i < k; i++) {
			a[i] = Integer.parseInt(sa[i]);
		}
		br.close();

		long min = 2;
		long max = 2;
		for (int i = k - 1; i >= 0; i--) {
			long x = min / a[i];
			long y = max / a[i];
			if (x == y && min % a[i] != 0) {
				System.out.println(-1);
				return;
			}
			if (min % a[i] != 0) {
				x++;
			}
			y++;
			min = a[i] * x;
			max = a[i] * y - 1;
		}
		System.out.println(min + " " + max);
	}
}


Measured memory_bytes: 49236
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
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; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define vint vector<int>
#define pri_que priority_queue
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vvchar vector<vector<char>>
#define vchar vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int h,w;cin>>h>>w;
    vstr s(h);
    rep(i,h)cin>>s[i];

    int res=0;
    vvint l(h,vint(w,0)),r(h,vint(w,0)),u(h,vint(w,0)),d(h,vint(w,0));

    //l
    rep(i,h) l[i][0]=(s[i][0]=='#'?0:1);
    rep(i,h){
        range(j,1,w){
            if(s[i][j]=='#') l[i][j]=0;
            else l[i][j]=l[i][j-1]+1;
        }
    }

    //r
    rep(i,h) r[i][w-1]=(s[i][w-1]=='#'?0:1);
    rep(i,h){
        for(int j=w-2; j>=0; j--){
            if(s[i][j]=='#') r[i][j]=0;
            else r[i][j]=r[i][j+1]+1;
        }
    }


    //u
    rep(i,w) u[0][i]=(s[0][i]=='#'?0:1);
    rep(i,w){
        for(int j=1; j<h; j++){
            if(s[j][i]=='#') u[j][i]=0;
            else u[j][i]=u[j-1][i]+1;
        }
    }
    
    //d
    rep(i,w) d[h-1][i]=(s[h-1][i]=='#'?0:1);
    rep(i,w){
        for(int j=h-2; j>=0; j--){
            if(s[j][i]=='#') d[j][i]=0;
            else d[j][i]=d[j+1][i]+1;
        }
    }

    // rep(i,h){
    //     rep(j,w){
    //         cout<<d[i][j];
    //     }
    //     cout<<endl;
    // }
    rep(k,10){
    rep(i,h){
        rep(j,w){
            int tmp=0;
            if(s[i][j]=='.'){
                tmp=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3;
                chmax(res,tmp);
            }
        }
    }
    }
    cout<<res<<endl;
}

Measured memory_bytes: 132804
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int input_time = sc.nextInt();
		int loop_time = 0;
		while(input_time != 0) {
			loop_time++;
			System.out.println("Case " + loop_time + ": " + input_time);
			input_time = sc.nextInt();
		}
	}
}



Measured memory_bytes: 42020
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

if A1 < B1 :
    A1, A2, B1, B2 = B1, B2, A1, A2

def solve() :    
    A = T1 * A1 + T2 * A2
    B = T1 * B1 + T2 * B2
    
    if A == B :
        return 'infinity'
    
    if (A1 > B1 and A > B) or (A1 < B1 and A < B) :
        return 0
    
    D0 = abs(A1 - B1) * T1
    D = abs(A - B)
    
    if D0 % D == 0 :
        return D0 // D * 2
    else :
        return D0 // D * 2 + 1
        
print(solve())


Measured memory_bytes: 38256
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//International Party
public class Main{

	int n, m, INF = 1<<29, min;
	boolean[] u, v, res;
	boolean[][] e;
	
	boolean ok(){
		v = new boolean[m];
		return dfs(0)==m;
	}
	
	int dfs(int k){
		if(v[k])return 0;
		int res = 1;
		v[k] = true;
		for(int i=0;i<n;i++){
			if(!u[i]||!e[k][i])continue;
			for(int j=0;j<m;j++)if(e[j][i])res += dfs(j);
		}
		return res;
	}
	
	void f(int k, int d){
		if(5<d||min<=d)return;
		if(ok()){
			min = d;
			res = u.clone(); return;
		}
		for(int i=k;i<n;i++){
			u[i] = true;
			f(i+1, d+1);
			u[i] = false;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(boolean h = true;;h=false){
			n = sc.nextInt(); m = sc.nextInt();
			if((n|m)==0)break;
			if(!h)System.out.println();
			Map<String, Integer> ref = new HashMap<String, Integer>();
			String[] s = new String[n];
			for(int i=0;i<n;i++){
				s[i] = sc.next();
				ref.put(s[i], i);
			}
			e = new boolean[m][n];
			for(int i=0;i<m;i++){
				int k = sc.nextInt();
				while(k--!=0)e[i][ref.get(sc.next())] = true;
			}
			u = new boolean[n];
			min = INF;
			f(0, 0);
			if(min==INF)System.out.println("Impossible");
			else {
				System.out.println(min);
				for(int i=0;i<n;i++)if(res[i])System.out.println(s[i]);
			}
		}
	}
	
	void debug(Object...o){
//		System.out.println(Arrays.deepToString(o));
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000
N, M = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    UF.union(x, y)
UF.all_find()


ans = 0
for i, p in enumerate(P):
    if UF.same(i, p):
        ans += 1

print(ans)


Measured memory_bytes: 13812
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int W, H, N;
    scanf("%d %d %d", &W, &H, &N);

    const int on = 1;
    const int off = 0;

    vector<int> x;
    vector<int> y;
    vector<int> a;

    for (int i = 0; i < N; i++)
    {
        int tmpx;
        int tmpy;
        int tmpa;
        scanf("%d %d %d", &tmpx, &tmpy, &tmpa);
        x.push_back(tmpx);
        y.push_back(tmpy);
        a.push_back(tmpa);
    }

    vector< vector<int> > vvi;
    vvi.resize(W);

    for (int i = 0; i < W; i++)
    {
        vvi[i].resize(H);
    }

    for (int i = 0; i < W; i++)
        for (int j = 0; j < H; j++) vvi[i][j] = on;

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

        if (a[i] == 1)
        {
            for (j = 0; j < x[i]; j++)
                for (k = 0; k < H; k++) vvi[j][k] = off;
        }
        else if (a[i] == 2)
        {
            for (j = x[i]; j < W; j++)
                for (k = 0; k < H; k++) vvi[j][k] = off;
        }
        else if (a[i] == 3)
        {
            for (j = 0; j < W; j++)
                for (k = 0; k < y[i]; k++) vvi[j][k] = off;
        }
        else
        {
            for (j = 0; j < W; j++)
                for (k = y[i]; k < H; k++) vvi[j][k] = off;
        }
    }

    int ans = 0;
    for (int i = 0; i < W; i++)
        for (int j = 0; j < H; j++) ans += vvi[i][j];

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


Measured memory_bytes: 256
x,n=map(int, input().split())

if n == 0:
    print(x)
    exit()
else:
    p=list(map(int, input().split()))

a = False
x1 = x
while a == False:
    if x1 not in p:
        a = True
        break
    elif x1 in p:
        x1 -= 1

b = False
x2 = x
while b == False:
    if x2 not in p:
        a = True
        break
    elif x2 in p:
        x2 += 1

if abs(x - x1) > abs(x - x2):
    print(x2)
elif abs(x - x1) < abs(x - x2):
    print(x1)
elif abs(x - x1) == abs(x - x2):
    print(x1)


Measured memory_bytes: 9220
N = int(input())
S = input()
lis =[0]
minn =N
for i in range(N):
  if S[i]=="E":
    lis.append(lis[i]+1)
  elif S[i]=="W":
    lis.append(lis[i])
#print(lis)
minn = lis[N]
#print(minn)
for i in range(2,N+1):
#  print("try:{0}".format(i))
#  print((i-1)-lis[i-1]+(lis[N]-lis[i]))
  minn = min(minn,(i-1)-lis[i-1]+(lis[N]-lis[i]))
print(minn)
  

Measured memory_bytes: 15244
//all possible//
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s,q,w,d,e,f,g;
	int a,b,c,i,j;
	vector<string > v,z,h;
	cin>>s;
	a=s.size()-1;
	for(i=0;i<a;i++)
	{
	    q+=s[i];
		if(q.size()%2==0)
		{
			for(j=0;j<q.size()/2;j++)
			w+=q[j];
			for(j=q.size()/2;j<q.size();j++)
			d+=q[j];
			
			if(w==d)
		{
			v.push_back(q);
			w.clear();
			d.clear();
		}
		else
		{
			w.clear();
			d.clear();
		}
		}
		
		
	}
	cout<<v[v.size()-1].size();

    

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e3 + 7;;

int n, m;
int a, b, c, d;

char tt[N][N];
int dis[N][N], vis[N][N];

bool ok(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < m && tt[i][j] == '.';
}

signed main()
{
	IO_OP;
	
	cin >> n >> m >> a >> b >> c >> d;
	a--, b--, c--, d--;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> tt[i][j];
		}
	}
	memset(dis,0x3f, sizeof dis);
	deque<pi> dk;
	dk.PB({a, b});
	vis[a][b] = 1;
	dis[a][b] = 0;
	while(dk.size()) {
		pi u = dk.front(); dk.pop_front();
		int i = u.F, j = u.S;
		for(int ii = i - 2; ii <= i + 2; ii++) {
			for(int jj = j - 2; jj <= j + 2; jj++) {
				if(ii == i && jj == j) continue;
				if(!ok(ii, jj)) continue;
				if(abs(ii-i)+abs(jj-j) == 1) {
					if(dis[i][j] < dis[ii][jj]) {
						dis[ii][jj] = dis[i][j];
						dk.push_front({ii, jj});
						vis[ii][jj] = 1;
					}
				} else {
					if(dis[i][j] + 1 < dis[ii][jj]) {
						dis[ii][jj] = dis[i][j] + 1;
						dk.push_back({ii, jj});
						vis[ii][jj] = 1;
					}
				}
			}
		}
	}

	if(vis[c][d]) {
		cout << dis[c][d] << endl;
	} else {
		cout << -1 << endl;
	}


}





Measured memory_bytes: 12628
from pprint import pprint as pp
"""
問題文
Atcoder国では、郵便番号は A+B+1 文字からなり、A+1 文字目はハイフン -、それ以外の全ての文字は 0 以上 9 以下の数字です。
文字列 S が与えられるので、Atcoder国の郵便番号の形式を満たすかどうか判定してください。
制約
    1≦A,B≦5
    |S|=A+B+1
    S は 0 以上 9 以下の数字、およびハイフン - からなる
S がAtcoder国の郵便番号の形式を満たすならば Yes 、そうでなければ No を出力せよ。
"""
a,b=map(int, input().split())
s=input()

def check(it):
    if len(it) != a+b+1:
        return False
    for e in it[:a]:
        if '0' <= e <= '9':
            pass
        else:
            return False
    for e in it[a+1:]:
        if '0' <= e <= '9':
            pass
        else:
            return False
    if it[a] != '-':
        return False
    return True

if check(s):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3572
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int i, number_r, number_d, current_number;
    number_r = Integer.parseInt(sc.next());
    number_d = Integer.parseInt(sc.next());
    current_number = Integer.parseInt(sc.next());
    for(i = 0; i < 10; i++) {
      current_number = current_number * number_r - number_d;
      System.out.println(current_number);
    }
  }
}


Measured memory_bytes: 21844
dp = 11.times.map{ [0]*1001 }
dp[0][0] = 1
(0..100).each do |i|
  9.downto(0) do |j|
    (0..1000).each do |k|
      break if k+i > 1000
      dp[j+1][k+i] += dp[j][k]
    end
  end
end

loop do
  n, s = gets.split.map(&:to_i)
  break if n == 0
  p dp[n][s]
end

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

using namespace std;

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

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

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

	ll n;
	cin >> n;

	vector<ll> buys;
	buys.emplace_back(1);

	for (ll i = 1; i <= 10; i++) {
		buys.emplace_back(pow(6LL, i));
		buys.emplace_back(pow(9LL, i));
	}

	vector<ll> dp(n + 1, INF64);
	dp[0] = 0;

	for (int i = 0; i < n; i++) {
		for (auto v : buys) {
			if (i + v > n) {
				continue;
			}

			dp[i + v] = min(dp[i + v], dp[i] + 1);
		}
	}

	cout << dp[n] << endl;
	return 0;
}


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

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,S = LI()
    A = [0] + LI()
    dp = [[0] * (S+1) for _ in range(N+1)]
    dp[0][0] = pow(2,N,MOD)
    d2 = pow(2,MOD-2,MOD)
    for i in range(1,N+1):
        for j in range(0,S+1):
            if j >= A[i]:
                dp[i][j] = (dp[i-1][j] + dp[i-1][j-A[i]] * d2) % MOD
            else:
                dp[i][j] = dp[i-1][j]

    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 135688
import java.util.*;
import java.lang.Math.*;
public class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		long n=sc.nextLong();
		long k=sc.nextLong();
		n=n%k;
		Long min=Math.min(n, Math.abs(n-k));
		System.out.println(min);
	}
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
int count(ll x){
	int cnt = 0;
	while(x != 0){
		cnt++;
		x /= 10;
	}
	return cnt;
}
int cnt[1000000];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		cnt[x]++;
	}	
	for(int i=1;i<=100000;i++)
	{
		if(cnt[i]>1)
		{
			n-=cnt[i]-1;
		}
	}
	if(n%2==0)
		n--;
	cout<<n<<endl;
} 



Measured memory_bytes: 768
#include <iostream>
using namespace std;
int main(){
    int a[4];
    int ans=0;
    for(int i=0;i<4;i++){
    cin>>a[i];
        ans+=a[i];
    }
    int m=ans/60;
    int s=ans%60;
    cout<<m<<endl;
    cout<<s<<endl;
}

Measured memory_bytes: 3088
using System;
using System.Collections.Generic;

namespace ABC
{
    class ABC096C
    {
        public static int H = 0;
        public static int W = 0;
        public static char[,] Masu = null;

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

        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            H = int.Parse(str[0]);//高さ
            W = int.Parse(str[1]);//幅

            Masu = new char[H, W];
            for (int h = 0; h < H; ++h)
            {
                int w = 0;
                var line = Console.ReadLine();
                foreach (char s in line)
                {
                    Masu[h, w] = s;
                    ++w;
                }
            }

            bool ans = Judge();
            Console.WriteLine("{0}", ans ? "Yes" : "No");
        }
        //# : 塗りたい
        //. : 塗れない
        //@ : 塗った

        static bool Judge()
        {
            //与えられた図形に対して、#を点としてグラフを構築
            //グラフ上の点がすべて連結(== 縦か横に別の点がある)であればtrue,孤立点があればfalse
            var graph = new int[H, W];
            for (int h = 0; h < H; ++h)
            {
                for (int w = 0; w < W; ++w)
                {
                    graph[h, w] = 0;
                }
            }
            for (int h = 0; h < H; ++h)
            {
                for (int w = 0; w < W; ++w)
                {
                    //#マスを見つけたら
                    if (Masu[h, w] == '#')
                    {
                        //隣接マスを黒くぬれるか調べる
                        int dir = -1;
                        bool canPaint = isConnect(h, w, out dir);
                        if (canPaint == true)
                        {
                            //塗ったマスは@とする
                            Masu[h, w] = '@';
                            Masu[h + dy[dir], w + dx[dir]] = '@';
                        }
                    }
                }
            }

            for (int h = 0; h < H; ++h)
            {
                for (int w = 0; w < W; ++w)
                {
                    //塗りたいのに塗れないマスがあったら失敗
                    if (Masu[h, w] == '#') return false;
                }
            }

            return true;
        }

        static bool isConnect(int h, int w, out int dir)
        {
            for (int i = 0; i < 4; ++i)
            {
                int targetH = h + dy[i];
                int targetW = w + dx[i];
                //キャンバス外なら飛ばす
                if(targetH < 0 || H <= targetH) { continue; }
                if(targetW < 0 || W <= targetW) { continue; }

                if (Masu[targetH, targetW] == '#' || Masu[targetH, targetW] == '@')
                {
                    dir = i;
                    return true;
                }
            }
            dir = -1;
            return false;
        }
    }
}


Measured memory_bytes: 13268
import sys
sys.setrecursionlimit(1000000)

N,M=map(int,input().split())

G=[[] for _ in range(N+1)]  #G[0]はダミー
for edge in range(M):
    x,y=map(int,input().split())
    G[x].append(y)

DP=[-1]*(N+1)   #DP[0]はダミー

def rec(now):
    global G
    global DP

    if DP[now]!=-1:
        return DP[now]

    else:
        res=0
        for next in G[now]:
            res=max(res,rec(next)+1)
        DP[now]=res
        return DP[now]  #resは不可


ans=0
for v in range(1,N+1):
    ans=max(ans,rec(v))



print(ans)





Measured memory_bytes: 59056
#include <stdio.h>

int main(void)
{
	int juice, pasta;
	int i, tmp;
	
	scanf("%d", &pasta);
	for (i = 0; i < 2; i++){
		scanf("%d", &tmp);
		if (tmp < pasta){
			pasta = tmp;
		}
	}
	
	scanf("%d", &juice);
	scanf("%d", &tmp);
	
	if (tmp < juice){
		juice = tmp;
	}
	
	printf("%d\n", pasta + juice - 50);
	
	return (0);
}

Measured memory_bytes: 592
/* 
	Author: ankrypt
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 15
#define PI 3.141592653589793
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi(a, b, c, d) for(int a = b; a < c; a += d)
#define fl(a, b, c, d) for(ll a = b; a < c; a += d)
#define fei(a, b, c, d) for(int a = b; a <= c; a += d)
#define fel(a, b, c, d) for(ll a = b; a <= c; a += d)
#define quit exit(0)
#define mem(x, a) memset(x, a, sizeof x)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pcl pair<char, ll>
#define psl pair<string, ll>


ll N, M, A, B, C;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<ll> V;
unordered_map<ll, ll> mp;
set<ll> s;
string S = "";
ll cases;

int main() {
	go;
	cin >> N >> A >> B;
	A = -A;
	ll diff = B + A;
	if(diff <= 0) {
		cout << "delicious\n";
		quit;
	}
	if(diff > N) {
		cout << "dangerous\n";
	}
	else {
		cout << "safe\n";
	}

    
	return 0;
}
/*
	Powered by Buggy Plugin
*/




Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

ll mini(ll a, ll b, ll c, ll d){ return min(a ,min(b ,min(c, d))); }
ll maxi(ll a, ll b, ll c, ll d){ return max(a ,max(b ,max(c, d))); }

int main(void){
    ll N, K;
    cin >> N >> K;
    vector<pair<ll, ll>> v(N);
    for(auto& it : v) cin >> it.first >> it.second;

    ull ans = 1L << 63;

    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++){
                    pair<ll, ll> ul(mini(v[i].first, v[j].first, v[k].first, v[l].first), maxi(v[i].second, v[j].second, v[k].second, v[l].second));
                    pair<ll, ll> br(maxi(v[i].first, v[j].first, v[k].first, v[l].first), mini(v[i].second, v[j].second, v[k].second, v[l].second));
                    int c=0;
                    for(int a=0;a<N;a++){
                        if(ul.first <= v[a].first && v[a].first <= br.first
                        && ul.second >= v[a].second && v[a].second >= br.second) c++;
                    }

                    if(c >= K) ans = min(ans, (ull)abs(ul.first-br.first) * (ull)abs(ul.second-br.second));
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
n=int(input())
l=[]
for i in range(n):
    lo=input().split()
    lop=[int(i) for i in lo]
    l.append(lop)
poss=0
for i in range(n-2):
    if(l[i][0]==l[i][1] and l[i+1][0]==l[i+1][1] and l[i+2][0]==l[i+2][1]):
        poss=1
        break
if(poss):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 62380
#include<iostream>
#include<math.h>

using namespace std;

int main()
{
	int n;
	cin >> n;
	int*a = new int[n] {};
	int z;
	for (int i = 0; i < n - 1; i++) {
		cin >> z;
		if (i == 0) {
			a[0] = z;
			a[1] = z;
		}
		else {
			if (a[i] > z)a[i] = z;
			a[i + 1] = z;
		}
	}
	int count = 0;
	for (int i = 0; i < n; i++) {
		count += a[i];
	}
	cout << count << endl;
	return 0;
}



Measured memory_bytes: 256
N=int(input())
town=[]
for i in range(N):
    x,y=map(int,input().split())
    town.append([x,y])
total=0
for i in range(N):
    for j in range(N):
        total+=((town[j][0]-town[i][0])**2+(town[j][1]-town[i][1])**2)**0.5
a=0
for i in range(N):
    a+=i
ave=total/a
print((ave*N-ave)/2)

Measured memory_bytes: 3444
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
using namespace std;

int main(void) {

	int a = 0, b = 0, temp;

	for (int i = 0; i < 4; i++) {
		scanf("%d", &temp);
		a += temp;
	}
	for (int i = 0; i < 4; i++) {
		scanf("%d", &temp);
		b += temp;
	}

	printf("%d\n", max(a, b));

	return 0;
}

Measured memory_bytes: 1024
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    x,a,b=MI()
    if abs(x-a)<abs(x-b):
        print("A")
    else:
        print("B")
main()

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int a,b,cnt,n;

int main(void)
{
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> a >> b;
		if(a==b)	cnt++;
		else		cnt=0;
		if(cnt==3)
		{
			cout << "Yes" << endl;
			return 0;	
		}	
	}
	cout << "No" << endl;
	return 0;
} 

Measured memory_bytes: 3616
m,p=map(int,input().split())
n = 10**6
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
                #エラトステネスの篩
ans=1
lists=[]
checker=1
for i in prime:
    lists.append(i)  
lists=sorted(lists) 
for i in lists:
    count=0
    while p%i==0:
        p=p/i
        count+=1
    a=count//m
    ans=ans*(i**a)


if p>10**6:
    if m==1:
        ans=ans*p
        
        print(int(ans))
    else:
        print(int(ans))
else:
    print(int(ans))
    

Measured memory_bytes: 74336
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll dp[100005];

int main()
{
    ll n;
    cin>>n;
    ll a[n+5];
    for(int i=0; i<n; i++)
        cin>>a[i];
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(int i=2; i<n; i++)
        dp[i]=min((dp[i-1]+abs(a[i]-a[i-1])),(dp[i-2]+abs(a[i]-a[i-2])));
    cout<<dp[n-1]<<endl;
    return 0;
}


Measured memory_bytes: 5180
#include <iostream>
#include <cmath>

using namespace std;

int N;
long long X;
long long x[100000];

long long gcd(long long a,long long b){
    long long m = max(a,b);
    long long n = min(a,b);
    while(m % n != 0){
        long long b = m % n;
        m = n;
        n = b;
    }
    return n;
}

int main(){
    cin >> N >> X;
    for(int i=0;i<N;i++) cin >> x[i];
    for(int i=0;i<N;i++) x[i] = abs(x[i]-X);
    for(int i=1;i<N;i++) x[0] = gcd(x[i],x[0]);
    cout << x[0] << endl;
    return 0;
}

Measured memory_bytes: 1024
D = int(input())
c = list(map(int, input().split()))
S = []
for i in range(D):
    S.append(list(map(int, input().split())))

nocontest = [1 for i in range(26)]

for i in range(D):
    s = S[i]
    contest = [0 for j in range(26)]
    for j in range(26):
        contest[j] = c[j] * nocontest[j] * s[j]
    #print(contest)
    max_contest = max(contest)
    ans = contest.index(max_contest)
    print(ans + 1)
    
    for i in range(26):
        if i == ans:
            nocontest[i] = 1
        else:
            nocontest[i] += 2
    #print(nocontest)

Measured memory_bytes: 9532
n,m = map(int,input().split())
a = [[int(j) for j in input().split()] for i in range(n)]
b = [int(input()) for k in range(m)]
for p in range(n):
    print(sum(a[p][q] * b[q] for q in range(m)))

'''
考えたプログラム

二次元配列を組む
list_m =[[0 for p in range(m)] for q in range(n)]

for i in range(n):
    lst = list(map(int,input().split()))
    list_m[i] = lst

1次元配列を組む
list_v = [0 for r in range(m)]

for j in range(m):
    list_v[j] = int(input())
print(list_v)

sum0 = 0
for p in range(n):
    for q in range(m):
        sum0 += list_m[p][q] * list_v[q]
    print(sum0)
    sum0 = 0
'''


Measured memory_bytes: 6020
program sample
	implicit none
    integer :: x,y,i,sum1,maxval1,minval1
    integer, allocatable :: a(:)
    
    read(*,*) x,y
    
    allocate(a(x))
    
    do i=1,x
       a(i)=y+i-1
    end do
    
    sum1=sum(a)
    maxval1=maxval(a)
	minval1=minval(a)
    
    if (maxval1 >=0 .and. minval1<=0) then
    	write(*,*) sum1
    else if (minval1>0) then
    	write(*,*) sum1-minval1
    else
    	write(*,*) sum1-maxval1
    end if
    
    deallocate(a)
    
    stop
end program sample

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
    // Your code here!
    int N, T;
    int c, t;
    int min_cost = 100000;
    
    cin >> N >> T;
    for(int i = 0; i < N; i++){
        cin >> c >> t;
        if(t <= T)
            min_cost = min(min_cost, c);
    }
            
    if(min_cost == 100000)
        cout << "TLE" << endl;
    else
        cout << min_cost << endl;
        
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
class Main
{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    
    String a = sc.next();
    String b = sc.next();
    
    String a1 = a.substring(0,1);
    String a2 = a.substring(1,2);
    String a3 = a.substring(2,3);
    
    String b1 = b.substring(0,1);
    String b2 = b.substring(1,2);
    String b3 = b.substring(2,3);
    
    int count = 0;
    
    if(a1.equals(b1)){
      count++;
    }
    if(a2.equals(b2)){
      count++;
    }
    if(a3.equals(b3)){
      count++;
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 23764
#include <algorithm>
#include <array>
#include <bitset>
#include <functional>
#include <iostream>
#include <memory>
#include <set>
#include <string>
#include <vector>

using namespace std;

int main() {
	int n, x;
	cin >> n >> x;
	int minm = 1000;
	for (int i = 0; i < n; i++) {
		int m;
		cin >> m;
		if (m < minm) {
			minm = m;
		}
		x -= m;
	}
	cout << n + (x / minm) << endl;
	return 0;
}


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

int a,b,c,sr[500],ans;
string s;

int  main(){
    cin>>s;
    for(int i=0;i<4;i++){
        sr[s[i]]++;
    }
    for(int i=0;i<500;i++){
        if(sr[i]==2)ans++;
    }
    if(ans==2)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}




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

#define PI acos(-1)

void textIO()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

}

bool Check(int n, int pos){return (bool)(n&(1<<pos));}
long long Set(int n, int pos){return n=n|(1<<pos);}
int Reset(int n, int pos){return n=n&~(1<<pos);}

long long n, m, x, ans = LONG_LONG_MAX;

vector<long long> cost(12);
vector<vector<long long>> arr(12, vector<long long> (12));


pair<bool, long long> getSol(int mask){
    long long ret = 0;

    for(int i=0;i<n;i++){
        if(Check(mask, i) == true){
            ret+=cost[i];
        }
    }
    for(int i=0;i<m;i++){
        long long sum = 0;
        for(int j=0;j<n;j++){
            if(Check(mask, j) == true){
                sum+=arr[j][i];
            }
        }
        if(sum < x){
            return {false, 0};
        }
    }
    return {true, ret};
}

void solve(int ind, int mask){
    if(ind == n){
        pair<bool, long long> p = getSol(mask);
        if(p.first == true){
            ans = min(ans, p.second);
        }
        return;
    }
    solve(ind+1, Set(mask, ind));
    solve(ind+1, mask);
}


int main()
{
    textIO();
    fastIO();


    cin >> n >> m >> x;

    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            if(j==0){
                cin >> cost[i];
            }
            else{
                cin >> arr[i][j-1];
            }
        }
    }


    solve(0, 0);

    if(ans != LONG_LONG_MAX){
        cout << ans << '\n';
    }
    else{
        cout << -1 << '\n';
    }


    return 0;
}


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

int main() {
	double a,b,c,d,e,f,node=0,answ,anssu;
	cin>>a>>b>>c>>d>>e>>f;
	for(double i=0;i*100*a<=f;i++){
		for(double j=0;j*100*b<=f;j++){
			for(double k=0;k*c<=f/2;k++){
				for(double l=0;l*d<=f/2;l++){
					double w=i*100*a+j*b*100;
					double su=k*c+l*d;
					if(w+su>f){
						continue;
					}
					if(e*w<100*su){
						continue;
					}
					if(100*su/(su+w)>=node){
						node=(100*su/(su+w));
						answ=w;
						anssu=su;
					}
				}
			}
		}
	}
	cout << answ+anssu <<" "<<anssu;
	return 0;
}

Measured memory_bytes: 256
def identification(x,y,arr)
    if(arr[y][x]==1)
        arr[y][x]=0
        identification(x-1,y,arr) if x-1>=0 && arr[y][x-1]==1
        identification(x+1,y,arr) if x+1<12 && arr[y][x+1]==1
        identification(x,y-1,arr) if y-1>=0 && arr[y-1][x]==1
        identification(x,y+1,arr) if y+1<12 && arr[y+1][x]==1
        return true
    end
    return false
end
while !STDIN.eof?
    arr=[]
    count=0
    12.times do
        arr<<gets.split(//).map(&:to_i)
    end
    gets
    12.times do |y|
        12.times do |x|
            count+=1 if identification(x,y,arr)
        end
    end
    p count
end

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

using namespace std;

/*
 * 約数の列挙
 *   返り値の約数はソートされていないことに注意
 */
static vector<int> enum_devisor (int n) {
    vector<int> devisor;
    int quotient;
    for ( int i = 1; i * i <= n; i++ ) {
        if ( n % i == 0 ) {
            devisor.push_back(i);
            quotient = n / i;
            if ( quotient != i )
                devisor.push_back(quotient);
        }
    }
    return devisor;
}

int main (void) {
    vector<char> num(1e6+1, 0);
    int N;
    cin >> N;
    vector<int> A(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> A.at(i);
        if ( num.at(A.at(i)) == 0 )
            num.at(A.at(i)) = 1;
        else
            num.at(A.at(i)) = 2;
    }

    int ans = 0;
    for ( int i = 0; i < N; i++ ) {
        if ( num.at(A.at(i)) == 2 )
            continue;
        vector<int> devisor;
        devisor = enum_devisor(A.at(i));
        bool is_ans = true;
        for ( auto itr : devisor ) {
            if ( itr != A.at(i) && num.at(itr) != 0 ) {
                is_ans = false;
                break;
            }
        }
        if ( is_ans )
            ans++;
    }

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


Measured memory_bytes: 5064