akhauriyash/Code-Regression huggingface dataset:
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}


int main()
{

   fastread();

   ll i,j,n,m,p,a,k,t,b,c,d,cnt=0,q,l,r;

   double ans=0;

      bool flag=false;

      string str;


      long double sum=0;

      cin>>n>>k;


       for(i=1; i<=n; i++)
       {
           if(i>k)
           {
               sum+=n-i+1;
               break;


           }


           long double value=1.0;

           a=i;

           while(a<k)
           {
               a*=2;

               value/=2;


           }

           //cout<<value<<endl;

           sum+=value;
       }

       sum/=n;
      cout<<setprecision(12)<<fixed<<sum<<endl;















}



Measured memory_bytes: 3672
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]

for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i + j)

print(ans)

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

int main() {
    int64_t a, b;
    cin >> a >> b;
    int64_t x = a * b;
    if (a < b) swap(a, b);
    int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    int64_t ans = x / b;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	int n, k; cin >> n >> k;
	string str; cin >> str;
	char c_min = 'z';
	for( char c : str ) c_min = min( c, c_min );
	if( k < 14 ){
		string tmp = "";
		while( k-- ){
			tmp += str; reverse( str.begin(), str.end() );
			tmp += str;
			if( k > 0 ) reverse( tmp.begin(), tmp.end() );
			vector<string> candy;
			for( int i = 0; i <= n; ++i ){
				candy.push_back( tmp.substr(i, n) );
			}
			sort( candy.begin(), candy.end() );
			str = candy.front();
			if( k > 0 ) reverse( str.begin(), str.end() );
			// cout << str << endl;
			tmp = "";
			if( k == 0 ){
				cout << str << endl;
				return 0;
			}
		}
	}
	else{
		string ans = "";
		while( n-- ){
			ans += c_min; 
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 40268
#include <bits/stdc++.h>
#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define rep(i,l,r) for(int i=l;i<r;i++)
#define bep(i,l,r) for(int i=l;i>=r;i--)
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define el '\n'
#define sz(s) s.size()
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define mr  make_pair
using namespace std;
int mod = 1e9+7;
int inf = 1e18;
const int N = 5e5+999;
int powmod(int a,int b) {int res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}
int arr[N];
signed main()
{
    io
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
        char ch;
        cin>>ch;
        if(ch=='z')
            cout<<"a"<<el;
        else
        {
            cout<<char(++ch);
        }
    }
   return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <queue>
#include<iomanip>
#include <cmath>
#include <set>

#define ABS(x) ((x)>0?(x):-(x))
#define MIN(x,y) ((x)>(y)?(y):(x))

using namespace std;
typedef long long ll;

ll newton(long long int a, long long int  b)
{
	if(a==b)
		return a;
	while(a != 0 && b != 0)
	{
		if(a > b)
		{
			b += a;
			a = b-a;
			b -= a;
		}
		b %= a;
	}
	return a;
}

struct UnionFind {
	vector<int> p;
	UnionFind(int N):p(N)
	{
		for(int i=0; i< N; i++)
		{
			p[i] = i;
		}
	}
	int root(int x)
	{
		if(p[x] == x)
			return x;
		return p[x] = root(p[x]);
	}
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if(rx == ry) return;
		p[rx] = ry;
	}
	bool issame(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

//大きな数に対する割り算をするとき、MODを指定することで掛け算の値に変換できる

ll div2mul_calc(ll a, ll b, ll m)
{
	if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        ll d = div2mul_calc(a, b / 2, m);
        return (d * d) % m;
    } else {
        return (a * div2mul_calc(a, b - 1, m)) % m;
    }
}
ll div2mul(ll n, ll mod)
{
	return div2mul_calc(n, mod-2, mod);
}

int main()
{
	int i,j,k;
	int s,t,x;
	int N,M;
	int mp[16][16] = {0};
	int req[16] = {0};
	cin >> N >>M;
	for(i=0;i<M;++i)
	{
		cin >> k;
		for(j=0;j<k;++j)
		{
			cin >> s;
			mp[i][s-1] = 1;
		}
	}
	for(i=0;i<M;++i)
	{
		cin >> req[i];
	}
	int c[16] = {0};
	int ans = 0;
	int mx = 1 << N;
	for(i=0;i<mx;++i)
	{
		for(j=0;j<M;++j)
		{
			c[j] = 0;
		}
		for(j=0;j<N;++j)
		{
			if(i&(1<<j))
			{
				for(k=0;k<M;++k)
				{
					c[k] += mp[k][j];
				}
			}
		}
		x = 1;
		for(j=0;j<M;++j)
		{
			if((c[j]&1) != req[j])
			{
				x = 0;
			}
		}
		ans += x;
	}
	cout << ans << endl;
	/*
	int N,Q;
	int s,t,x;
	int i,j,k;
	priority_queue<pair<int, int> > q_s,q_e;

	cin >> N >> Q;
	for(i=0; i< N ; ++i)
	{
		cin >> s >> t >> x;
		s -= x;
		t -= x;
		if(s < 0)
			s = 0;
		if(t < 0)
			t = 0;
		q_s.push(make_pair(-s,x));
		q_e.push(make_pair(-t,x));
	}
	int kouji = 0;
	int ans = -1;
	for(i=0;i < Q; ++ i)
	{
		ans = -1;
		cin >> s;
		while(!q_s.empty())
		{
			if(-q_s.top().first =< s)
			{
				kouji ++;

			}
			else
		}
		while(!q_e.empty())
		{

		}
	}
	*/
	return 0;
}




































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

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
string n;
cin>>n;
int n_s=n.size();
if(n[n_s-1]=='3'){
    cout<<"bon"<<endl;
}
else if(n[n_s-1]=='0'||n[n_s-1]=='1'||n[n_s-1]=='6'||n[n_s-1]=='8'){
    cout<<"pon"<<endl;
}
else{
    cout<<"hon"<<endl;
}
return 0;
}

Measured memory_bytes: 3652
n = int( input() )

n_list = [ 0 for _ in range( 10 ** 4 + 1 ) ]

def g( x, y, z ):
    return min( x * x + y * y + z * z + x * y + y * z + z * x, 10 ** 4 + 1 )

for x in range( 1, 101 ):
    for y in range( 1, 101 ):
        for z in range( 1, 101 ):
            n_list[ g( x, y, z ) - 1 ] += 1

for k in range( n ):
    print( n_list[ k ] )

Measured memory_bytes: 9248
if __name__ == '__main__':

	a,b,c,x,y = map(int,input().split())

	#A,Bのみで買った場合
	tmp1 = (a * x) + (b * y)

	#A-Bで買った場合 量は2倍になる
	mi = min(x,y)

	tmp2 = mi * c * 2

	#A-Bで買った場合 残りの判定
	if x - mi == 0:
		#Bをそのまま買う
		tmp3 = b * (y - mi)
		
		#ABを買う(残りのAは捨てる)
		tmp4 = c * (y - mi) * 2
		
		tmp2 += min(tmp3,tmp4)
		
	else:
		#Aをそのまま買う
		tmp3 = a * (x - mi)
		
		#ABを買う(残りのBは捨てる)
		tmp4 = c * (x - mi) * 2
		
		tmp2 += min(tmp3,tmp4)

	#判定
	print(min(tmp1,tmp2))



Measured memory_bytes: 9144
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
s = sum(a)
count = Counter(a)
q = int(input())
b_c = [list(map(int, input().split())) for i in range(q)]
for i in b_c:
  s += (i[1] - i[0]) * count[i[0]]
  count[i[1]] += count[i[0]]
  count[i[0]] = 0
  print(s)

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

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> data(n);
    for(int i = 0; i <n; i++){
        cin >> data[i];
    }
    int bote_sum = accumulate(data.begin(), data.end(), 0);
    double border = bote_sum / (4.0 * m);
    // cout << border << endl;
    sort(data.begin(), data.end(), greater<int>());
    // rep(i, data.size()) cout << data[i] <<endl;
    int counter = 0;
    for(int i = 0; i < n; i++){
        if(data[i] >= border){
            counter++;
        }
    }
    if(counter >= m ){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

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

using ll = long long;
using ull = unsigned long long;

#define MOD 1000000007

int main(void) {
    ll H, W;
    cin >> H >> W;
    for(ll h = 0;h < H;h++) {
        string line;
        cin >> line;
        for(ll i = 0;i < W;i++) cout << line[i];
        cout << endl;
        for(ll i = 0;i < W;i++) cout << line[i];
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                int a = sc.nextInt();
                int b = sc.nextInt();
                int c = sc.nextInt() - a;
                int d = sc.nextInt() - b;
                sc.close();
                for(int i = 0 ; i < c ; i++){
                        System.out.print("R");
                }
                for(int i = 0 ; i < d ; i++){
                        System.out.print("U");
                }
                for(int i = 0 ; i < c ; i++){
                        System.out.print("L");
                }
                for(int i = 0 ; i <= d ; i++){
                        System.out.print("D");
                }
                for(int i = 0 ; i <= c ; i++){
                        System.out.print("R");
                }
                for(int i = 0 ; i <= d ; i++){
                        System.out.print("U");
                }
                System.out.print("LU");
                for(int i = 0 ; i <= c ; i++){
                        System.out.print("L");
                }
                for(int i = 0 ; i <= d ; i++){
                        System.out.print("D");
                }
                System.out.println("R");
        }
}

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

using namespace std;
using ll = long long;

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

int main() {
  int n, d;
  cin >> n >> d;
  int k = 2 * d + 1;
  int ans = (n + k - 1) / k;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3576
#include <algorithm>
#include <array>
#include <assert.h>
#include <chrono>
#include <bitset>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <numeric>
#include <random>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<ld>> vvld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<pll> vpll;

#ifdef OLBOEB
mt19937 rnd(228 + 1488 + 238 + 24111997 % 322);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

void print_time() {
#ifdef OLBOEB
    cout.flush();
    cerr << "\ntime: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
}

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }


const ll MAXN = 228;
ll n;
bool g[MAXN][MAXN];
const ll INF = 1e9;

ll bfs(ll s) {
    queue<ll> q;
    vb used(n);
    vl depth(n, +INF);
    q.push(s);
    depth[s] = 0;
    used[s] = true;
    ll maxd = 0;

    while (!q.empty()) {
        ll v = q.front();
        q.pop();
        for (ll u = 0; u < n; ++u) {
            if (used[u] || !g[v][u]) continue;
            used[u] = true;
            depth[u] = depth[v] + 1;
            maxd = max(maxd, depth[u]);
            q.push(u);
        }
    }
    for (ll v = 0; v < n; ++v) {
        for (ll u = v + 1; u < n; ++u) {
            if (g[v][u] && ((depth[v] - depth[u]) % 2 == 0)) {
                cout << -1 << endl;
                exit(0);
            }
        }
    }
    return (maxd + 1);
}


int main() {
    cout << fixed << setprecision(20);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n;
    for (ll i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (ll j = 0; j < n; ++j) {
            g[i][j] = s[j] == '1';
        }
    }

    ll ans = 0;
    for (ll i = 0; i < n; ++i) {
        ans = max(ans, bfs(i));
    }

    cout << ans << endl;

    print_time();
    return 0;
}



Measured memory_bytes: 384
//解説と回答例を参考にした

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

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



int main(){
    int N;
    cin>>N;
    vector<vector<int>> G(N);
    vector<pair<int,int>> vp;

    for(int i=1;i<N;i++){
        int a,b;
        cin>>a>>b;
        a--,b--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
        vp.emplace_back(a,b);
    }

    int K=0;//色の数
    map<pair<int,int>,int> I;
    vector<int> cs(N,0);//色を保管する

    vector<int> used(N,0);//探索済みか否かを保管する配列
    queue<int> que;
    used[0]=1;
    que.emplace(0);
    while(!que.empty()){//幅優先探索
        int v=que.front();que.pop();
        if(K<(int)G[v].size())K=G[v].size();//Kの数は隣接頂点の数あるため
        int cur=1;//色
        for(int u:G[v]){//辿れる頂点を探索
            if(used[u])continue;//色を塗ってあるなら
            if(cur==cs[v])cur++;//現在の色が探索元頂点塗ってある色と同色なら
            cs[u]=I[make_pair(u,v)]=I[make_pair(v,u)]=cur++;
            //色を塗りながら探索先頂点に色を塗る
            used[u]=1;
            que.emplace(u);
        }
    }
    cout<<K<<endl;
    for(auto p:vp)cout<<I[p]<<endl;
    return 0;
}

//a=97,z=122

Measured memory_bytes: 20084
def divisors(n):
	res = []
	for i in range(1,int(n**0.5) + 1):
		if n % i == 0:
			res.append(i)
			if i != n//i:
				res.append(n//i)
	res.sort()
	return res

if __name__ == '__main__':
	d = [int(s) for s in input().split()]
	c = 0
	for i in divisors(d[2]):
		if d[0] <= i and d[1] >= i:
			c = c+1
	print(c)


Measured memory_bytes: 5640
#include <bits/stdc++.h>
#define rep(i, s, e) for(int i = s; i < e; i++)
#define rrep(i, s, e) for(int i = s; i > (s)-(e); i--)
#define pr(s) std::cout << s << std::endl
#define prb(s) std::cout << s
using namespace std;



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


  int a, b, c;
  cin >> a >> b >> c;

  if (b-a == c-b) pr("YES");
  else pr("NO");


  return 0;
}


Measured memory_bytes: 256
import sys
readline = sys.stdin.buffer.readline
def main():
    n = int(readline())
    s = set([int(i) for i in readline().split()])
    q = int(readline())
    t = [int(i) for i in readline().split()]
    ans = 0
    for i in t:
        if i in s:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 14124
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

static void predict_weather(char *str);

int main(void){
  char str[7];
  cin >> str;

  predict_weather(str);
  return 0;
}

static void predict_weather(char *str){
  if(strcmp(str, "Sunny") == 0){
    cout << "Cloudy" << endl;
  } else if(strcmp(str, "Cloudy") == 0){
    cout << "Rainy" << endl;
  } else if(strcmp(str, "Rainy") == 0){
    cout << "Sunny" << endl;
  }

}

Measured memory_bytes: 256
N = int(input())
D = [int(v) for v in input().split(' ')]

Ds = list(sorted(D))
p = int(len(D) / 2)
DsL = Ds[p - 1]
DsR = Ds[p]
Ks = DsL + 1
Ke = DsR

print(Ke - Ks + 1)

Measured memory_bytes: 14428
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define YESNO(i) puts((i)?"YES":"NO");
#define YesNo(i) puts((i)?"Yes":"No");
#define yesno(i) puts((i)?"yes":"no");
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll l,r,d;cin>>l>>r>>d;
  print(r/d-(l-1)/d);
  return 0;
}

Measured memory_bytes: 3596
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include <cmath>
#include<algorithm>
//#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;

int main(){
    int A,B,C,K;
    cin>>C>>B>>A>>K;
    int i=0;
    while (B<=C){
        B=B*2;
        i++;
    }
    if (i>K){
        cout<<"No"<<endl;
        return 0;
    }
    while (A<=B){
        A=A*2;
        i++;
    }
    if (i<=K) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
 return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = INT_MAX;
const long long INFL =LONG_LONG_MAX;
const double PI = atan(1)*4;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

ll gcb(ll a, ll b){/// ユークリッドの互除法: O(log)
    
    if(b == 0) return a;
    
    return gcb(b,a%b);
}


ll lcm(ll a, ll b){
    
    return  a/gcb(a,b) * b; ///gcbは約数
}


int main() {
    ll n,m;cin>>n>>m;
    string s,t;cin>>s>>t;
    
    ll v = (ll)lcm(n,m);
    
    map<ll,char> out;
    
    for(auto i = 0;i<n;i++){
        out[ i*(v/n) + 1 ] = s[i];
    }
    
    for(auto i = 0;i<m;i++){
        if(out.count( i*(v/m) + 1) == 0)continue;
        else if (out[ i*(v/m) + 1 ] != t[i]){ cout<<-1<<endl; return 0;}
    }
    
    cout<<v<<endl;
    


    
    return 0;
}










Measured memory_bytes: 6144
H,W = [int(x) for x in input().split()]
A = [list(input()) for _ in range(H)]
#%%
def dfs(h,w):
    if(A[h][w]=='.'):
        return False
    else:
        A[h][w]='.'
        x = False
        if(w<W-1):
            x = dfs(h,w+1)
        if(not x and h<H-1):
            dfs(h+1,w)
        return True

dfs(0,0)
for a in A:
    if('#' in a):
        print('Impossible')
        break
else:
    print('Possible')


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n,m, x,y,a;
vector<int> vecx, vecy;
int main() {
	cin >> n >> m >> x >> y;
	for (int i = 0; i < n; i++) {
		cin >> a;
		vecx.push_back(a);
	}
	sort(vecx.begin(), vecx.end());
	for (int i = 0; i < m; i++) {
		cin >> a;
		vecy.push_back(a);
	}
	sort(vecy.begin(), vecy.end());
	for (int i = vecx[n - 1]+1; i <= vecy[0]; i++) {
		if (x < i&&i <= y) {
			cout << "No War" << '\n';
			return 0;
		}
	}
	cout << "War" << '\n';
	return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define loop(i,L,R) for(int i=(L);i<=(R);i++)
#define rept(i,L,R) for(int i=(L);i<(R);i++)
#define isc(n) scanf("%d",&n)
#define llsc(n) scanf("%lld",&n)
#define dsc(n) scanf("%lf",&n)
#define enl cout<<endl
#define pb(x) push_back(x)
#define xx first
#define yy second
typedef long long ll;
typedef pair<int,int>PI;
typedef pair<pair<int,int>,int>PII;
const int mx=1e5+10;
int arr[mx],prime[mx],cum[mx];
int main()
{
	for(int i=2;i<mx;i++)
	{
        if(arr[i]==0)
        {
            prime[i]=1;
            for(int j=i*2;j<mx;j+=i)arr[j]=1;
        }
	}
	for(int i=1;i<mx;i++)
	{
        if(prime[i] && prime[(i+1)/2])cum[i]=1;
        cum[i]+=cum[i-1];
       // if(i<100)cout<<i<<" "<<cum[i]<<endl;
    }
    int n,l,r;
    cin>>n;
    while(n--)
    {
        cin>>l>>r;
        cout<<cum[r]-cum[l-1]<<endl;
    }
	return 0;
}


Measured memory_bytes: 1792
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]

check = [[1] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if i == k or j == k:
                pass
            else:                    
                if d[i][j] > d[i][k] + d[k][j]:
                    print (-1)
                    exit()
                elif d[i][j] == d[i][k] + d[k][j]:
                    check[i][j] = 0

ans = 0
for i in range(N):
    for j in range(N):
        ans += d[i][j] * check[i][j]

print (ans // 2)    

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

typedef long long ll;

int S(int x){
    int dsum = 0;

    while (x>0){
        dsum += (x%10);
        x /= 10;
    }

    return dsum;
}

int main(){
    int x;

    cin >> x;

    int dsum = S(x);

    if (x%dsum == 0){
        cout << "Yes" << endl;
    } else{
        cout << "No" << endl;
    }

}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

// PfsMap : 素因数分解し、マップを作成
func PfsMap(n int) map[int]int {
	pfs := make(map[int]int)
	for n%2 == 0 {
		pfs[2] = pfs[2] + 1
		n = n / 2
	}

	for i := 3; i*i <= n; i = i + 2 {
		for n%i == 0 {
			pfs[i] = pfs[i] + 1
			n = n / i
		}
	}

	if n > 2 {
		pfs[n] = pfs[n] + 1
	}

	return pfs
}

func main() {
	sc.Split(bufio.ScanWords)

	N, P := getInt(), getInt()
	psf := PfsMap(P)
	ans := 1
	for i, v := range psf {
		for v >= N {
			ans *= i
			v -= N
		}

	}
	out(ans)
}


Measured memory_bytes: 640
x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
s = p[0:x]+q[0:y]+r
s.sort(reverse=True)
print(sum(s[0:x+y]))

Measured memory_bytes: 112236
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

#define rep(i, n) for(int i=0; i<int(n);i++)
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> PI;
typedef pair<int, PI> tt;
int main() {
  int n;
  while(cin >> n, n) {
    int P[50], T[50];
    rep(i, n) cin >> P[i] >> T[i];
    priority_queue<tt> Q;
    set<PI> M;
    Q.push(mp(0, mp(0, 0)));
    int taken = 0;
    int ans = 1<<29;
    while(!Q.empty()) {
      int t = -Q.top().F, cnt = Q.top().S.F, k = Q.top().S.S;
      Q.pop();
      if (M.count(mp(cnt, k))) continue;
      M.insert(mp(cnt, k));

      taken = max(taken, k);
      if (k == n) {
        ans = min(ans, t + P[k-1]);
        continue;
      }

      if (cnt > 0) {
        int at = t + P[k-1] + P[k];
        int time = T[k-1] + P[k-1] * (cnt+1) + P[k];
        if (time <= T[k]) {
          Q.push(mp(-at, mp(1, k+1)));
        }
      }
      {
        int at = k>0 ? t + abs(P[k] - P[k-1]) : t + P[k];
        int time = k>0 ? T[k-1] + abs(P[k] - P[k-1])*(cnt+1) : P[k];
        if (cnt+1 <= 3 && time <= T[k])
          Q.push(mp(-at, mp(cnt+1, k+1)));
      }

    }
    if (taken < n) cout << "NG " << taken+1 << endl;
    else cout << "OK " << ans << endl;
  }
}

Measured memory_bytes: 1200
n = int(input())
ad = []
for i in range(n):
    ad.append([int(i) for i in input().split()])

#dp[p][q]
#p = 何日目
#q = p日目にqをした時のp日目までの最大幸福度 <- どれを選んだかが問題にならない
dp = [[0,0,0]]
#ads = []
#tmp = []

for i in range(1,n+1):
    if i == 1:
        a = ad[i-1][0]
        b = ad[i-1][1]
        c = ad[i-1][2]
        dp.append([a,b,c])
    else:
        dp.append([max(dp[i-1][1] + ad[i-1][0],dp[i-1][2] + ad[i-1][0]),max(dp[i-1][0] + ad[i-1][1],dp[i-1][2] + ad[i-1][1]),max(dp[i-1][0] + ad[i-1][2],dp[i-1][1] + ad[i-1][2])])
print(max(dp[n]))

"""
for i in range(3): #最初に選んだのがi
    for j in range(1,n+1): #j日目
        if j == 1:
            dp.append(dp[j-1]+ad[j-1][i])
            former = i
        else:
            if dp[j-1]+ad[j-1][dic[former][0]] <  dp[j-1]+ad[j-1][dic[former][1]]:
                dp.append(dp[j-1]+ad[j-1][dic[former][1]])
                former = dic[former][1]
            else:
                dp.append(dp[j-1]+ad[j-1][dic[former][0]])
                former = dic[former][0]
        #print(former)
    #print(dp[1:])
    ls.append(dp[n])
    dp = [0]
print(max(ls))
"""
"""
for i in range(3):#1日目の選択
    for j in range(2):#2日目の選択
        for k in range(1,n+1): #n日目まで
            if k == 1:
                dp.append(dp[k-1]+ad[k-1][i])
            elif k == 2:
                dp.append(dp[k-1]+ad[k-1][dic[i][j]])
            else:
                if k == 3:
                    former = dic[i][j]
                if dp[k-1]+ad[k-1][dic[former][0]] <  dp[k-1]+ad[k-1][dic[former][1]]:
                    dp.append(dp[k-1]+ad[k-1][dic[former][1]])
                    former = dic[former][1]
                else:
                    dp.append(dp[k-1]+ad[k-1][dic[former][0]])
                    former = dic[former][0]
        #print(i,j)
        #print(dp)
        ls.append(dp[n])
        dp = [0]
print(max(ls))
"""
"""
#dp[p][q]
#p = 何日目
#q = p日目にqをした時のp日目までの最大幸福度
dp = [[0,-1]]
ads = []
tmp = []

former = [[-1,-1]]
dic = {0:[1,2],1:[0,2],2:[0,1]}
ls = []
for i in range(3):#最初の1つ
    for k in range(1,n+1): #n日目まで
        if k == 1:
            ads.append(dp[k-1][0]+ad[k-1][i])
            former.append([i,i])#1日目
        elif k != n:
            #次の日の候補
            alpha = dic[former[k-1][0]]
            beta  = dic[former[k-1][1]]
            former.append([alpha,beta])
            if dp[k-1] + ad[alpha] + ad[dic[alpha][0]] < dp[k-1] + ad[alpha] + ad[dic[alpha][1]]):
                ads.append()
            if dp[k-1] + ad[beta] + ad[dic[beta][0]] < dp[k-1] + ad[beta] + ad[dic[beta][1]]:

            print(dp)
            dp.append(ads)
            ads = []

            tmp = []



        #print(i,j)
        #print(dp)
        ls.append(max(dp[n]))
        dp = [[0,0]]
print(max(ls))
"""


Measured memory_bytes: 70616
N=int(input())
List = list(map(int, input().split()))
AList=[0]

cnt=0
i=0
while i<N:
    if i==0:
        Mae=List[0]
    elif i==N-1 and List[i]<=Mae:
        AList.append(cnt+1)
    elif i==N-1:
        AList.append(cnt)
    elif List[i]<=Mae:
        Mae=List[i]
        cnt+=1
    else:
        AList.append(cnt)
        Mae=List[i]
        cnt=0
    #print(Mae)
    i+=1

#print(AList)
print(max(AList))



Measured memory_bytes: 14228
using System;

namespace ABC076D
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] t = new int[N + 1];
            int[] v = new int[N + 1];

            string[] bufs = Console.ReadLine().Split(' ');
            for (int i = 0; i < N; i++)
            {
                t[i] = int.Parse(bufs[i]);
            }
            t[N] = 999;

            bufs = Console.ReadLine().Split(' ');
            for (int i = 0; i < N; i++)
            {
                v[i] = int.Parse(bufs[i]);
            }
            v[N] = 0;
            // END Initialize //

            // Recurrsive Speed Limit
            for (int i = N - 1; i >= 0; i--)
            {
                if (v[i] > v[i + 1] + t[i])
                {
                    v[i] = v[i + 1] + t[i];
                }
            }


            double curv = 0.0;
            int curt = 0;
            double dist = 0.0;

            for (int i = 0; i < N; i++)
            {
                double upTime = Math.Min(v[i] - curv, t[i]);
                double downTime = Math.Max((curv + upTime) - v[i + 1], 0.0);
                double flatTime = t[i] - upTime - downTime;

                if (flatTime < 0)
                {
                    flatTime = 0;
                    double cross = ((v[i + 1] + t[i]) - curv) / 2.0;
                    upTime = cross;
                    downTime = t[i] - cross;
                }

                if (upTime > 0)
                {
                    dist += upTime * ( 2 * curv + upTime ) / 2.0;
                    curv += upTime;
                }
                dist += flatTime * v[i];
                if (downTime > 0) {
                    dist += downTime * (curv + v[i + 1] ) / 2.0;
                    curv = v[i + 1];
                }

                curt += t[i];
            }


            Console.WriteLine(dist.ToString("F4"));
        }
    }
}


Measured memory_bytes: 13140
# ARC086D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


n = int(input())
a = list(map(int, input().split()))

m = max([abs(item) for item in a if item<=0] + [0])
M = max([abs(item) for item in a if item>=0] + [0])

def sub(i, j, a):
    print(i, j)
    a[j-1] += a[i-1]
    
print(2*n-1)
if M >= m:
    ind = a.index(M)+1
    for i in range(1,n+1):
        if i==ind:
            continue
        sub(ind, i, a)
    sub(ind, 1, a)
    for i in range(1, n):
        sub(i, i+1, a)
else:
    ind = a.index(-m)+1
    for i in range(1,n+1):
        if i==ind:
            continue
        sub(ind, i, a)
    sub(ind, n, a)
    for i in range(n, 1, -1):
        sub(i, i-1, a)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
  ll n;
  cin >> n;
  vl a(n);
  rep(i,n){
    cin >> a[i];
  }
  ll ans=INF;
  FOR(i,-100,101){
    ll k=0;
    rep(j,n){
      k+=(a[j]-i)*(a[j]-i);
    }
    ans=min(ans,k);
  }
  cout << ans << endl;
}

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

