akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define ll long long
#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
double const EPS = 1e-12, PI = acos(-1);
const int N = 1e5 + 9, M = 5e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;
const ll inf = 1e18;

int arr[N];

int main() {
  fastIO;
#ifdef LOCAL
  freopen("input.in", "rt", stdin);
#endif
  ll n;
  cin >> n;
  cout << ((n - 1) * (n) ) / 2;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<deque>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int>pii;
typedef pair<int, pii>pi3;
ll mod = 1000000007;
int m[100][100];
bool flag[100][100];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		char z;
		scanf(" %c", &z);
		if (z == 'Y')
		{
			printf("Four\n");
			return 0;
		}
	}
	printf("Three\n");
	//printf((n % 500 <= a) ? "Yes\n" : "No\n");
}

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

int main() {
  int n;
  cin >>n;
  int a=0;
  int b=0;
  int c=0;
  int ans=0;
  rep(i,n){
    string s;
    cin>>s;
    if(s.at(s.size()-1)=='A'&&s.at(0)=='B'){
      c++;
    }
    else if(s.at(s.size()-1)=='A'){
      a++;
    }
    else if(s.at(0)=='B'){
      b++;
    }
    rep(i,s.size()-1){
      if(s.at(i)=='A'&&s.at(i+1)=='B'){
        ans++;
      }
    }
  }
  if(a>0&&b>0){
    ans+=c;
  }
  else if((a==0&&b!=0)||(a!=0&&b==0)){
    ans+=c;
  }
  else{
    ans+=max(c-1,0);
  }
  int mi=min(a,b);
  mi=min(mi,n-1);
  ans+=mi;
  
  cout<<ans<<endl;  
}



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

o = []
for _ in range(q):
    t, d = input().split()
    o.append((t, d))


def check(x):
    cur = s[x]
    ind = x
    for i in range(q):
        if o[i][0] == cur:
            if o[i][1] == 'L':
                ind -= 1
                if ind < 0:
                    return "LEFT"
                cur = s[ind]
            else:
                ind += 1
                if ind > n-1:
                    return "RIGHT"
                cur = s[ind]
    return "MID"


ans = n

bottom = -1
top = n

while top - bottom > 1:
    mid = (top+bottom)//2
    if check(mid) == "LEFT":
        bottom = mid
    else:
        top = mid

ans -= 1+bottom

bottom = -1
top = n

while top - bottom > 1:
    mid = (top+bottom)//2
    if check(mid) == "RIGHT":
        top = mid
    else:
        bottom = mid

ans -= n-top

print(ans)

Measured memory_bytes: 91596
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

