akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws Exception{
		int num = 998244353;

		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
 		StringTokenizer st = new StringTokenizer(bf.readLine());
 		int n = Integer.parseInt(st.nextToken());
 		int d = Integer.parseInt(st.nextToken());
 		int count = 0;
 		for(int i = 0;i<n;i++){
//	 		String input1 = bf.readLine().trim();
//	 		String input2 = bf.readLine().trim();
	 		StringTokenizer st1 = new StringTokenizer(bf.readLine());
	 		int x1 = Integer.parseInt(st1.nextToken());
	 		int y1 = Integer.parseInt(st1.nextToken());
	 		if ((long)(x1)* (long)(x1) + (long)(y1)*(long)(y1) <= (long)(d)*(long)(d))
	 			count++;
 		}
 		
 		
 		out.println(
 				count);
	 		
 		out.close();
 		
 		
 		
 	}
}
 	
 
//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is

 		
 		
 		
 		
	




Measured memory_bytes: 45724
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<climits>//long long型の最大値(LLONG_MAX)など
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;
typedef long double lb;

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

int main() {
    ll H,W;
    cin >> H >> W;
    vector<vector<char>> a(H,vector<char>(W));

    rep(i,H){
        rep(j,W){
            cin >> a[i][j];
        }
    }

    rep(i,W+2){
        cout << '#';
    }
    cout << endl;

    rep(i,H){
        cout << '#';
        rep(j,W){
            cout << a[i][j];
        }
        cout << '#' << endl;
    }

    rep(i,W+2){
        cout << '#';
    }
    cout << endl;

}



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

int main(){
    int n;
    int ans=inf;
    cin >> n;
    rep(i,n){
        int a;
        int count=0;
        cin >> a;
        while(a%2==0){
            count++;
            a=a/2;
        }
        ans=min(ans,count);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int V = 1e5 + 100;
int n, we, w[N], v[N];
long long dp[V], dp0[V];

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

	cin >> n >> we;

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

	for (int j = 0; j < V; j++) {
		dp0[j] = LLONG_MAX;
		dp[j] = LLONG_MAX;
	}

	dp0[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < V; j++) {
			if (dp0[j] == LLONG_MAX) continue;
			dp[j] = min(dp[j], dp0[j]);
			dp[j + v[i]] = min(dp[j + v[i]], dp0[j] + (long long) w[i]);
		}

		for (int j = 0; j < V; j++) {
			dp0[j] = dp[j];
			dp[j] = LLONG_MAX;
		}
	}

	int ans = 0 ;
	for (int i = V - 1; i > 0; i--) {
		if (dp0[i] <= we) {
			ans = i;
			break;
		}
	}

	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 5164
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define n_p(v) next_permutation(v.begin(),v.end())
#define to_ll(b) stoll(b)
#define MOD 1000000007
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	int n; cin>>n;
	set<int> pri;
	map<int,int> mp;
	rep(i,2,n+1){
		bool ok=true;
		rep(j,2,sqrt(i)+1){
			if(i%j==0 && i!=j) ok=false;
		}
		if(ok) pri.insert(i);
	}
	rep(i,2,n+1){
		int k=i;
		while(k>1){
			for(int c:pri){
				if(k==1) break;
				if(k%c==0){
					mp[c]++;
					k/=c;
				}
			}
		}
	}
	ll ans=1;
	for(auto c:mp){
		ans*=c.second+1;
		ans%=MOD;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
// C - Many Requirements
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(n);++i)

int N,M,Q,ans;
vi a,b,c,d;

void dfs(vi A){
	if(N+1 <= (int)A.size()){
		int now = 0;
		rep(i, Q) if(A[b[i]]-A[a[i]] == c[i]) now += d[i];
		ans = max(ans, now);
		return;
	}
	A.push_back(A.back());
	while(A.back() <= M){
		dfs(A);
		A.back()++;
	}
}

int main(){
	cin>>N>>M>>Q;
	a = b = c = d = vi(Q);
	rep(i, Q) cin>>a[i]>>b[i]>>c[i]>>d[i];
	dfs(vi(1,1));
	cout<< ans <<endl;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
using namespace std;
main(){
//	freopen("input.txt","r",stdin);
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    int arr[n][m];
    for(int i=0;i<n;i++){
    	string str;
    	cin>>str;
    	for(int j=0;j<m;j++){
    		if(str[j] == '.'){
    			arr[i][j] = 0;
			}
			else{
				arr[i][j] = 1;
			}
		}
	}
	map<int,int> row,col;
	for(int i=0;i<n;i++){
		int flag = 0;
		for(int j=0;j<m;j++){
			if(arr[i][j] == 1){
				flag = 1;
			}
		}
		if(flag == 0){
			row[i] = 2;
		}
	}
	for(int j=0;j<m;j++){
		int flag = 0;
		for(int i=0;i<n;i++){
			if(arr[i][j] == 1){
				flag = 1;
			}
		}
		if(flag == 0){
			col[j] = 2;
		}
	}
	for(int i=0;i<n;i++){
		if(row[i] != 2){
			for(int j=0;j<m;j++){
				if(col[j] != 2){
					if(arr[i][j] == 0){
						cout<<".";
					}
					else{
						cout<<"#";
					}
				}
			}
			cout<<endl;
		}
	}
}

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

int main() {
	// your code goes here
	int n;
	cin>>n;
	
	vector<int> h(n, 0), dp(n, 0);
	
	for(int i=0; i<n; i++) cin>>h[i];
	
	dp[0] = 0;
	dp[1] = abs(h[1]-h[0]);
	for(int i=2; i<n; i++){
		dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]));
	}
	
	cout<<dp[n-1];
	
	return 0;
}