int main(){

 int x, y;

 while(1) {
  cin >> x >> y;
  if ((x == 0) && (y == 0)) break;
  if (x > y) {
   cout << y << " " << x << "\n";
  } else {
   cout << x << " " << y << "\n";
  }
 }

 return 0;
}

Measured memory_bytes: 1160
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        int n;
        int k;
        try (Scanner sc = new Scanner(System.in)) {
            n = sc.nextInt();
            k = sc.nextInt();
        }
        if (k == 1) {
            System.out.println(0);
            return;
        }
        System.out.println(n -k);
    }
}


Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define MAX 100000
#define NIL -1

int n;
vector<int> G[MAX];
int color[MAX];

void dfs(int r, int c){
    stack<int> S;
    S.push(r);
    color[r] = c;
    while(!S.empty()){
        int u = S.top(); S.pop();
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i];
            if (color[v] == NIL){
                color[v] = c;
                S.push(v);
            }
        }
    }
}

void assignColor(){
    int id = 1;
    for(int i=0; i<n; ++i) color[i] = NIL;
    for(int u=0; u<n; ++u){
        if (color[u] == NIL) dfs(u, id++);
    } 
}

int main(){
    int s, t, m, q;
    cin >> n >> m;
    for(int i=0; i<m; ++i){
        cin >> s >> t;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    
    assignColor();
    
    cin >> q;
    for(int i=0; i<q; ++i){
        cin >> s >> t;
        if (color[s] == color[t]){
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
    
    return 0;
}

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

namespace AOJ
{
	class Program
	{
		static void Main(string[] args)
		{
			int r = 0;
			var s = "";
			while ((s = Console.ReadLine()) != null)
			{
				foreach (Match m in Regex.Matches(s, "\\d+"))
				{
					r += int.Parse(m.Value);
				}
			}
			Console.WriteLine(r);
		}
	}
}

Measured memory_bytes: 6936
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a[105][105]={};
  cin >> n;
  for(int i=0;i<n;i++){
    int u,k;
    cin >> u >> k;
    for(int j=0;j<k;j++){
      int v;
      cin >> v;
      a[u-1][v-1]=1;
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(j)cout << " " ;
      cout << a[i][j];
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
//priority_queue<int, vector<int>, greater<int> > pq;
#define _CRT_SECURE_NO_DEPRECATE
const int N = 300030;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =  1e9+7;
ll n,w;
ll dp[N];
vector<pair<ll,ll> > v;
int main()
{
    ios::  sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>w;
	rep(i,0,n)
	{
		ll x,y;
		cin>>x>>y;
		rep(j,w-x+1,0)
		{
			dp[j+x]=max(dp[j+x],y+dp[j]);
		}
	}
	cout<<dp[w];
	
}






Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {

            int[] vs = RArInt();
            bool b = false;
            if (vs[0]<vs[1])
            {
                if (vs[0] < vs[2] && vs[2] < vs[1])
                {
                    b = true;
                }
            }
            else
            {
                if (vs[1] < vs[2] && vs[2] < vs[0])
                {
                    b = true;
                }
            }
            Console.WriteLine(b ? "Yes" : "No");

        }
        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RArSt(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RArInt(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RArLong(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RArDouble(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }
}


Measured memory_bytes: 11092
H, W =  [int(item) for item in input().split()]
hl = [0] * H
wl = [0] * W
m = []
for h in range(H):
  rows = input().rstrip()
  m.append(rows)
  for w in range(W):
    if rows[w] == ".":
      hl[h] += 1
      wl[w] += 1

for h in range(H):
  if not hl[h] == W :
    for w in range(W):
      if not wl[w] == H:
        print(m[h][w], end="")
    print("")

Measured memory_bytes: 4468
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long,long>> vpll;
typedef vector<pair<int,int>> vpii;
int main() {
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall

	ins(a);
	int i = 0;
	int i1 = a.size()-1;
	while(i1!=-1){
		if(a[i]!=a[i1]){
			out("No");
			return 0;
		}
		i++;
		i1--;
	}
	i = 0;
	i1 = (a.size()-1)/2-1;
	while(i1!=-1){
		if(a[i]!=a[i1]){
			out("No");
			return 0;
		}
		i++;
		i1--;
	}
	i = (a.size()+3)/2-1;
	i1 = (a.size() - 1);
	while(i!=a.size()){
		if(a[i]!=a[i1]){
			out("No");
			return 0;
		}
		i++;
		i1--;
	}
	out("Yes");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define fr(i,a,b) for(ll i=a; i<b; i++)
#define rf(i,a,b) for(ll i=a; i>=b; i--)
typedef std::vector<long long > vi ;
#define F first
#define S second
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 1000000007
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define mx(a) *max_element(all(a))
#define mn(a) *min_element(all(a))
#define endl '\n'
using  namespace std; 
int main()
{
    fast;
   ll t=1;
   //std::cin >> t;
   while(t--)
   {
       ll n,x,m;
       std::cin >> n>>x>>m;
       ll a[m+2]={0},r,ans=0,d=x;
       ll mp[m+2]={0};
       if(n>m)
       {fr(i,1,m+2)
       {
          a[i]=a[i-1]+x%m;
          x=x%m;
          if(mp[x]==0)
          {
              mp[x]=i;
          }
          else
          {
              r=a[i]-a[mp[x]];
              ll nt=i-mp[x];
              ans=ans+((n-mp[x]+1)/nt)*r+a[((n-mp[x]+1)%nt)+mp[x]-1];
              break;
          }
          x=(x*x)%m;
       }
           cout<<ans<<"\n";
       }
       else
       {
           fr(i,1,n+1)
           {
               ans=ans+x%m;
               x=x%m;
               x=x*x;
           }
           cout<<ans<<"\n";
       }
   
   }
   
}

Measured memory_bytes: 5200
def find(l, e, start, end):
	mid = (start+end)//2
	if (l[mid] == e):
		return (e, e)
	elif (l[mid] > e):
		if (l[mid-1] < e):
			return (l[mid-1], l[mid])
		return find(l, e, start, mid)
	elif (l[mid] < e):
		if (l[mid+1] > e):
			return (l[mid], l[mid+1])
		return find(l, e, mid, end)

def print_sum(input):
	d, n, m = input[0], input[1], input[2]
	S, K = input[3:3+n-1], input[3+n-1:]
	S = [0] + sorted(S) + [d]
	sum = 0
	for k in K:
		low, high = find(S, k, 0, len(S))
		sum += min(k-low, high-k)
	print sum

while (True):
	d = int(raw_input())
	if d == 0: break
	n, m = int(raw_input()), int(raw_input())
	input = [d, n, m]
	for i in range(n-1+m):
		next_int = int(raw_input())
		input.append(next_int)
	print_sum(input)

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    string s;
    cin >> s;
    vector<long long> base;
    for (int i = n - 1; ~i; i--) {
      for (auto u : base) {
        a[i] = min(a[i], a[i] ^ u);
      }
      if (s[i] == '0') {
        base.push_back(a[i]);
      } else if (a[i] > 0) {
        cout << 1 << '\n';
        break;
      }
      if (i == 0) {
        cout << 0 << '\n';
      }
    }
  }
  return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,i,j;
	cin>>n;
	string s="ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
	string s1;
	cin>>s1;
	for (i=0;i<s1.length();i++)
	{
		for (j=0;j<s.length();j++)
		{
			if (s[j]==s1[i])
			{
				s1[i]=s[j+n];
				break;
			}
		}
	}
	cout<<s1<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
ll K;
  cin>>K;
  
  ll count=0;
  queue<string> S;
  S.push("1");
  S.push("2");
  S.push("3");
  S.push("4");
  S.push("5");
  S.push("6");
  S.push("7");
  S.push("8");
  S.push("9");
  string ans;

  while(count<K) {
    string W=S.front();
    S.pop();
    count++;
    if(count==K) {
ans=W;
    }
    for(ll i=W.back()-'0'-1;i<=W.back()-'0'+1;i++) {
if(i<0||i>9) {
continue;
}
   S.push(W+to_string(i));
    }
  }
  
  cout<<ans<<endl;
}
   


  
  
  


Measured memory_bytes: 9756
#include<stdio.h> 
long long fiboDP(int n) {
   long long fibodp[200] = {0};
   fibodp[0] = 1;
   fibodp[1] = 1;
   for(int i=2; i<=n; i++) {
       fibodp[i] = fibodp[i-1] + fibodp[i-2];
       }
       return fibodp[n];
       }
       int main(void){
           int n;
           scanf("%d\n", &n);
           printf("%lld\n", fiboDP(n));
           return 0;
           }


Measured memory_bytes: 2104
#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <functional>
#include <chrono>
#include <cstring>
#include <limits.h>

using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<lint> vl;
typedef pair<lint,lint> pll;

void solve(){

}

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


    int n; cin>>n;
    vl a(n+1);
    for (lint &i: a) cin>>i;

    vl c(n+1, LONG_LONG_MAX);
    c[0] = 1;
    for (int i = 1; i<=n; ++i){
        c[i] = (c[i-1] - a[i-1])*2;
        if (c[i] > LONG_LONG_MAX/4) break;
        if (c[i] <= 0 ) {
            cout<<-1;
            return 0;
        }
    }

    if (a[n]>c[n]){
        cout<<-1;
        return 0;
    }
    vl m(n+1);
    m[n]=a[n];
    for (int i=n-1; i>=0; --i){
        m[i] = m[i+1] + a[i];
        m[i] = min(m[i], c[i]);
    }

    lint ans = 0;
    for (lint i : m) ans += i;
    cout<<ans;



}


Measured memory_bytes: 5560
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define mod 1000000007
#define M 1000000
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll a,b,c;
    cin>>a>>b>>c;
    ll y;
    if(c==b)
     y=floor((b-1)*a/b);
    if(c<b)
     y=floor((c)*a/b);
    if(c>b)
    {
         y=floor((b-1)*a/b);
    }
    cout<<y;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++) a[i]=i+1;
  int ans=1,MOD=1000000007LL;
  for(int i=2;i<1000;i++){
    int tmp=1;
    for(int j=0;j<n;j++){
      while(a[j]%i==0){
	a[j]/=i;
	tmp++;
      }
    }
    (ans*=tmp)%=MOD;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define min(a,b) (((a)>(b))?(b):(a))
#define max(a,b) (((a)>(b))?(a):(b))
#define pb push_back
#define mp make_pair
#define INF (1<<28)-1
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
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; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int main(){
	int n;cin>>n;
	string S;cin>>S;
	int sum[n+10];
	sum[0]=1;
	for(int i=0;i<n;i++){
		sum[i+1]=sum[i]+(S[i]=='W'?1:0);
	}
	int ans=n;
	for(int i=0;i<=n;i++){
		int left=sum[i]-sum[0];
		int right=n-i-(sum[n]-sum[i]);
		ans=min(left+right,ans);
	}
	cout<<ans;
}


Measured memory_bytes: 1796
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX_DIGIT 50
ll dp[100][2];
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main(){
	ll n,k;
	cin>>n>>k;
	ll a[n];
	for(ll i=0;i<n;i++)cin>>a[i];
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0;
	for(int d=0;d<MAX_DIGIT;d++){
		ll mask = 1LL<<(MAX_DIGIT-d-1);

		int num =0;
		for(int i=0;i<n;i++)if(a[i]&mask)num++;

		ll cost0 = mask*num;
		ll cost1 = mask*(n-num);

		if(dp[d][1]!=-1){
			chmax(dp[d+1][1],dp[d][1]+max(cost0,cost1));
		}
		if(dp[d][0]!=-1){
			if(k&mask){
				chmax(dp[d+1][1],dp[d][0]+cost0);
			}
		}
		if(dp[d][0]!=-1){
			if(k&mask)chmax(dp[d+1][0],dp[d][0]+cost1);
			else chmax(dp[d+1][0],dp[d][0]+cost0);
		}
	}
	cout<<max(dp[MAX_DIGIT][0],dp[MAX_DIGIT][1])<<endl;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue> //priority_queue 优先队列
#include <map>
#include <set> //multiset  set<int>::reverse_iterator rit; for(rit=s.rbegin();rit!=s.rend();rit++)
#include <vector>
#include <stack>
#include <cmath>
#include <utility>
#include <sstream>
#include <string>
#define mod 1000000007
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
const db eps=1e-6;
const int INF = 0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=2e5+5;
using namespace std;

int t,n,m,x,y,ans;
ll a[N]={0},b[N]={0};
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
		b[i+1]=2*a[i]-b[i];
	}
	b[0]=b[n]/2;
	printf("%lld",b[0]);
	for(int i=1;i<n;i++){
		b[i]=2*a[i-1]-b[i-1];
		printf(" %lld",b[i]);
	}
	return 0;
}

Measured memory_bytes: 2944