int main(){
  int N;
  cin >> N;
  if(N % 2 == 0) {
    cout << N * (N-2) / 2 << endl;
    for(int i=1; i<=N; i++) {
      for(int j=i+1; j<=N; j++) {
	if(i + j != N + 1)
	  cout << i << ' ' << j << endl;
      }
    }
  } else {
    cout << (N-1) * (N-3) / 2 + (N-1) << endl;
    for(int i=1; i<=N; i++) {
      for(int j=i+1; j<=N; j++) {
	if(i + j != N)
	  cout << i << ' ' << j << endl;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
// AtCoder Regular Contest 077
// C - pushpush

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;


const int MAX_N = 200000;

int N;
int a[MAX_N];

int main() {

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

    for (int i = 0; i < N; i++) {
        if (i <= (N - 1) / 2) {
            cout << a[N - 2 * i - 1] << ' ';
        } else {
            cout << a[2 * i - N] << (i == N - 1 ? '\n' : ' ');
        }
    }
    cout << endl;

    return 0;

}





Measured memory_bytes: 2944
#input
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

sat = 0
old_i = -2
for a in A:
    i = a - 1
    sat += B[i]
    if old_i + 1 == i:
        sat += C[old_i]
    old_i = i

print(sat)

Measured memory_bytes: 3064
N,M = map(int,input().split())

C = []
for i in range(M):
    l = [i]
    x,y = map(int,input().split())
    l.append(x)
    l.append(y)
    C.append(l)

C = list(sorted(C,key= lambda x: x[2]))

counter = [1 for i in range(N)]

for i in range(M):
    C[i][2] = counter[C[i][1]-1]
    counter[C[i][1]-1] += 1

C = list(sorted(C,key= lambda x: x[0]))

for i in range(M):
    for j in range(6-len(str(C[i][1]))):
        print(0,end = "")
    print(C[i][1],end = "")
    for j in range(6-len(str(C[i][2]))):
        print(0,end = "")
    print(C[i][2])


Measured memory_bytes: 29472
package main

import "fmt"

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

	res := 0
	for i := 0; i < n; i++ {
		if h[i] == 0 {
			continue
		}
		res += h[i]
		min := h[i]
		for j := i + 1; j < n; j++ {
			if min > h[j] {
				min = h[j]
			}
			h[j] -= min
		}
	}
	fmt.Println(res)
}


Measured memory_bytes: 512
#pragma GCC optimize ("Ofast") 
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <queue>
#include <string.h>
using namespace std;
struct EDGE
{
	int to;
	long long cap,flow,rev;
};
struct DINIC
{
	static const int maxn=200;
	long long M=1e15;
	int top[maxn],deep[maxn],s,t;
	vector<EDGE> v[maxn];
	bitset<maxn> u;
	void make_edge(int a,int b,long long cap)
	{
		v[a].push_back(EDGE{b,cap,0,v[b].size()});
		v[b].push_back(EDGE{a,0,0,v[a].size()-1});
	}
	long long dfs(int a,long long flow)
	{
		if(a==t||!flow)
			return flow;
		EDGE e;
		long long x;
		while(top[a]<v[a].size())
		{
			e=v[a][top[a]];
			if(deep[e.to]==deep[a]+1&&e.cap!=e.flow)
			{
				x=dfs(e.to,min(flow,e.cap-e.flow));
				if(x)
					return v[a][top[a]].flow+=x,v[e.to][e.rev].flow-=x,x;
			}
			top[a]++;
		}
		deep[a]=-1;
		return 0;
	}
	bool bfs()
	{
		int tmp;
		queue<int> q;
		u.reset(),u[s]=1,q.push(s),memset(deep,0,sizeof(deep));
		while(!q.empty())
		{
			tmp=q.front(),q.pop();
			for(EDGE e:v[tmp])
				if(!u[e.to]&&e.cap!=e.flow)
					u[e.to]=1,deep[e.to]=deep[tmp]+1,q.push(e.to);
		}
		return u[t];
	}
	long long max_flow(int _s,int _t)
	{
		long long flow=0,tflow;
		s=_s,t=_t;
		while(bfs())
		{
			memset(top,0,sizeof(top));
			while(tflow=dfs(s,M))
				flow+=tflow;
		}
		return flow;
	}
	void reset()
	{
		for(int i=0;i<maxn;i++)
			v[i].clear();
	}
}dinic;
int n,tmp,s,t;
long long M=1e15,ans;
int main()
{
	cin>>n,s=n+1,t=n+2;
	for(int i=1;i<=n;i++)
	{
		cin>>tmp;
		if(tmp<=0)
			dinic.make_edge(s,i,-tmp);
		else
			dinic.make_edge(i,t,tmp),ans+=tmp;
		for(int j=i*2;j<=n;j+=i)
			dinic.make_edge(i,j,M);
	}
	cout << ans-dinic.max_flow(s,t)<<'\n';
}

Measured memory_bytes: 256
def d_lazy_faith(A, B, Q, S, T, X):
    from bisect import bisect_right

    # 出発地点の東西いずれかに神社または寺がないという状態を避けるため、
    # 自明に訪ねる意味がないような位置に寺社を建てる
    INF = float('inf')
    s = [-INF] + S + [INF]
    t = [-INF] + T + [INF]

    ans_tmp = []
    for x in X:
        b, d = bisect_right(s, x), bisect_right(t, x)
        res = INF
        # 出発地点xに対し、左右の神社どちらへ行くか？
        # 左右の寺のどちらへ行くか？
        # 寺と神社どちらを先に訪ねるか？
        # 8通りに対し最も距離が短かったものがクエリに対する答え
        for shrine in [s[b - 1], s[b]]:
            for temple in [t[d - 1], t[d]]:
                res = min(res,
                          abs(shrine - x) + abs(temple - shrine),
                          abs(temple - x) + abs(shrine - temple))
        ans_tmp.append(res)
    ans = '\n'.join(map(str, ans_tmp))
    return ans

A, B, Q = [int(i) for i in input().split()]
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]
print(d_lazy_faith(A, B, Q, S, T, X))

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

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

int main(){
    int N;
    cin >> N;
    double sum = 0;
    rep(i, N){
        double a;
        cin >> a;
        sum += 1/a;
    }
    printf("%.6f\n", 1/sum);
    return 0;
}

Measured memory_bytes: 3740
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	int H,W;
	static char a[1002][1002];
	scanf("%d%d",&H,&W);
	rep1(i,H){
		scanf("\n");
		rep1(j,W)scanf("%c",&a[i][j]);
	}
	
	static int d[1002][1002];
	static bool used[1002][1002];
	rep(i,1002)rep(j,1002){
		d[i][j] = INF;
		used[i][j] = true;
	}
	rep1(i,H)rep1(j,W){
		if(a[i][j] == '#')d[i][j] = 0;
		used[i][j] = false;
	}
	
	queue<pair<int,int>> que;
	rep1(i,H)rep1(j,W)if(a[i][j] == '#')que.push(P(i,j));
	while(!que.empty()){
		P p = que.front(); que.pop();
		if(used[p.fr][p.sc])continue;
		used[p.fr][p.sc] = true;
		rep(k,4){
			if(d[p.fr+dir_4[k][0]][p.sc+dir_4[k][1]] == INF){
				d[p.fr+dir_4[k][0]][p.sc+dir_4[k][1]] = d[p.fr][p.sc]+1;
				que.push(P(p.fr+dir_4[k][0],p.sc+dir_4[k][1]));
			}
		}
	}
	
	int ret = 0;
	rep1(i,H)rep1(j,W)ret = max( ret , d[i][j] );
	cout << ret << endl;
}


Measured memory_bytes: 14352
def contest_with_drinks_easy(N: int, T: list, M: int, drinks: list)->list:
    total = sum(T)
    return [total - T[p-1] + m for p, m in drinks]


if __name__ == "__main__":
    N = int(input())
    T = [int(s) for s in input().split()]
    M = int(input())
    drinks = [tuple(int(s) for s in input().split()) for _ in range(M)]
    ans = contest_with_drinks_easy(N, T, M, drinks)
    print('\n'.join(map(str, ans)))


Measured memory_bytes: 3064
using System;

namespace Test
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split();
            var n = int.Parse(inputs[0]);
            var m = int.Parse(inputs[1]);
            var A = new int[n][];
            for (int i = 0; i < A.Length; i++)
            {
                A[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            }
            var B = new int[m][];
            for (int i = 0; i < B.Length; i++)
            {
                B[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            }
            var C = new long[A.Length, B[0].Length];

            for (int y = 0; y < C.GetLength(0); y++)
            {
                for (int x = 0; x < C.GetLength(1); x++)
                {
                    var temp = 0L;
                    for (int i = 0; i < B.Length; i++)
                    {
                        temp += A[y][i] * B[i][x];
                    }
                    C[y, x] = temp;
                }
            }

            for (int y = 0; y < C.GetLength(0); y++)
            {
                for (int x = 0; x < C.GetLength(1); x++)
                {
                    Console.Write("{0}", C[y, x]);
                    if (x == (C.GetLength(1) - 1)) break;
                    Console.Write(" ");
                }
                Console.WriteLine();
            }
        }
    }
}