Measured memory_bytes: 3984
#include<bits/stdc++.h>
#define taskname "test1"
#define int long long
using namespace std;

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);	cout.tie(nullptr);
    if (ifstream("test.inp"))
    {
        freopen("test.inp", "r", stdin);
        #ifdef CHECKING
            freopen(taskname".out", "w", stdout);
        #else
            freopen("test.out", "w", stdout);
        #endif //CHECKING
    }
    else if (ifstream(taskname".inp"))
    {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }

    vector<int> a(4);
    for (int &i : a) cin >> i;
    int x = a[0] + a[1];
    int y = a[2] + a[3];
    if (x < y) cout << "Right";
    else if (x > y) cout << "Left";
    else cout << "Balanced";
}



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

int main(){
  int n,k;
  cin>>n>>k;
  vector<int>a(n);
  rep(i,n)cin>>a[i];
  int ans=0;
  
  for(int l=0;l<=k;++l){
    for(int r=0;r<=k-l;r++){
      if (l+r>n)continue;
      int d=k-l-r;
      int now=0;
      vector<int>s;
      rep(i,l){
        now+=a[i];
        s.push_back(a[i]);
      }
      for(int i=n-r;i<n;++i){
        now+=a[i];
        s.push_back(a[i]);
      }
      sort(s.begin(),s.end());
      for(int i=0;i<d;++i){
        if(i>=s.size())break;
        if(s[i]>0)break;
        now-=s[i];
      }
      ans=max(ans,now);
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int check[51][30];
int main(){
	string s,ans="";
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>s;
		for(int j=0;j<s.length();j++){
			check[i][s[j]-'a']++;
		}
	}
	for(int i=0;i<='z'-'a';i++){
		int minimam=check[0][i];
		for(int j=1;j<n;j++)minimam=min(minimam,check[j][i]);
		for(int j=0;j<minimam;j++)ans+='a'+i;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
// #include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define exf(x)	 for(auto&& tmp : x) { cout << tmp << endl; }	// 拡張for
#define PI 3.14159265358979323846264338327950288
const int MOD{ int(1e9 + 7) };	// = 1000000007
const int inf{ 2100000000 };	// = 2100000000 (MAX:2147483647)
typedef long long ll;
using namespace std;

// -------------------------------------------------- //
// ------------------ ここから本編 ------------------ //
// -------------------------------------------------- //

int main(void) {

	int N;
	cin >> N;
	vector<string> S(N); 
	int ac = 0, wa = 0, tle = 0, re = 0;
	rep(i, N) {
		cin >> S[i];
		if (S[i] == "AC") ac++;
		else if (S[i] == "WA") wa++;
		else if (S[i] == "TLE") tle++;
		else re++;
	}

	cout << "AC x " << ac << endl;
	cout << "WA x " << wa << endl;
	cout << "TLE x " << tle << endl;
	cout << "RE x " << re << endl;

	return 0;
}


Measured memory_bytes: 6424
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef std::vector<vector<int> > vvi;
typedef pair<int, int> pi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
#define inf (ll)1e9

#define debugone(x) cout << #x << " " << x << "\n"; cout.flush();
#define debugtwo(x) cout << #x << "-------------" << "\n";for(auto &it: x) cout << it << " ";cout << "\n"; cout.flush();
#define debugthree(x, i, j) cout << #x << "------------" << "\n";cout << "from " << i << " to " << j << "\n";for(ll k=i; k<=j; k++) cout << x[k] << " ";cout << "\n"; cout.flush();



int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
			
	ll n;
	cin >> n;
	ll sqrtn = sqrt(n);

	//N = (m + 1) (N/m)
	ll res = 0;
	for(ll i= 1; i <= sqrtn; i++){
		if(n%i == 0){
			ll m = n/i - 1;
			if(m == 0) continue;
			if(n%m == n/m){
				res+= m;
			}
		}
	}

	cout << res << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;

int main()
{
    int n;
    cin >> n;
    ll a[100002], b[100002];
    ll s[200002];
    P pa[100002], pb[100002];
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
        s[i * 2] = a[i];
        s[i * 2 + 1] = b[i];
        pa[i] = P(a[i], i);
        pb[i] = P(b[i], i);
    }
    sort(pa, pa + n);
    sort(pb, pb + n);
    sort(s, s + n * 2);
    bool used[100002];
    fill(used, used + n, false);
    int na = 0, nb = 0;
    ll ans = 0;
    int last;
    for(int i = 0; i < n; i++){
        if(pa[na] < pb[nb]){
            ans += pa[na].first;
            used[pa[na].second] = true;
            last = pa[na].second;
            na++;
        }
        else{
            ans += pb[nb].first;
            used[pb[nb].second] = true;
            last = pb[nb].second;
            nb++;
        }
    }
    if(na == 0 || nb == 0){
        cout << ans << endl;
        return 0;
    }
    bool dbl = false;
    for(int i = 0; i < n; i++) dbl |= !used[i];
    if(dbl){
        cout << ans << endl;
        return 0;
    }
    int r;
    if(pa[na].first < pb[nb].first){
        r = pa[na].second;
        na++;
    }
    else{
        r = pb[nb].second;
        nb++;
    }
    if(last != r || na == n || nb == n){
        cout << ans - s[n - 1] + s[n] << endl;
    }
    else{
        cout << ans + min(s[n + 1] - s[n - 1], s[n] - s[n - 2]) << endl;
    }
}

Measured memory_bytes: 6656
a,b,c,d=map(int,input().split())

abcd=[a*c,a*d,b*c,b*d]

tmp=max(abcd)

if tmp>=0:
    print(tmp)
else:
    if a<=0 and 0<=b:
        print(0)
    elif c<=0 and 0<=d:
        print(0)
    else:
        print(tmp)










Measured memory_bytes: 61640
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long ll;

int main() {
	int n; cin >> n;
	map<int, int>a;
	vector<ll>sortedA((int)1e6,0);
	for (int i = 0; i < n; i++) {
		int tmp; cin >> tmp;
		a[tmp]++;
	}
	for (auto x : a) {
		if (x.second >= 4) {
			sortedA.push_back(x.first);
			sortedA.push_back(x.first);
		}
		else if (x.second >= 2 && x.second < 4)sortedA.push_back(x.first);
	}

	sort(sortedA.rbegin(), sortedA.rend());
	cout << sortedA[0] * sortedA[1] << endl;

	return 0;
}

Measured memory_bytes: 22400
//
// Created by kuroneko on 2019-07-06.
//

using namespace std;

#include <iostream>
#include <vector>
#include <cmath>
#include <string>

typedef long long ll;
int INF = 1000000007;

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

    if (A >= 6 && A <= 12) ans = B/2;
    else if (A <= 5) ans = 0;
    cout << ans << endl;
    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 rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1e9+7;
const ll INF=1e9;
const ll IINF=1e15;
const double EPS=1e-8;
const double pi=acos(-1);

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;
}

ll dp[310][310][310];

int main(){
    ll N,K;
    cin >> N >> K;
    vector<ll> H(N+1,0);
    rep(i,N) cin >> H[i+1];
    rep(i,N+1) rep(j,K+1) rep(k,N+1) dp[i][j][k]=IINF;
    dp[0][0][0]=0;
    rep2(i,1,N+1){
        rep(j,K+1){
            rep(k,N+1){
                chmin(dp[i][j][i],dp[i-1][j][k]+max(0LL,H[i]-H[k]));
                if (j<K) chmin(dp[i][j+1][k],dp[i-1][j][k]);
            }
        }
    }
    ll ans=IINF;
    rep(i,K+1) rep(j,N+1) chmin(ans,dp[N][i][j]);
    cout << ans << endl;
}

Measured memory_bytes: 227584
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,k,op; char A[N]; deque<int> Q;
int main()
{
	int i;
	scanf("%d %d\n",&n,&k);
	scanf("%s",A+1);
	if(k>=2*n){
		if(n&1) printf(k&1 ? "A" : "B");
		for(i=1;i<=n/2;i++) printf("BA");
	  }
	else{
		for(i=1;i<=n;i++) Q.push_back(A[i]=='A');
		for(i=1;i<=2*n&&i<=k;i++)
			if(Q.front()^op) Q.pop_front(),Q.push_front(op);
			else Q.pop_front(),Q.push_back(op),op^=1;
		for(i=1;i<=n;i++)
			printf(Q.front()^op ? "A" : "B"),Q.pop_front();
	  }
	return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define eb emplace_back
#define uqv(v) v.erase(unique(all(v)), v.end());
#define INF 1e9
#define LINF 1e18

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

int arr[55];

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

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

	int ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			ans += arr[i] * arr[j];
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
a,b,k = map(int,input().split())
for i in range(k):
  if i%2 == 0:
    if a%2 != 0 :
      a -=1
    a /= 2
    b += a
  else :
    if b%2 != 0:
      b -= 1
    b /= 2
    a += b
print(int(a),int(b))

Measured memory_bytes: 3060
#include<stdio.h>

int selectionsort(int *a, int length)
{

  int i, j, tmp, cnt=0, mini;

  for(i=0; i<length; i++)
    {
      mini = i;
      
      for(j=i; j<length; j++)
	{
	  if(a[j]<a[mini])
	    {
	      mini = j;
	    }
	}

      if(i != mini)
	{
	  tmp = a[i];
	  a[i] = a[mini];
	  a[mini] = tmp;
	  cnt++;
	}
    }

  return cnt;
}


main()
{
  int i, n, Array[100], cnt=0;

  scanf("%d", &n);

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

  cnt = selectionsort(Array, n);

  printf("%d", Array[0]);

  for(i=1; i<n; i++)
    {
      printf(" %d", Array[i]);
    }

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

return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using i64 = int_fast64_t;
#define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define rep(i, n) repeat(i, 0, n)

void solve() {
    const int INF = 1e9 + 7;
    int x, y;
    std::cin >> x >> y;
    int dx[2] = {x, -x};
    int dy[2] = {y, -y};
    int a[4] = {0, 0, 0, 0};
    rep(i, 2) {
        rep(j, 2) {
            a[i * 2 + j] = ((dy[j] - dx[i]) < 0 ? INF : dy[j] - dx[i]) + i + j;
        }
    }
    std::cout << std::min({a[0], a[1], a[2], a[3]}) << std::endl;
}

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

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX 100

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N, M;
	int K, A, ans = 0;
	int temp[MAX] = {};
	
	cin>>N>>M;
	
	for(int i = 0; i < N; i++){
		cin>>K;
		for(int j = 0; j < K; j++){
			cin>>A;
			temp[A]++;
		}
	}
	for(int i = 1; i <= M; i++){
		if(temp[i] == N) ans++;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
import math
def facts(n):
    ans = []
    for  i in range(1, int(math.sqrt(n)+1)):
        if(n%i==0):
            ans.append(i)
            ans.append(n//i)
    ans = sorted(list(dict.fromkeys(ans)))
    if(ans[-1]==n):
        ans = ans[:-1]
    return ans

n,k = map(int, input().split())
nums = sorted(list(map(int, input().split())))
ans = sum(nums[:k])
print(ans)


Measured memory_bytes: 62624
S=raw_input()
 
M=10**9+7
 
all=1
abc=0
ab=0
a=0
 
for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab
 
	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3
 
	abc%=M
	ab%=M
	a%=M
	all%=M
 
 
print abc%M

Measured memory_bytes: 32492
import java.util.*;

public class Main {
	

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

		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();

		for (int i = A; i<B+1; i++){
			if(i%N==0){
				System.out.println("OK");
				return;
			}
			continue;
		}
		System.out.println("NG");
		return;
	}


}


Measured memory_bytes: 35684
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

vector<int> v[111111];
int ord[111111], low[111111];
void dfs(int x,int p,int &c,vector<P> &B){
  ord[x]=low[x]=c++;
  for(int i=0;i<v[x].size();i++){
    int y=v[x][i];
    if(y==p) continue;
    if(ord[y]==-1){
      dfs(y,x,c,B);
      low[x]=min(low[x],low[y]);
    } else{
      low[x]=min(low[x],ord[y]);
    }
    if(ord[x]<low[y]) B.push_back(P(x,y));
  }
}

void bridge(int n,vector<P> &B){
  B.clear();
  int c=0;
  fill(ord,ord+n,-1);
  for(int i=0;i<n;i++)if(ord[i]==-1)dfs(i,-1,c,B);
}

void Main() {
  int n,m;
  cin >> n >> m;
  rep(i,m) {
    int x,y;
    cin >> x >> y;
    x--,y--;
    v[x].pb(y);
    v[y].pb(x);
  }
  vector<P> ans;
  bridge(n,ans);
  pr(ans.size());
}

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


Measured memory_bytes: 2944
package main

import (
	"fmt"
	"io"
	"os"
)

func main() {
	a(os.Stdin, os.Stdout)
}

func a(stdin io.Reader, stdout io.Writer) {
	var a int
	var b int

	// a > 0, b > 0 -> Positive
	// a > 0, b = 0 -> Zero
	// a > 0, b < 0 -> Zero
	// a = 0, b * 0 -> Zero
	// a < 0, b > 0 -> Zero
	// a < 0, b = 0 -> Zero
	// a < 0, b < 0 -> What?

	fmt.Fscan(stdin, &a, &b)

	if a > 0 && b > 0 {
		fmt.Fprintln(stdout, "Positive")
		return
	}

	if a*b < 0 {
		fmt.Fprintln(stdout, "Zero")
		return
	}

	// -3 -1 -> -3 * -2 * -1 -> Neg
	// (-1) - (-3) = 2, 2%2 == 0
	if (b-a)%2 == 1 {
		fmt.Fprintln(stdout, "Positive")
		return
	}

	fmt.Fprintln(stdout, "Negative")

}


Measured memory_bytes: 512
array = list(map(int, input()))

for i in range(2 ** 3):

    ans = array[0]
    mark = []

    for j in range(3):

        if (i >> j) & 1:
            mark.append('+')
            ans += array[j+1]
        
        else:
            mark.append('-')
            ans -= array[j+1]

    if ans == 7:
        print('{}{}{}{}{}{}{}=7'.format(array[0],mark[0],array[1],mark[1],array[2],mark[2],array[3]))
        exit()

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  int D,L,S,K;
  cin >> D >>L;
  S=D/L;
  K=D/L+D%L;
  if(D%L==0){
    cout << S << endl;
  }else{
    cout << K <<endl;
  }
  return(0);
}



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

int main() {
	int n;
	cin>>n;
	int t[n+1],x[n+1],y[n+1];
	for(int i=0;i<n;i++){
		cin>>t[i+1]>>x[i+1]>>y[i+1];
	}
	t[0]=x[0]=y[0]=0;
	int flag=1;
	for(int i=1;i<=n;i++){
		int dt=abs(t[i]-t[i-1]);
		int l=abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
//		cout<<dt<<endl<<l<<endl;
		if((l<=dt)*((l%2)==(dt%2))){

		}else{
			flag=0;
			break;
		}
	}
	if(flag){
		cout<<"Yes"<<endl;

	}else{
		cout<<"No"<<endl;
	}

	return 0;
}


Measured memory_bytes: 1408
/*  .　　∧_∧
   　（ ´・ω・)
   　//＼￣￣旦＼
   ／/ ※ ＼＿＿＿＼
   ＼＼ 　※ 　※ 　※ ヽ
   　 ＼ヽ-＿_＿--＿__ヽ*/

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define sort(v,n) sort(v,v+n);
#define vsort(v) sort(v.begin(),v.end());
#define vvsort(v) sort(v.begin(),v.end(),greater<int>());
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
typedef pair<int,int> p;
typedef pair<ll,ll> lp;
typedef priority_queue<int> pq;
typedef priority_queue<int,vector<int>,greater<int> > rpq;
bool is_uruu(int y) {
        return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}
const ll MOD=1e9+7;
const double PI=acos(-1.0);
//-------------------------------------------------------------------------------------------------------------------------------------------//
int main(){
        int n;
        string s;
        cin>>n;
        cin>>s;
        for(int j=0; j<4; j++) {
                int sw[n+3];
                string ans="";
                if(j==0) {
                        ans="WW";
                        sw[0]=0;
                        sw[1]=0;
                }else if(j==1) {
                        ans="WS";
                        sw[0]=0;
                        sw[1]=1;
                }else if(j==2) {
                        ans="SW";
                        sw[0]=1;
                        sw[1]=0;
                }else if(j==3) {
                        ans="SS";
                        sw[0]=1;
                        sw[1]=1;
                }
                for(int i=1; i<n-1; i++) {
                        if(s[i]=='o') {
                                if((sw[i-1]+sw[i])%2==0) {
                                        sw[i+1]=1;
                                        ans+='S';
                                }else{
                                        sw[i+1]=0;
                                        ans+='W';
                                }
                        }else{
                                if((sw[i-1]+sw[i])%2==0) {
                                        sw[i+1]=0;
                                        ans+='W';
                                }else{
                                        sw[i+1]=1;
                                        ans+='S';
                                }
                        }
                }
                if((sw[n-2]+sw[n-1]+sw[0]+(s[n-1]=='o'))%2==0 && (sw[n-1]+sw[0]+sw[1]+(s[0]=='o'))%2==0) {
                        cout<<ans<<endl;
                        return 0;
                }
        }
        cout<< -1<<endl;
}


Measured memory_bytes: 1024
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(ll i##_len=(n) ,i=i##_len-1;i>=0;--i)
#define repi(i,a,b) for(ll i=ll(a);i<=ll(b);++i)
#define ALL(f,x,...) ([&](decltype((x)) xxxx) { return (f)(begin(xxxx), end(xxxx), ## __VA_ARGS__); })(x)
#define lim 1000000007ll
#include<bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = std::pair<ll,ll>;
using namespace std;
template<class T>T 
chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T>T 
chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template <class T> T 
gcd(T a, T b){if (a < b) {a ^= b;b ^= a;a ^= b;} return b ? gcd(b, a % b) : a;}
template <class T> T 
lcm(T a, T b){return a * b / gcd(a, b);}
vector<char> 
string_to_vector_char(const string& input){vector<char> out(input.length());rep(i,input.length()){out[i]=input[i];}return out;}
map<char,int> 
count_same_elements(const vector<char>& v){map<char,int>cmap; for_each(v.begin(),v.end(),[&cmap](int x){cmap[x]++;}); return cmap; }
template<class A,class B> vector<B> 
mapf(const vector<A>& v,const function<B(A)>& func){vector<B> v_(v.size());rep(i,v.size()){ v_[i]=func(v[i]); }return v_;}
template<class A,class B> vector<B> 
adjacent_map(const vector<A>& v,const function<B(A,A)>& func){vector<B> v_(v.size()-1);rep(i,v.size()-1){ v_[i]=func(v[i+1],v[i]); }return v_;}
template<class A> bool
all_of(const vector<A>& v){bool flag=true;rep(i,v.size()){ if(v[i]<1){flag=false;}; }return flag;}
template<class A> bool
any_of(const vector<A>& v){bool flag=false;rep(i,v.size()){ if(v[i]>0){flag=true; break;}; }return flag;}
template<class A> bool
none_of(const vector<A>& v){bool flag=true;rep(i,v.size()){ if(v[i]>0){flag=false;}; }return flag;}
template<class T,class U>
void msg_with_compare(T A,T B,U A_greater_B,U A_eq_B,U A_less_B){
    if(A==B){cout<<A_eq_B<<"\n";}else if(A>B){cout<<A_greater_B<<"\n";}else{cout<<A_less_B<<"\n";}}
template<class B,class T>
void msg_with_boolean(B A,T true_msg,T false_msg){cout<< ( A? true_msg:false_msg);}
template<class B,class T>
void msg_with_boolean(B A1,B A2,T both_true_msg,T true_false_msg,T false_true_msg,T both_false_msg){
    if(A1){if(A2){cout<<both_true_msg;}else{cout<<true_false_msg;}
    }else{if(A2){cout<<false_true_msg;}else{cout<<both_false_msg;}}
}
template<class T>
void scan_vector(long long size,vector<T>& vector){
    vector.resize(size);
    for(long long i=0;i<size;++i){
        cin>>vector[i];
    }
}

ll a,b,c,k;
vector<ll> v;
void input(){
    cin>>a;
}
void src(){

    repi(i,1,2){
        v.push_back(i*i*i*i*i*i*i);
    }
    repi(i,1,3){
        v.push_back(i*i*i*i*i);
    }
    repi(i,1,10){
        v.push_back(i*i*i);
    }
    repi(i,1,31){
        v.push_back(i*i);
    }
    ALL(sort,v);
    cout<<*(upper_bound(v.begin(),v.end(),a)-1);

}   

int main(int argc,char* argv[]){
    ios::sync_with_stdio(false);
 //   ifstream in( argv[1] ); cin.rdbuf(in.rdbuf());
    input();
    src();    
    return 0;
}

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

int main () {
  vector<char> line ;
  line = {'A','B','C','D','E','F'} ;
  
  char a , b ;
  cin >> a >> b ;
  
  int x , y ;
  
  for ( int i = 0 ; i < 6 ; i++ ) {
    if ( line.at(i) == a ) {
      x = i ;
    }
    if ( line.at(i) == b ){
      y = i ;
    }
  }
  
  if ( x == y ) {
    cout << "=" << endl ;
  } else if ( x >= y ){
    cout << ">" << endl ;
  } else {
    cout << "<" << endl ;
  }
}


Measured memory_bytes: 256
//inlclude before define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
#include<deque>
#include<iomanip>
#include<set>
#include<unordered_set>
#include<tuple>
#include<map>
#include<memory>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef vector<double> VD;
typedef pair<int, int> P1;
typedef long long int ll;

//number
#define INF 1e9
#define NUM 1000000007

//itr
#define all(x) begin(x),end(x)

//repeat
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);i++)
#define RREPS(i,x) for(int i=((int)(x));i>=0;i--)

//max,min
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))

//function

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

/*ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a * (b / g);
}*/

/*int dig(int a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}*/

//grid template
int x[] = { -1, 0, 1, 0 };
int y[] = { 0,-1,0,1 };
int xx[] = { -1,-1,1,1 };
int yy[] = { 1,-1,1,-1 };

int main() {
	int a,b,c;
	cin >> a >> b >> c;

	int m = min(a, b);
	int n = 0;
	for (int i = m; i >= 1; i--) {
		if (a%i == 0 && b%i == 0) {
			c--;
			if (c == 0) {
				cout << i << endl;
				return 0;
			}
		}
	}
	
}




 

Measured memory_bytes: 256
a_b=[]
time = [0,0,0,0]
for i in range(3):
    a_b=input().split()
    if a_b[0]=='1':
        time[0]+=1
    if a_b[0]=='2':
        time[1]+=1
    if a_b[0]=='3':
        time[2]+=1
    if a_b[0]=='4':
        time[3]+=1
    if a_b[1]=='1':
        time[0]+=1
    if a_b[1]=='2':
        time[1]+=1
    if a_b[1]=='3':
        time[2]+=1
    if a_b[1]=='4':
        time[3]+=1
print('YES' if max(time)<=2 else 'NO')


Measured memory_bytes: 3064
O = input()
E = input()
S = ""

if len(O) == len(E):
  for i in range(len(O)):
    S += O[i] + E[i]
    
else:
  for i in range(len(E)):
    S += O[i] + E[i]
  S += O[len(O)-1]
  
print(S)

Measured memory_bytes: 8952
S = input()
N = int(S)

res = 0
for i in range(1, len(S)):
    if i % 2 == 1:
       res += 10 ** i - 10 ** (i - 1)

if len(S) % 2 == 1:
    res += N - 10 ** (len(S) - 1) + 1

print(res)




Measured memory_bytes: 2940
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long int ll;

struct city{
	int cityId;
	int group;
	int establishYear;
	int establishedOrder;
};

bool acs(struct city left,struct city right){
	if(left.group == right.group){
		if(left.establishYear < right.establishYear){
			return true;
		}else{
			return false;
		}
	}else if( left.group < right.group){
		return true;
	}else{
		return false;
	}
}

bool orderByCityId(struct city left,struct city right){
	if( left.cityId < right.cityId){
		return true;
	}else{
		return false;
	}
}

int main()
{
	int n,m;
	cin>>n>>m;
	struct city *cityList = new struct city[m];
	rep(i,m){
		cityList[i].cityId = i;
		int p,y;
		cin>>p>>y;
		cityList[i].group = p;
		cityList[i].establishYear = y;
	}
	sort(cityList,cityList + m,acs);	//group,year順
	int currentGroup = cityList[0].group;
	int counter = 1;
	rep(i,m){
		if(currentGroup != cityList[i].group){
			counter = 1;
			currentGroup = cityList[i].group;
		}
		cityList[i].establishedOrder = counter;
		counter++;
	}
	sort(cityList,cityList + m, orderByCityId);
	rep(i,m){
		printf("%06d%06d\n",cityList[i].group,cityList[i].establishedOrder);
	}
	return 0;
}



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


bool check(string a,string b,int d){
  if(a.size()<b.size())swap(a,b);
  if(a==b) return 1;
  int A = a.size(),B=b.size();
  if(d==0||A-B>d)return 0;


  //erase
  for(int i=0;i<A;i++){
    char ch = a[i];
    a.erase(a.begin()+i);
    if(check(a,b,d-1))return 1;
    a.insert(a.begin()+i,ch);
  }
  
  if(A!=B) return 0;

  
  //swap
  for(int i=0;i<A-1;i++){
    if(a[i]==a[i+1]||a[i+1]!=b[i]||a[i]!=b[i+1])continue;
    swap(a[i],a[i+1]);
    if(check(a,b,d-1))return 1;
    swap(a[i],a[i+1]);
  }

  //change
  int cnt=0;
  for(int i=0;i<A;i++) cnt+=a[i]!=b[i];
  if(cnt<=d)return 1;
  
  return 0;
}

int main(){
  int n,d;
  while(cin>>n,n){
    cin>>d;
    string str[201];
    for(int i=0;i<n;i++)cin>>str[i];
    sort(str,str+n);

    int cnt=0;    
    for(int i=0;i<n;i++)
      for(int j=i+1;j<n;j++)
	if(check(str[i],str[j],d)) cout<<str[i]<<","<<str[j]<<endl,cnt++;
    cout<<cnt<<endl;
  }
  return 0;
}

Measured memory_bytes: 3176
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


signed main() {
  int N, G; 
  cin >> N >> G;

  vector<int> A(N), B(N);
  REP(i, N) cin >> A[i] >> B[i];

  int ans = INF;
  REP(i, (1<<N)){
    int next = -1;
    int ret = 0;
    int point = 0;
    REP(j, N) if((i >> j)&1){
      point += (j+1)*100*A[j]+B[j];
      ret += A[j];
    }else{
      next = j+1;
    }
    if(point < G){
      int required = G-point;
      int cnt = (required+next*100-1)/(next*100);
      if(cnt <= A[next-1]){
        ret += cnt;
        point += cnt*next*100;
      }
    }
    if(point >= G) chmin(ans, ret);
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <unordered_set>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  unordered_set<int> from_set, to_set;

  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    if (a == 1) {
      from_set.emplace(b);
    } 
    if (b == n) {
      to_set.emplace(a);
    }
  }

  bool flag = false;
  for (const int i : from_set) {
    const auto it = to_set.find(i);
    if (it != to_set.end()) {
      flag = true;
      break;
    }
  }

  if (flag) {
    cout << "POSSIBLE" << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}


Measured memory_bytes: 8520
class erat():
    def __init__(self,n):
        self.d = set()
        self.prime = set()
        for i in range(2,n+1):
            ind = 2
            if i not in self.d:
                self.prime.add(i)
            while(True):
                temp = i*ind
                ind += 1
                if temp > n:
                    break
                else:
                    if temp not in self.d:
                        self.d.add(temp)
    def isprime(self,n):
        if n in self.prime:
            return True
        else:
            return False

e = erat(10**5)
arr = [0 for i in range(10**5+1)]
for i in range(3,10**5+1):
    if e.isprime(i) and e.isprime((i+1)//2):
        arr[i] = arr[i-1]+1
    else:
        arr[i] = arr[i-1]
# print(arr[:10])
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(arr[r]-arr[l-1])

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

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

    long long N, K;
    cin >> N >> K;

    double p = 0;
    for (int n=1; n<=N; ++n) {
        long long d = 1;
        while (d*n < K) {
            d *= 2;
        }
        p += 1.0 / ((double)d * N);
    }

    cout << std::setprecision(11) << p << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include <string.h>
using namespace std;
int main(){
	while(1){
		int n;
		cin>>n;
		if(n==0)break;
		int a=0,b=0;
		int x,y;
		for(int i=0;i<n;i++){
			cin>>x>>y;
			if(x>y)a+=x+y;
			if(x==y)a+=x,b+=y;
			if(x<y)b+=x+y;
			
		}
		
		cout<<a<<" "<<b<<endl;
		
	}
	
	return 0;
	
}

Measured memory_bytes: 1160
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), Z = sc.nextInt(), W = sc.nextInt();
		int a[] = new int[N];
		for(int i=0;i<N;i++)a[i]=sc.nextInt();
		sc.close();
		
		int ans = 0;
		
		if(N==1) {
			ans = Math.abs(W - a[N-1]);
			System.out.println(ans);
			return;
		}
		
		if(Math.abs(W - a[N-1]) >= Math.abs(a[N-1] - a[N-2])) ans = Math.abs(W - a[N-1]);
		else ans = Math.abs(Math.abs(a[N-1] - a[N-2]));
		
		System.out.println(ans);
		
		
	}
}