Measured memory_bytes: 12252
#include <bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,0,v.size()-1)cout << v[i] << " ";cout << endl;
#define arrprint(v,n) rep(i,0,n-1)cout << v[i] << " ";cout << endl;
#define matprint(v,n,m) rep(i,0,n-1){rep(j,0,m-1){cout << v[i][j] << " ";}cout << endl;}
using namespace std;
const int mod=1000000007;
const int INF=1001001001;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int x;
    cin >> x;
    ll ans = 0;
    while(x>=500){
        ans += 1000;
        x -= 500;
    }
    while(x>=5){
        ans += 5;
        x -= 5;
    }

    cout << ans << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 256
import copy


def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

def func(r, c):
    return f[r+1+c+1] * i[r+1] % MOD * i[c+1] % MOD

MOD = 10**9+7
f, i = prepare(2*10**6 + 2, MOD)


r1, c1, r2, c2 = map(int,input().split())

combi = func(r2, c2) - func(r2, c1-1) - func(r1-1, c2) + func(r1-1, c1-1)
print(combi % MOD)   

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n+2);
    a[0] = 0;
    a[n] = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int sum = 0;
    for(int i = 1; i < n+2; i++)
        sum += abs(a[i] - a[i-1]);
    for(int i = 1; i < n+1; i++){
        cout << sum + (abs(a[i+1] - a[i-1]) - (abs(a[i]-a[i-1])+abs(a[i]-a[i+1]))) << endl;
    }
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
   int x,y,a,b,c,d,sr,sg;
   long long int ans=0;
   priority_queue<int> cl,r1,g1;
   priority_queue< int,vector<int>,greater<int> > r,g;
   cin>>x>>y>>a>>b>>c;
   for(int i=0;i<a;i++)
   {
      cin>>d;
      r1.push(d);
   }
   for(int i=1;i<=x;i++)
   {
      r.push(r1.top());
      r1.pop();
   }
   for(int i=0;i<b;i++)
   {
      cin>>d;
      g1.push(d);
   }
   for(int i=1;i<=y;i++)
   {
      g.push(g1.top());
      g1.pop();
   }
   for(int i=0;i<c;i++)
   {
      cin>>d;
      cl.push(d);
   }
   while(!cl.empty())
   {
      if(cl.top()>r.top() && cl.top()>g.top())
      {
         if(r.top()<g.top())
         {
            r.pop();
            r.push(cl.top());
         }
         else
         {
            g.pop();
            g.push(cl.top());
         }
      }
      else if(cl.top()>r.top())
      {
         r.pop();
         r.push(cl.top());
      }
      else if(cl.top()>g.top())
      {
         g.pop();
         g.push(cl.top());
      }
      else
      {
         break;
      }
      cl.pop();
   }
   while(!r.empty())
   {
      ans+=r.top();
      r.pop();
   }
   while(!g.empty())
   {
      ans+=g.top();
      g.pop();
   }
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 2552
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define si(x) ((int)(x).size())
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

#define W first
#define V second

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,lim; cin>>n>>lim;
	pii item[n];
	For(i,0,n-1) cin>>item[i].W>>item[i].V;
	int mem[lim+1];
	fill(mem,mem+lim+1,0);
	For(i,0,n-1)
	{
		for(int j=lim;j>=item[i].W;j--)
		{
			mem[j]=max(mem[j],mem[j-item[i].W]+item[i].V);
		}
	}
	cout<<mem[lim]<<"\n";
	return 0;
}






Measured memory_bytes: 1024
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18

ll mod = 1e9+7;
const ll MAX_N = 3000;
/**/
int main() {
	// 入力
	ll N,K;cin>>N>>K;
    
	// 解法
	ll ans = 0;
	for (ll i = K; i <= N+1; ++i){ // i個選ぶ
		ll min = (0 + (i-1))*i/2;
		ll max = (N + (N-i+1))*i/2;
		ans += max - min + 1;
		ans %= mod;
	}

	//出力
	printf("%lld\n", ans);
}


Measured memory_bytes: 3660
n = input()
def get(n):
	cnt = 0
	while True:
		if not n % 2:
			n /= 2
			cnt += 1
		else:
			break
	return cnt
d = {}
for x in xrange(1, n + 1):
	d[x] = get(x)
max_v = sorted(d.values())[-1]
d = {v: k for k, v in d.iteritems()}
print d[max_v]

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

signed main()
{
  int n;
  string p, s;
  cin >> p >> s;

  p += p;
  n = p.find(s);
  
  if (n < 0){
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }
  
  return (0);
}

Measured memory_bytes: 3176
import java.io.PrintWriter;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		int N = sc.nextInt();
		int[] X = new int[N];
		for(int i=0; i<N; i++)
			X[i] = sc.nextInt();
		int[] X2 = X.clone();
		Arrays.sort(X2);
		
		for(int i=0; i<N; i++) {
			pw.println(X[i]<=X2[N/2-1] ? X2[N/2] : X2[N/2-1]);
		}
				
		sc.close();
		pw.close();
	}
}


Measured memory_bytes: 91848
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

// O(N) STL ?????????
// v[i] <= x <= v[j] ????????? (i<=j)
int stable_partition(vector<int> &v, int l, int r, int x) {
	int i = l - 1;
	for (int j = l; j < r; j++) {
		if (v[j] <= x) {
			i++;
			swap(v[i], v[j]);
		}
	}
	swap(v[i + 1], v[r]);
	return i + 1;
}

signed main() {
	int n; cin >> n;
	vector<int> v(n); rep(i, 0, n) { cin >> v[i]; }
	int b = stable_partition(v, 0, n - 1, v[n - 1]);
	dump(b);
	cout << v[0]; rep(i, 1, v.size()) {
		if (b == i)cout << " [" << v[i] << "]";
		else cout << " " << v[i];
	} cout << endl;
	return 0;
}

Measured memory_bytes: 3120
import java.awt.Event;
import java.awt.geom.Point2D;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.nio.channels.FileChannel;
import java.sql.Timestamp;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;
import java.util.TreeSet;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.IntStream;
 
public class Main {
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args){
		new Main();
	}
	public Main(){
//		new TestA().doIt();
//		new TestB().doIt();
//		new TestC().doIt();
		new TestD().doIt();
	}
	class TestA{
		void doIt() {
			String str = sc.next();
			if(str.equals("AAA") || str.equals("BBB")) {
				System.out.println("No");
			}else {
				System.out.println("Yes");
			}
		}
	}
	class TestB{
		void doIt() {
			long N = Long.parseLong(sc.next());
			long A = Long.parseLong(sc.next());
			long B = Long.parseLong(sc.next());
			long Loop = N / (A + B);
			N = N % (A + B);
			
			long Acount = Loop * A;
			if(N < A)Acount += N;
			else if(N >= A)Acount += A;
			
			System.out.println(Acount);
		}
	}
	class TestC{
		void doIt() {
			int A = Integer.parseInt(sc.next());
			int B = Integer.parseInt(sc.next());
			int num = 0;
			while(true) {
				int numA = (int)(num * 0.08);
				int numB = (int)(num * 0.10);
				if(numA == A && numB == B)break;
				if(numA > A) {
					num = -1;
					break;
				}
				num++;
			}
			System.out.println(num);
		}
	}
	class TestD{
		void doIt() {
			StringBuilder S = new StringBuilder(sc.next());
			StringBuilder Sprev = new StringBuilder();
			StringBuilder Snext = new StringBuilder();
			Integer Q = Integer.parseInt(sc.next());
			Integer R = 0;
			for(Integer i = 0;i < Q;i++) {
				Integer T = Integer.parseInt(sc.next());
				if(T == 1) {
					R += 1;
				}else {
					Integer F = Integer.parseInt(sc.next()) + R;
					if(F % 2 == 1) {
						Sprev = Sprev.insert(0, sc.next());
					}else {
						Snext = Snext.append(sc.next());
					}
				}
			}
			if(R % 2 == 1) {
				Sprev = Sprev.reverse();
				S = S.reverse();
				Snext = Snext.reverse();
				S = Snext.append(S).append(Sprev);
			}else {
				S = Sprev.append(S).append(Snext);
			}
			System.out.println(S.toString());
		}
	}
}

Measured memory_bytes: 86448
N, M = map(int, input().split())
E = [list(map(int, input().split())) for _ in range(N)]
E.sort()

ans = 0

for i in range(N):
  if M - E[i][1] >= 0:
    ans += E[i][0] * E[i][1]
    M -= E[i][1]
  else:
    ans += E[i][0] * M
    break

print(ans)

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

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


Measured memory_bytes: 3076
s=input().replace('BC','D')
a=[]
b=''
for c in s:
    if c=='B' or c=='C':
        a.append(b)
        b=''
    else:
        b+=c
a.append(b)
ans=0
for i in a:
    ac=0
    for j in i:
        if j=='A':
            ac+=1
        else:
            ans+=ac
print(ans)