Measured memory_bytes: 26580
from string import ascii_lowercase
def next_permutation(a):
    """Generate the lexicographically next permutation inplace.

    https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
    Return false if there is no next permutation.
    """
    # Find the largest index i such that a[i] < a[i + 1]. If no such
    # index exists, the permutation is the last permutation
    for i in reversed(range(len(a) - 1)):
        if a[i] < a[i + 1]:
            break  # found
    else:  # no break: not found
        return -1  # no next permutation

    # Find the largest index j greater than i such that a[i] < a[j]
    j = next(j for j in reversed(range(i + 1, len(a))) if a[i] < a[j])
    
    return a[:i] + a[j]

s = input()
lower = set(ascii_lowercase)
for c in s:
    if c in lower:
        lower.remove(c)
    else:
        print(-1)
        exit()
if len(lower) > 0:
    lower = sorted(lower)
    print(s+lower[0])

else:
    print(next_permutation(s))

Measured memory_bytes: 3892
n, k = map(int, input().split())
p = [int(i)-1 for i in input().split()]
c = [int(i) for i in input().split()]


def merge(p_a, c_a, p_b, c_b):
    p_c = []
    c_c = []
    for i, j in zip(p_a, c_a):
        p_c.append(p_b[i])
        c_c.append(j + c_b[i])
    return p_c, c_c