Measured memory_bytes: 11336
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
#define maxn 51
using namespace std;
const int dx[]={-1,-1,-1,0,0,1,1,1};
const int dy[]={-1,0,1,-1,1,-1,0,1};
int n,m;
char map[maxn][maxn];
inline int work(int x,int y)
{
	int tot=0;
	for(re int i=0;i<8;i++)
	{
		int xx=dx[i]+x;
		int yy=dy[i]+y;
		if(map[xx][yy]=='#') tot++;
	}
	return tot;
}
int main()
{
	cin>>n>>m;
	for(re int i=1;i<=n;i++)
	for(re int j=1;j<=m;j++)
	cin>>map[i][j];
	for(re int i=1;i<=n;i++)
	{
		for(re int j=1;j<=m;j++)
	    {
	    	if(map[i][j]=='#') cout<<"#";
	    	if(map[i][j]=='.') cout<<work(i,j);
		}
		putchar(char(10));
	}
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from sys import stdin
from math import isinf


def generate_adj_table(v_table, _init_adj_table):
    for each in v_table:
        start, end, weight = map(int, each)
        _init_adj_table[start][end] = weight

    return _init_adj_table


def floyd(_adj_table):
    for k in v_range:
        for i in v_range:
            for j in v_range:
                _adj_table[i][j] = min(_adj_table[i][j],
                                       _adj_table[i][k] + _adj_table[k][j])
    return _adj_table


def solve(_after_table):
    negative = False
    for m in v_range:
        if _after_table[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
        return None
    else:
        for each in _after_table:
            print(' '.join(('INF' if isinf(ele) else str(ele) for ele in each)))

    return _after_table


if __name__ == '__main__':
    _input = stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    info_list = map(lambda x: x.split(), _input[1:])
    v_range = range(vertices)

    init_adj_table = tuple([float('inf')] * vertices for _ in v_range)
    for n in v_range:
        init_adj_table[n][n] = 0

    adj_table = generate_adj_table(info_list, init_adj_table)
    after_table = floyd(adj_table)
    solve(after_table)

Measured memory_bytes: 8792
#include <bits/stdc++.h>
using namespace std;
int n;
multiset<int> s1, s3;
int a[100005];
long long f1[100005], f2[100005];
void print(multiset<int> s) {
    multiset<int>::iterator it;
    for(it = s.begin(); it != s.end(); ++it)
        cout << *it << endl;
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int u; cin >> u;
        s1.insert(u);
        f1[0] += u;
    }
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; ++i) {
        int u; cin >> u;
        s3.insert(u);
        f2[n+1] += u;
    }
    for(int i = 1; i <= n; ++i) {
        int u = *s1.begin();
        if (u < a[i]) {
            f1[i] = f1[i-1] + a[i] - u;
            s1.erase(s1.begin());
            s1.insert(a[i]);
        } else f1[i] = f1[i-1];
    }
    //cout << f2[n+1] << endl;
    multiset<int>::iterator it;
    for(int i = n; i >= 1; --i) {
        int u = *s3.rbegin();
        //cout << u << endl;
        if (u > a[i]) {
            f2[i] = f2[i+1] + a[i] - u;
           // cout << f2[i] << endl;
            it = s3.end(); --it;
            //cout << *it << endl;
            s3.erase(it);
            s3.insert(a[i]);
            //print(s3);
        } else f2[i] = f2[i+1];
    }
    //for(int i = 1; i <= n; ++i)
        //cout << f1[i] << " " << f2[i] << endl;
    long long res = -1000000000000000LL;
    for(int i = 1; i <= n; ++i)
        res = max(res, f1[i-1] - f2[i]);
    res = max(res, f1[n] - f2[n+1]);
    cout << res << endl;
}


Measured memory_bytes: 11520
#include <bits/stdc++.h>
#define MOD 998244353

using namespace std;

typedef long long ll;

ll pow_mod(ll x,int k) {
  ll ans=1;
  while (k) {
  	if (k&1) ans=ans*x%MOD;
  	x=x*x%MOD;
  	k>>=1;
  }
  return ans;
}

ll facd[500005],facv[500005];

void pre(int n) {
  facd[0]=1;
  for(int i=1;i<=n;i++) facd[i]=facd[i-1]*i%MOD;
  facv[n]=pow_mod(facd[n],MOD-2);
  for(int i=n-1;i>=0;i--) facv[i]=facv[i+1]*(i+1)%MOD;
}

inline ll C(int n,int m) {
  return (n<m)?0:facd[n]*facv[m]%MOD*facv[n-m]%MOD;
}

int main() {
  int n,m;
  scanf("%d%d",&n,&m);
  pre(max(n,m));
  int ans=0;
  ll s1=pow_mod(n+1,m),s2=pow_mod(m+1,n),inv1=pow_mod(n+1,MOD-2),inv2=pow_mod(m+1,MOD-2);
  for(int i=0;i<=min(n,m);i++) {
    ans=(ans+C(n,i)*C(m,i)%MOD*facd[i]%MOD*((i&1)?MOD-1:1)%MOD*s1%MOD*s2)%MOD;
    s1=s1*inv1%MOD;
    s2=s2*inv2%MOD;
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long u_ll;
typedef pair<int, int> pair_;
 
const int INF = 1001001001;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

 
int gcd(int a, int b){
    if(b == 0) return a;
 
    return gcd(b, a%b);
}
 
int main(){

   int n,k;
   cin >> n >> k;

   int r, s, p;
   cin >> r >> s >> p;

   string t;
   cin >> t;
   int cnt = n/k;
   int ans=0;
   vector<int> ren(k,1);

   rep(i, cnt+1){
       rep(j,k){
           if(i*k+j == n) {
                break;
           }
           else if(i==0) {
                if(t[i*k+j]=='r') ans+=p;
                else if(t[i*k+j]=='s') ans+=r;
                else if(t[i*k+j]=='p') ans+=s;
               // cout << ans << endl;
               continue;
           }

           if(t[i*k+j]==t[(i-1)*k+j]){
               ren[j]++;
               if(t[i*k+j]=='r') ans+=p*(ren[j]%2);
               else if(t[i*k+j]=='s') ans+=r*(ren[j]%2);
               else if(t[i*k+j]=='p') ans+=s*(ren[j]%2);
           }
           else if((t[i*k+j]!=t[(i-1)*k+j])&&(ren[j]!=1)){
                ren[j]=1;
                if(t[i*k+j]=='r') ans+=p*(ren[j]%2);
                else if(t[i*k+j]=='s') ans+=r*(ren[j]%2);
                else if(t[i*k+j]=='p') ans+=s*(ren[j]%2);
           }
           else if((t[i*k+j]!=t[(i-1)*k+j])&&(ren[j]==1)){
                if(t[i*k+j]=='r') ans+=p*(ren[j]%2);
                else if(t[i*k+j]=='s') ans+=r*(ren[j]%2);
                else if(t[i*k+j]=='p') ans+=s*(ren[j]%2);
                ren[j]=1;
           }
       }
   }

   cout << ans;

    return 0;
}

Measured memory_bytes: 768
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N;
	string s[10001];
	int naibu=0;
	int A=0,B=0,BA=0;
	scan(N);
	rep(i,N){
		scan(s[i]);
		rep(j,s[i].size()-1){
			if(s[i][j]=='A'&&s[i][j+1]=='B') naibu++;
		}
		if(s[i][0]!='B'&&s[i].back()=='A') A++;
		else if(s[i][0]=='B'&&s[i].back()!='A') B++;
		else if(s[i][0]=='B'&&s[i].back()=='A') BA++;
	}
	if(A+B==0&&BA>0) prin(naibu+min(A,B)+BA-1);
	else prin(naibu+min(A,B)+BA);
	return 0;
}


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



int main(void) {
    int K, N;
    int A[200010];

    cin >> K >> N;
    for (int i=0; i < N; i++) {
        cin >> A[i];
    }
    int max = K - A[N - 1] + A[0];

    for (int i=0; i < N-1; i++) {
        int len = A[i+1] - A[i];
        if (len > max) max = len;
    }


    cout << K - max << endl;

    return 0;
}

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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 2e3 + 2;

string S;
vector<int> G[N];
int D[N], C[N], U[N];

void DFS(int v, int p = -1) {
	C[v] = (S[v] - '0');
	for (int u : G[v]) if (u != p) DFS(u, v), C[v] += C[u], U[v] += U[u] + C[u];
	D[v] = U[v] & 1;
	for (int u : G[v]) if (u != p) D[v] = max(D[v], D[u] + C[u] - (U[v] - (U[u] + C[u])));
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	int n; cin >> n >> S;
	for (int i = 1; i < n; i++) {
		int v, u; cin >> v >> u; v--, u--;
		G[v].push_back(u), G[u].push_back(v);
	}
	int ans = INF;
	for (int r = 0; r < n; r++) {
		for (int i = 0; i < n; i++) D[i] = C[i] = U[i] = 0;
		DFS(r);
		ans = min(ans, (D[r] ? INF : (U[r] >> 1)));
	}
	cout << (ans == INF ? -1 : ans) << endl;

	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
 	char s[10];
 	char a[10]="Sunny";
 	char b[10]="Cloudy";
	 cin>>s;
	 
	if(strcmp(a,s)==0){
	 cout<<"Cloudy";
	 return 0;
 	}
	 
	 if(strcmp(b,s)==0){
	 cout<<"Rainy";
	 return 0;
 	}
	  cout<<"Sunny";
	 return 0;

}

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

int main(void){
  int n, m;
  cin >> n >> m;
  if(n == m) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

int main() {
	int N; cin >> N;
	vector<int> a(N), b(N), c(N);
	for (int i = 0; i < N; i++)cin >> a[i] >> b[i] >> c[i];

	vector<vector<int>> dp(N, vector<int>(3));
	dp[0][0] = a[0];
	dp[0][1] = b[0];
	dp[0][2] = c[0];
	for (int i = 1; i < N; i++) {
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i];
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c[i];
	}

	int ans = max(dp[N - 1][0], max(dp[N - 1][1], dp[N - 1][2]));
	cout << ans << endl;
}

Measured memory_bytes: 6912
package main

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

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	isBroken := make(map[int]bool, 0)
	for i := 0; i < m; i++ {
		sc.Scan()
		t, _ := strconv.Atoi(sc.Text())
		isBroken[t] = true
	}
	dp := make([]int, n+1) // DP変数定義
	dp[0] = 1              // DP初期条件(0段目-何もしない事の1通り)
	if !isBroken[1] {
		dp[1] = 1 // 壊れていなければ1通り
	}
	for i := 2; i < n+1; i++ { // 2段目から開始する
		if !isBroken[i-2] {
			dp[i] += dp[i-2]
		}
		if !isBroken[i-1] {
			dp[i] += dp[i-1]
		}
		dp[i] %= 1000000007
	}
	fmt.Println(dp[n])
}


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