ans = -10**18
for i in range(n):
    co = 0
    for _ in range(min(n, k)):
        i = p[i]
        co += c[i]
        ans = max(ans, co)

if k > n:
    pp = p[:]
    cc = c[:]
    for i in range(n):
        c[i] = cc[p[i]]
    k -= n
    a = list(range(n))
    b = [0] * n
    while k > 0:
        if k % 2 == 1:
            a, b = merge(a, b, p, c)
        p, c = merge(p, c, p, c)
        k //= 2

    #print(a, b)
    ans = max(ans,max(b))
    for i in range(n):
        co = b[i]
        i = a[i]
    #    print(i, co)
        for _ in range(n):
            i = pp[i]
            co += cc[i]
    #        print(i, co)
            ans = max(ans, co)
    #    print()

print(ans)


Measured memory_bytes: 69644
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int A = sc.nextInt();
    int B = sc.nextInt();
    
    System.out.println(N*A < B ? N*A : B);
  }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
#define int long long
#define MOD 1000000007
typedef vector<int> vi;
typedef pair<int,int> pi;
#define inf 1e18
#define For(i,a,b) for (int i = a; i < b; i++)
#define Rep(i,a,b) for (int i = a; i <= b; i++)
#define ps(x,y) fixed << setprecision(y) << x 
#define pb push_back 
#define mp make_pair 

int a[105];
 
int32_t main()
{
    fast;
    int n, c = 0; cin >> n;
    For(i, 0, n) {
        cin >> a[i];
        if(a[i] % 2 == 0) c++;
    }

    cout << pow(3, n) - pow(2, c);


    
    
    
    return 0;
}

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

using namespace std;

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

	char& Q = A.back();
	char& W = B.front();
	char& E = B.back();
	char& R = C.front();
	if (Q == W && E == R) {
		cout << "YES" << endl;
	}
	else cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using ll = long long int;
const ll M = 1e18;
using namespace std;
vector <int > rm;
vector <int >::iterator it;
int main()
{
    ll n; cin >> n; ll s = 0;
    if(n % 2) return cout << 0 << '\n' , 0;
    else {
        ll tmp = n >> 1;
        while ( tmp  > 0)
        {
            s += (tmp / 5);
            tmp /= 5;
        }
        cout << min(s , M) << '\n';

    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=2e5+9;
int aa,bb,cc,n;
vector<string>s;
vector<char>v;

void cal(int i,int a,int b,int c){ 
    if(i==n){ 
        if(a>=0&&b>=0&&c>=0){ 
            cout<<"Yes"<<'\n';
            for(int j=0;j<n;j++){ 
                cout<<v[j]<<'\n';
            }
            exit(0);
        }
        return ;
    } 
    if(s[i]=="AB"){ 
        if(a-1>=0){ 
            v.push_back('B');
            cal(i+1,a-1,b+1,c);
            v.pop_back();
        }
        if(b-1>=0){ 
            v.push_back('A');
            cal(i+1,a+1,b-1,c);
            v.pop_back();
        }
    } 
    //***
    if(s[i]=="AC"){ 
        if(a-1>=0){ 
            v.push_back('C');
            cal(i+1,a-1,b,c+1);
            v.pop_back();
        }
        if(c-1>=0){
            v.push_back('A');
            cal(i+1,a+1,b,c-1);
            v.pop_back();
         
        }
    } 
    //****
    if(s[i]=="BC"){ 
        if(c-1>=0){ 
            v.push_back('B');
            cal(i+1,a,b+1,c-1);
            v.pop_back();
        }
        if(b-1>=0){ 
            v.push_back('C');
            cal(i+1,a,b-1,c+1);
            v.pop_back();
           
        }
    } 
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>aa>>bb>>cc;
    for(int i=0;i<n;i++){
        string ss;
        cin>>ss;
        s.push_back(ss);
    } 
    cal(0,aa,bb,cc);
    cout<<"No"<<'\n';
    
    
    return 0;
}


Measured memory_bytes: 16164
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
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(b<a){ a=b; return 1; } return 0; }
using namespace std;

// 0~nまでの排他的論理和
ll xorRange(ll n){
    if(n%4 == 0) return n;
    if(n%4 == 1) return 1;
    if(n%4 == 2) return n^1LL;
    if(n%4 == 3) return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    ll a, b; cin >> a >> b;
    cout << (xorRange(b)^xorRange(--a)) << endl;
}

Measured memory_bytes: 3612
n,m = map(int,input().split())

maxdist = (n-1)//2
maxodd = maxdist if not maxdist%2 == 0 else maxdist-1
maxgusu = maxdist if maxdist%2 == 0 else maxdist-1

count=0

for i,sa in enumerate(range(1,maxodd+1)[::-2]):
    j = i+1
    print(j,j+sa)
    count+=1
    if count==m:
        exit()
for i,sa in enumerate(range(2,maxgusu+1)[::-2]):
    j=i+1
    print(1+maxodd+j,1+maxodd+j+sa)
    count+=1
    if count==m:
        exit()





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

#define ll long long

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int a,b,c,k;
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> k;
    if(k <= a) cout << k;
    else if(k<=b) cout << a;
    else {
        k -= (a+b);
        cout << a-k;
    }
    cout << '\n';
    return 0;
}