signed main(void) {
    int N;
    cin >> N;

    // (i-1)%iが最も大きいあまりが出る
    // 1からi-1までの総和を求めれば良い
    int ans = (N*N - N) / 2;

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <bitset>
#include <map>

using namespace std;

int main(){

    int N ,count = 0;
    cin >> N;

    for (int i = 1; i <= N; i++){
        int p;
        cin >> p;
        if (p != i) count++;
    }

    if (count == 0 || count == 2){
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



i64 n, m;
void solve(){
	cin >> n >> m;
	
	cout << abs((n-2)*(m-2)) << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

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

char a[200200];
string s;
stack <char> st, _st;


int main(){
	scanf("%s", a);
	s = a;

	for(int i=0; i<s.size(); i++){
		if(st.empty()) st.push(s[i]);
		else{
			if(st.top() == 'S' && s[i] == 'T'){
				_st.push(s[i]);
				st.pop();
			}
			else{
				st.push(s[i]);
			}
		}
	}

	printf("%d\n", st.size());
	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <iomanip>
using namespace std;

typedef long long ll;


int main() {
	int n; cin >> n;
	vector<int> a(n + 2), b(n + 2);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	bool avail[52] = {};
	for (int i = 1; i <= 50; i++) avail[i] = true;
	deque<int> que;
	for (int t = 51; t > 0; t--) {
		avail[t] = false;
		bool flag = true;
		for (int i = 0; i < n; i++) {
			bool used[52] = {}, f = false;
			que.push_back(a[i]);
			while (!que.empty()) {
				int pos = que.front(); que.pop_front();
				if (pos == b[i]) {
					f = true;
					continue;
				}
				if (used[pos]) continue;
				used[pos] = true;
				for (int j = 1; j <= 50; j++) {
					if (!avail[j]) continue;
					que.push_back(pos%j);
				}
			}
			flag &= f;
		}
		if (!flag) avail[t] = true;
	}
	if (avail[51]) {
		cout << -1 << endl;
		return 0;
	}
	ll ans = 0;
	for (int i = 1; i <= 50; i++) {
		if (!avail[i]) continue;
		ans += 1LL << (ll)i;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
#define N 100005
#define inf 0x3f3f3f3f
using namespace std;
ll sum,a[N],t,tmp,n;
int main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
		t+=i;
	}

	if(sum%t)cout<<"NO";
	else{
		tmp=a[1];
		for(int i=1;i<n;i++)a[i]=a[i+1]-a[i];
		a[n]=tmp-a[n];
		ll d=sum/t,ok=1,ans=0;
		for(int i=1;i<=n&&ok;i++){
			a[i]-=d;
			if(a[i]%n||a[i]>0)ok=0;
			ans+=a[i]/n;
		}
		if(ok&&ans==-d)cout<<"YES";
		else cout<<"NO";
	}
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll MOD=1000000007;
const ll MODA=998244353;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
long long gcd(long long a,long long b){
    ll gcdmax=max(a,b);
    ll gcdmin=min(a,b);
    while(true){
        if(gcdmax%gcdmin==0)break;
        else gcdmax%=gcdmin;
        swap(gcdmin,gcdmax);
    }
    return gcdmin;
}
ll powerup(ll N,ll P,ll M){
    if(P==0)return 1;
    else if(P%2==0){
        ll t=powerup(N,P/2,M);
        return t*t%M;
    }
    else return N*powerup(N,P-1,M)%M;
}
vector<ll> find_divisor(ll N){
  ll k=1;
  while(k*k<=N){
    k++;
  }
  vector<ll> A(1);
  rep(i,k){
    if(i==1)A.at(0)=1;
    else if(i>=2){
      if(N%i==0)A.push_back(i);
    }
  }
  ll t=0;
  t=A.size();
  rep(i,t){
    if(A.at(t-i-1)*A.at(t-i-1)!=N)A.push_back(N/A.at(t-1-i));
  }
  return A;
}
vector<ll> fac;
vector<ll> finv;
vector<ll> inv;
void COMinit(ll N,ll P){
    rep(i,N+1){
        if(i==0){
            fac.push_back(1);
            finv.push_back(1);
            inv.push_back(1);
        }
        else if(i==1){
            fac.push_back(1);
            finv.push_back(1);
            inv.push_back(1);
        }
        else{
            fac.push_back(fac.at(i-1)*i%P);
            inv.push_back(P-inv.at(P%i)*(P/i)%P);
            finv.push_back(finv.at(i-1)*inv.at(i)%P);
        }
    }
}

ll COM(ll n,ll k,ll P){
    if(n<k)return 0;
    if(n<0||k<0)return 0;
    return fac.at(n)*(finv.at(k)*finv.at(n-k)%P)%P;
}
int main()
{
  ll A,B,C,D,E;
  cin>>A>>B>>C>>D>>E;
  cout<<15-A-B-C-D-E<<endl;
}

Measured memory_bytes: 3600
import java.util.*;
import java.util.stream.Collectors;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int a[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sc.next());
        }
        sc.close();
        Map<Integer, Integer> h = new TreeMap<>(Comparator.reverseOrder());
        for (int i = 0; i < n; i++) {
            if (h.containsKey(a[i])) {
                h.put(a[i], h.get(a[i]) + 1);
            } else {
                h.put(a[i], 1);
            }
        }
        List<Integer> s = h.entrySet().stream().filter(x -> x.getValue() >= 4).map(x -> x.getKey())
                .collect(Collectors.toList());
        List<Integer> t = h.entrySet().stream().filter(x -> x.getValue() >= 2).map(x -> x.getKey())
                .collect(Collectors.toList());
        long ans = 0;
        if (s.size() > 0) {
            ans = (long) s.get(0) * s.get(0);
        }
        if (t.size() > 1) {
            ans = Math.max(ans, (long) t.get(0) * t.get(1));
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 48532
// AOJ 2494 Sliding GCD
// 2018.3.18 bal4u

#include <stdio.h>

#define MAX   100000
#define DMAX     130	// max 126

int t[MAX+1][DMAX+1], w[MAX+1];
int c[MAX+1];

void divisor_tble(int N)
{
	int i, k, n = (N>>1)+1;
	for (i = 2; i <= n; i++) {
		for (k = i<<1; k <= N; k += i) t[k][w[k]++] = i;
	}
}

int main()
{
	int  N, W, nw;
	int i, k, lo, hi, ans;

	scanf("%d%d", &N, &W), nw = N-W+1;
	if (W == 1) {
		putchar('1');
		for (k = 2; k <= nw; k++) putchar(' '), putchar('1');
		putchar('\n');
		return 0;
	}

	divisor_tble(N);

	printf("%d", W);
	ans = 1;
	for (k = 1; k <= W; k++) {
		c[k] += 2; ans++;
		for (i = 0; i < w[k]; i++) if (++c[t[k][i]] == 2) ans++;
	}

	lo = 1, hi = W;
	for (k = 2; k <= nw; k++) {
		for (i = 0; i < w[lo]; i++) if (--c[t[lo][i]] == 1) ans--;
		c[lo] -= 2; if (c[lo] < 2) ans--;
		lo++, hi++;
		c[hi] += 2; if (c[hi] == 2) ans++;
		for (i = 0; i < w[hi]; i++) if (++c[t[hi][i]] == 2) ans++;
		printf(" %d", ans);
	}
	putchar('\n');
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
 map<int, int64_t> p;
  for (int x : A) {
    if (p.count(x)) {
      // 既に含まれているならインクリメント
      p.at(x)++;
    } else {
      // 含まれていないなら、1を追加
      p[x] = 1;
    }
  }
  
  int64_t Z=0;
   for(auto l:p){
     int64_t i=l.second;
     Z+=i*(i-1)/2;
   }
  for (int i = 0; i < N; i++){
    cout<<Z-p.at(A.at(i))+1<<endl;

  }
}  

Measured memory_bytes: 10240
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<P,P> PP;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-10;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

struct UnionFindTree {
    vector<int> par;
    vector<int> rank;
    vector<int> siz;

    void init(int n) {
        par.resize(n);
        rank.resize(n);
        siz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
        }
    }
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) rank[x]++;
        par[y] = x;
        siz[x] += siz[y];
    }
    bool is_same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        x = find(x);
        return siz[x];
    }
};

ll n, m;
P a[MAX_N];
UnionFindTree g;
map<int, int> deg;
bool used[MAX_N]{};
vector<ll> v;

int main() {
    cin >> n >> m;
    REP(i,n){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a,a+n);
    g.init(n);
    REP(i,m){
        int x, y;
        cin >> x >> y;
        g.unite(x,y);
    }
    int dsum = 0;
    REP(i,n){
        if(deg.count(g.find(i))==0){
            deg[g.find(i)] = g.size(i);  // 連結成分を1つの頂点とみなす。次数の制限は含む頂点数となる。
            dsum += g.size(i);
        }
    }
    if((deg.size()-1)*2 > dsum){ // 次数は辺の2倍必要
        cout << "Impossible" << endl;
    }
    else if(deg.size()==1){
        cout << 0 << endl;
    }
    else{
        ll ans = 0;
        REP(i,n){
            int x = g.find(a[i].second);
            if(!used[x]){  // 1頂点につき最低1次数は使う
                used[x] = true;
                ans += a[i].first;
                deg[x]--;
            }
            else if(deg[x]>0){
                v.push_back(a[i].first);
                deg[x]--;
            }
        }
        REP(i,int(deg.size()-2)){
            ans += v[i];
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 6912
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

/* INCLUDES */
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <random>
#include <utility>
#include <limits>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
using namespace std;

/* TYPES */
#define long long long
#define all(v) v.begin(), v.end()
typedef pair<int,int> pii;
typedef pair<int64_t,int> pli;
typedef pair<int64_t,int64_t> pll;
typedef vector<int> vi;
typedef vector<pair<int,int> > vpi;
typedef vector<string> vs;
typedef vector<vector<int> > vvi;
typedef vector<vector<int64_t> > vvl;

/* CONSTANTS */
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

/* FUNCTIONS */
template<typename T, typename U> inline void setMin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void setMax(T &x, U y) { if(x < y) x = y; }
template<typename T>
inline T gcd(T a, T b) {
    T c;
    while(b) c = b, b = a % b, a = c;
    return a;
}
template<typename T>
inline T square(T a, T b) { return a*b; }

const int N = 2e5+1;

class TaskE {

    long n, k, a[N], f[N];

public:
    void solve(istream &cin, ostream &cout) {
        cin >> n >> k;
        for(int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
        for(int i = 0; i < n; i++) cin >> f[i];

        long l = 0, r = 1e12;
        while(l < r) {
            long mid = l+r >> 1;
            vector<long> b;
            for(int i = 0; i < n; i++) {
                b.push_back(mid / f[i]);
            }
            sort(b.begin(), b.end());
            long req = 0;
            for(int i = 0; i < n; i++) {
                req += max(a[i] - b[i], 0ll);
            }
            if(req > k) l = mid + 1;
            else r = mid;
        }

        cout << l << endl;
    }
};

class Solver {
public:
    void solve(std::istream& in, std::ostream& out) {
        TaskE *obj = new TaskE();
        obj->solve(in, out);
        delete obj;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solver solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

Measured memory_bytes: 8708
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
using P=pair<int,int>;
typedef unsigned long long ull;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll MOD=1e9+7;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  int n;
  cin >> n;
  vector<int>a(n);
  rep(i,n) cin >> a[i];
  int ans=0;
  rep(i,n){
    if(a[a[i]-1]==i+1)ans++;
  }
  cout << ans/2 << endl;
}


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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    lint n;cin >> n;
    vector<int> v1, v2;
    REP(i,n){
        int a;
        cin >> a;
        if(i%2==0){
            v1.emplace_back(a);
        }else{
            v2.emplace_back(a);
        }
    }
    if(n%2==0){
        IREP(i,SZ(v2)){
            cout << v2[i] << " ";
        }
        REP(i, SZ(v1))
        {
            cout << v1[i] << " ";
        }
    }else{
        IREP(i, SZ(v1))
        {
            cout << v1[i] << " ";
        }
        REP(i, SZ(v2))
        {
            cout << v2[i] << " ";
        }
    }
    return 0;
}

Measured memory_bytes: 3188