Measured memory_bytes: 3584
fn main() {
    use std::io::{stdin, BufRead, BufReader};
    let stdin = stdin();
    let stdin = stdin.lock();
    let stdin = BufReader::new(stdin);
    let mut lines = stdin.lines();
    let a: Vec<u32> = lines.next().unwrap().unwrap().split_whitespace().map(|s| s.parse().unwrap()).collect();
    let total: u32 = lines.next().unwrap().unwrap().split_whitespace().map(|s| s.parse::<u32>().unwrap()).sum();

    println!("{}", if total >= a[0] { "Yes" } else { "No" });
}

Measured memory_bytes: 4352
use std::cmp::max;
fn main() {
    proconio::input! {
        n: usize,
        a: [usize;n],
        q: usize,
        bc: [(usize,usize);q],
    }
    let mut m=*a.iter().max().unwrap();
    for &(b,c) in &bc {
        m=max(m,max(b,c));
    }
    m+=1;
    let mut s=0;
    let mut v=vec![0;m];
    for a in a {
        v[a]+=1;
        s+=a;
    }
    for (b,c) in bc {
        v[c]+=v[b];
        s+=c*v[b];
        s-=b*v[b];
        v[b]=0;
        println!("{}",s);
    }
}

Measured memory_bytes: 6800
#include <iostream>
#define INF (1 << 31) - 1
using namespace std;

typedef pair<int,int> P;

int n,q,cnt = 1;
P dat[300000];

void init(){
	int nn = 1;
	while(nn < n) nn *= 2;
	n = nn;
	for(int i = 0;i < n * 2 - 1;i++){
		dat[i] = P(INF,0);
	}
}

void update(int a,int b,int x,int k,int l,int r){
	if(r <= a || b <= l) return;
	if(a <= l && r <= b){
		dat[k] = P(x,cnt);
		return;
	}
	update(a,b,x,k * 2 + 1,l,(l + r) / 2);
	update(a,b,x,k * 2 + 2,(l + r) / 2,r);
}

int get(int i){
	i = i + n - 1;
	int last = dat[i].second,val = dat[i].first;
	while(i){
		i = (i - 1) / 2;
		if(last < dat[i].second){
			last = dat[i].second;
			val = dat[i].first;
		}
	}
	return val;
}

int main(){
	cin >> n >> q;
	init();
	for(int i = 0;i < q;i++){
		int v;
		cin >> v;
		if(v == 0){
			int s,t,x;
			cin >> s >> t >> x;
			update(s,t + 1,x,0,0,n);
			cnt++;
		}
		else{
			int x;
			cin >> x;
			cout << get(x) << endl;
		}
	}
	return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}

template <typename T>
T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

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

  int n;
  cin >> n;
  vector<int> a(n);
  int nxt = 1;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] == nxt) nxt++;
  }
  int ret = n - (nxt - 1);
  cout << (ret < n ? ret : -1) << endl;
}


Measured memory_bytes: 1024