akhauriyash/Code-Regression huggingface dataset:
n, m=map(int, input().split())
es0=[]
es=[[] for i in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    es0.append((a-1,b-1))
    es[a-1].append(b-1)
    es[b-1].append(a-1)

from collections import deque

def bfs(s, es):
    visited=[0]*n
    visited[s]=1
    q=deque([s])
    while q:
        p=q.pop()
        for r in es[p]:
            if visited[r]==0:
                q.append(r)
                visited[r]=1
    if 0 in visited:
        return False
    else: return True

from copy import deepcopy
ans=0
for e in es0:
    newes=deepcopy(es)
    newes[e[0]].remove(e[1])
    newes[e[1]].remove(e[0])
    if bfs(0,newes):
        continue
    else:
        ans+=1
print(ans)



Measured memory_bytes: 47580
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
const int N=2e5+10;
int a[N],n;
int main()
{
    n=read();
    ll ans=0;
    rep(i,1,n) a[i]=read();

    sort(a+1,a+1+n);

    int m=n-1,now=1,id=n;
    for(int i=1;i<=m;++i)
    {
        //printf("i:%d id:%d now:%d\n",i,id,now);

        if(now<2) ans+=a[id],now++;
        else{
            now=1,--id;
            ans+=a[id];
        }
    }
    printf("%lld\n",ans);

}


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

using namespace std;
using ll = long long;
const int MAXN = 20;
const int inf = 1.01e7;
string s[MAXN];
int dist[MAXN][MAXN];
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
int n, m;

int bfs(int i, int j) {
  queue<pair<int, int>> q;
  q.emplace(i, j);
  memset(dist, inf, sizeof dist);
  dist[i][j] = 0;
  int mx = 0;
  while(!q.empty()) {
    auto t = q.front();
    q.pop();
    mx = max(mx, dist[t.first][t.second]);
    for(int e = 0; e < 4; ++e) {
      int x = t.first + dx[e], y = t.second + dy[e];
      if(x < 0 || x >= n || y < 0 || y >= m || s[x][y] == '#') continue;
      if(dist[x][y] <= dist[t.first][t.second] + 1) continue;
      dist[x][y] = dist[t.first][t.second] + 1;
      q.emplace(x, y);
    }
  }
  return mx;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for(int i = 0; i < n; ++i) {
    s[i].clear();
    cin >> s[i];
  }
  int res = 0;
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < m; ++j) {
      if(s[i][j] == '.') res = max(res, bfs(i, j)); 
    }
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 256
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var myOut = main();
if(myOut !== undefined)console.log(myOut);

function main(){
  var n = next(), m = next();
  var a = nexts(n);
  var b = xArray(0,m*2+3);
  var sum = 0;
  for(var i = 1; i < n; i++){
    var c = a[i-1], d = a[i];
    if(d < c)d += m;
    var x = d-c;
    b[c+2]--, b[d+1] += x, b[d+2] -= x-1;
    sum += x;
  }
  var tot = 0;
  for(var i = 2; i < m*2+1; i++){
    tot += b[i];
    b[i] = b[i-1] + tot;
  }
  var ans = sum;
  for(var i = 1; i <= m; i++){
    var t = sum + b[i] + b[i+m];
    if(t < ans)ans = t;
  }
  return ans;
}

Measured memory_bytes: 31048
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n ;
    cin >> n;
    while(n!=0){
      vector<int>a(n);
      vector<int>S(n+1);
      S.at(0) = 0;
      for(int i = 0;i < n;i++){
        cin >> a.at(i);
      }
      for(int i = 0;i < n;i++){
         S.at(i+1) = S.at(i) + a.at(i);
      }
      int ans = -99999999990990999;
      for(int k = 0; k < n;k++){
      for(int i = 0; i < n-k  ;i++){
        if(S.at(n-k) - S.at(i) > ans){
          ans = S.at(n-k) - S.at(i);
      }
    }
  }
          cout << ans << endl;
          cin >> n;
        }
}


Measured memory_bytes: 3068
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


string line;

struct Info{
	Info(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	int row,col;
};

char buf1[101],buf2[101],buf3[101];
bool table1[201][201],table2[201][201];
int len_1,len_2,start_row = 100,start_col = 100,G[128];
int diff_row[6] = {1,1,0,-1,-1,0},diff_col[6] = {0,-1,-1,0,1,1};
int loc[6][6] = {{0,1,2,3,4,5},{1,2,3,4,5,0},{2,3,4,5,0,1},{3,4,5,0,1,2},{4,5,0,1,2,3},{5,0,1,2,3,4}};
vector<Info> V;

void func(){

	getchar();
	getline(cin,line);
	for(len_1 = 0; len_1 != line.length(); len_1++){
		buf1[len_1] = line[len_1];
	}
	buf1[len_1] = '\0';

	getline(cin,line);
	for(len_2 = 0; len_2 != line.length(); len_2++){
		buf2[len_2] = line[len_2];
	}
	buf2[len_2] = '\0';
	scanf("%s",buf3);

	for(len_1 = 0; buf1[len_1] != '\0'; len_1++);
	for(len_2 = 0; buf2[len_2] != '\0'; len_2++);

	if(len_1 != len_2){
		printf("false\n");
		return;
	}else if(len_1 == 0 && len_2 == 0){
		printf("true\n");
		return;
	}

	for(int row = 0; row <= 200; row++){
		for(int col = 0; col <= 200; col++){
			table1[row][col] = false;
			table2[row][col] = false;
		}
	}

	V.clear();

	int tmp_row = start_row,tmp_col = start_col,tmp;
	table1[start_row][start_col] = true;
	V.push_back(Info(start_row,start_col));

	for(int i = 0; i < len_1; i++){
		tmp = G[buf1[i]];
		tmp_row += diff_row[tmp];
		tmp_col += diff_col[tmp];
		table1[tmp_row][tmp_col] = true;
		V.push_back(Info(tmp_row,tmp_col));
	}

	bool FLG;
	vector<Info> X;

	for(int loop = 0; loop < V.size();  loop++){

		for(int k = 0; k < 6; k++){

			for(int i = 0; i < X.size(); i++){
				table2[X[i].row][X[i].col] = false;
			}
			X.clear();

			tmp_row = V[loop].row;
			tmp_col = V[loop].col;
			table2[tmp_row][tmp_col] = true;
			X.push_back(Info(tmp_row,tmp_col));

			FLG = true;
			for(int i = 0; i < len_2; i++){

				tmp = loc[k][G[buf2[i]]];
				tmp_row += diff_row[tmp];
				tmp_col += diff_col[tmp];
				if(table1[tmp_row][tmp_col] == false){
					FLG = false;
					break;
				}
				table2[tmp_row][tmp_col] = true;
				X.push_back(Info(tmp_row,tmp_col));
			}
			if(!FLG)continue;

			for(int i = 0; i < V.size(); i++){
				if(table2[V[i].row][V[i].col] == false){
					FLG = false;
					break;
				}
			}
			if(FLG){
				printf("true\n");
				return;
			}
		}
	}
	printf("false\n");
}


int main(){

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

	G['a'] = 0;
	G['b'] = 1;
	G['c'] = 2;
	G['d'] = 3;
	G['e'] = 4;
	G['f'] = 5;

	for(int i = 0; i < case_num; i++)func();

	return 0;
}

Measured memory_bytes: 3324
import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
	public static void main(String[] args) { 
		/*If person x has a situation where all piles have even size, they LOSE
		 * Whatever piles they touch, the opposing player can mirror to always win
		 * Therefore, if >= 1 odd pile exists, person 1 can make all those odds into evens
		 * to make person 2 LOSE
		 * Otherwise, if all piles are even to begin with, person 2 can mirror and eventually WIN
		 **/
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		int N = I.nextInt();
		int odd = 0;
		for (int i = 0; i < N; i++) odd+=I.nextInt()%2;
		O.pln(odd>=1?"first":"second");
	}
	public static double max(double a, double b) {return Math.max(a, b);}
	public static double min(double a, double b) {return Math.min(a, b);}
	public static long min(long a, long b) {return Math.min(a,b);}
	public static long max(long a, long b) {return Math.max(a,b);}
	public static int min(int a, int b) {return Math.min(a,b);}
	public static int max(int a, int b) {return Math.max(a,b);}
	public static long abs(long x) {return Math.abs(x);}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return max(a,b);
		return GCD(min(a,b),max(a,b)%min(a,b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	public static int pop(long x) { //Returns number of bits within a number
		int cnt = 0;
		while (x>0) {
			if (x%2==1) cnt++;
			x/=2;
		}
		return cnt;
	}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());};
		double nextDouble() {return Double.parseDouble(next());}
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(double x) {w.println(x);w.flush();}
		void pln(boolean x) {w.println(x);w.flush();}
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void pln(BigInteger x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
		void p(BigInteger x) {w.print(x);w.flush();}
		void p(double x) {w.print(x);w.flush();}
		void p(boolean x) {w.print(x);w.flush();}
	}
}


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

using namespace std;


void solve() {
    int n,k,s;
    cin >> n >> k >> s;
    int x = s;
    int y = s == 1000*1000*1000 ? s-1 : s+1;
    for (int i = 0; i < k; i++) {
        cout << x << ' ';
    }
    for (int i = k; i < n; i++) {
        cout << y << ' ';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<string>
#include<bitset>
#include<cfloat>
#include<iomanip>
#include<numeric>

//#define int long long
#define repi(i,start,end) for(int (i)=(start),TemPNuM=(int)(end);(i)<TemPNuM;++(i))
#define rep(i,end) repi((i),0,(end))
#define rfor(x,v) for(auto& (x) : (v))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fsort(v,lambda) sort(all((v)),(lambda))
#define vin(v) rep(i,(v).size())cin >> (v)[i];
#define vpin(v) rep(i,(v).size())cin>>v[i].first>>v[i].second

using namespace std;
using ll =  long long;
using pint =  pair<int,int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vpint = vector<pint>;

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; }
template<class T>void put_double(T a){if(cout.precision()!=12)cout<<setprecision(12);cout<<a<<endl;}
template<class T>void print(T a){cout << a << endl;}
//lambda: [](int x, int y){return x<y;}

signed main(void) {
    int n; cin >> n;
    vint a(n); vin(a);
    int ans = a[0];
    rep(i, n - 1) {
        ans = __gcd(ans, a[i + 1]);
    }
    print(ans);

    return 0;
}


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

using namespace std;

int main() {
	double r,f,g;
	cin >> r;

	f = acos(-1) * r*r;
	g = (r * 2)*acos(-1);

	cout << fixed <<  setprecision(6) << f  <<  " " << g << endl;

		
}



Measured memory_bytes: 3284
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
	/**
	 * Increment Decrement
	 * @param 1 ≦ N ≦ 100
	 * @param |S| = N
	 * @result max x
	 */
	public static void main(String... args) {
		try (Scanner sc = new Scanner(System.in)) {
			int n = sc.nextInt();
			String s = sc.next();
			List<String> list = Arrays.asList(s.split(""));

			int x = 0;
			int ans = 0;
			for (String t : list) {
				if (t.equals("I")) {
					x ++;
					if (x > ans) {
						ans = x;
					}
				} else {
					x --;
				}
			}
			System.out.println(ans);
		}
	}
}


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

using namespace std;

using ll = long long;

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

    int n;
    cin >> n;

    vector<int> d(n);
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    sort(d.begin(), d.end(), greater<int>());

    int num = 1, bf = d[0];
    for (int i = 1; i < n; ++i) {
        if (bf > d[i]) {
            ++num;
            bf = d[i];
        }
    }

    cout << num << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int card[4][13] = {{},{}};
	int i,j,a,b,n; //0:S 1:H 2:C 3:D
	scanf("%d",&n);
	for(i=0;i<n*2;i++){
		scanf("%c %d",&a,&b);
		if(a=='S') card[0][b-1] = 1;
		if(a=='H') card[1][b-1] = 1;
		if(a=='C') card[2][b-1] = 1;
		if(a=='D') card[3][b-1] = 1;
	}
	for(i=0;i<4;i++){
		for(j=0;j<13;j++){
			if(card[i][j]!=1){
				if(i==0) printf("S %d\n",j+1);
				if(i==1) printf("H %d\n",j+1);
				if(i==2) printf("C %d\n",j+1);
				if(i==3) printf("D %d\n",j+1);
			}
		}
	}
return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
#define inf 998244353
#define LINF 1000000000000000007LL
#define ll long long
using namespace std;
signed main(){
	int x,k;
	vector<int> r;
	cin>>x>>k;
	vector< pair<int,int> > ev;
	for(int i=0;i<k;i++){
		int tmp;
		cin>>tmp;
		r.pb(tmp);
		ev.pb( mp ( tmp, -1 ) );
	}
	int q; cin>>q;
	for(int i=0;i<q;i++){
		int tim, a;
		cin>>tim>>a;
		ev.pb( mp( tim, a ) );
	}
	sort(ev.begin(),ev.end());
	vector<int> ans;
	int dir = -1, con = 0, ct = 0, btm = 0, tp = x;
	for(int i=0;i<ev.size();i++){
		int et = ev[i].first - ct;
		con += dir * et;
		btm = min( max( btm, -con ), x-con);
		tp = min( max( tp, -con ), x-con);
		if( ev[i].second == -1){
			dir *= -1;
		}
		else{
			int a = ev[i].second;
			a = min( max( btm, a ), tp );
			ans.pb( a + con );
		}
		ct = ev[i].first;
	}
	for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<endl;
	}
}

Measured memory_bytes: 7780
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<char>> a(n, vector<char>(n));
    vector<vector<char>> b(m, vector<char>(m));
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> b[i][j];
        }
    }

    for(int i = 0; i <= n - m; i++)
    {
        for(int j = 0; j <= n - m; j++)
        {
            int count = 0;
            for(int b1 = 0; b1 < m; b1++)
            {
                for(int b2 = 0; b2 < m; b2++)
                {
                    if(b[b1][b2] == a[i+b1][j+b2])
                    {
                        count++;
                    }
                }
            }
            if(count == m * m)
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}




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

int main(int argc, char *argv[]) {
  int ans = 0;
  char s[10];
  scanf("%s", s);
  ans = (s[0] == '1') + (s[1] == '1') + (s[2] == '1');
  printf("%d\n", ans);
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
ll N;
//区間ごとにanが何回採用されるかを求めると良い
int main(){
 
    ll N;
    cin >> N;
 
    //vector<ll > A(N, 0);
    vector<ll > idx(N+2, 0);
 
    for(ll i = 1; i <= N; i++){
        ll t; cin >> t;
        //各要素の位置を記録
        idx[t] = i;
    }
 
    ll ans = 0;
 
    //番兵：2つ先，2つ前を見るので複数入れとかないと飛び越してしまう
    //set<ll > usedIdx = {0, N+1};
    multiset<ll > usedIdx;
    usedIdx.insert(0);
    usedIdx.insert(0);
    usedIdx.insert(N+1);
    usedIdx.insert(N+1);
    //自分自身の要素が採用される区間はいくつか？を求める．
    
    //大きい順に挿入された位置を見て自分より右or左に自分より大きい数字があるかを調べる
    for(ll i = N; i >= 1; i--){
        auto it = usedIdx.lower_bound(idx[i]);
        //自分より右側で自分より大きい
        ll R  = *it;
        it++;
        //さらに右側
        ll RR = *it;
        it--; it--;
        //自分より左側で自分より大きい
        ll L  = *it;
        it--;
        ll LL = *it;

        //cout << *left_idx << " " << *right_idx << endl;
        //位置を追加
        usedIdx.insert(idx[i]);
        // //答え更新
        // ans += ((idx[i] - *left_idx) * (*right_idx - idx[i])) * i;

        //左側の自分より大きい数基準での組み合わせ
        ans += i * (R - idx[i]) * (L - LL);
        //右側の自分より大きい数基準での組み合わせ
        ans += i * (idx[i] - L) * (RR - R);
    }
 
    cout << ans << endl;
 
} 

Measured memory_bytes: 5760
// Starting with the name of Allah

#include <bits/stdc++.h>
#define ll long long
#define nl endl
#define Nayon ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define gcd(a,b)         __gcd(a,b)
#define lcm(a,b)         (a/gcd(a,b))*b
#define v_sum(a)         accumulate(a.begin(),a.end(),0)
#define v_max(a)         *max_element(a.begin(),a.end())
#define v_min(a)         *min_element(a.begin(),a.end())
#define v_uni(a)         a.erase(unique(a.begin(),a.end()),a.end())
# define pi           3.14159265358979323846

using namespace std;




int main()
{
	Nayon;
	int i,j,x=0,cnt=0;
	string s;
	cin>>s;
	for(i=0;i<s.size();i++){
		for(j=i;j<s.size();j++){
			if(s[j]=='R'){
				cnt++;
			}
			else{
				break;
			}
		}
		if(cnt>x){
			x=cnt;
		}
		cnt=0;
	}
	cout<<x<<nl;
}


Measured memory_bytes: 3536
#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <string>
#include <algorithm>
#include <cmath>

typedef long long ll;

using namespace std;

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

    if (n >= 15){
        cout << 800 * n - 200 * (n / 15) << endl;
    }
    else
    {
        cout << 800 * n << endl;
    }
    return 0;
}

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

using namespace std;

const int size = 2e5 + 7;
int ans[2][3];
int activities[3][size];


int main(){
	int n;
	memset(ans, 0, sizeof(ans));
	cin>>n;
	for(int x=0;x<n;x++){
		for(int i=0;i<3;i++){
			cin>>activities[i][x];
		}
	}
	for(int x=0;x<n;x++){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(i == j) continue;
				ans[x%2][i] = max(ans[x%2][i], activities[i][x] + ans[((x-1)%2 + 2)%2][j]);
			}
			// cout<<ans[x%2][i]<<" ";
		}
		// cout<<"\n";
	}

	int totalCost = 0;
	for(int i=0;i<3;i++){
		totalCost = max(totalCost, ans[(n-1)%2][i]);
	}
	cout<<totalCost;
	return 0;
}

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

using namespace std;
int main()
{
    string s;
    cin >> s;
    if(s[0] != 'A'){
        cout << "WA" << endl;
        return 0;
    }
    int c = 0;
    int n = -1;
    for(int i = 2; i <= s.size()-2; i++){
        if(s[i] == 'C'){
            c++;
            n = i;
        }
    }
    if(c != 1){
        cout << "WA" << endl;
        return 0;
    }
    for(int i = 1; i < s.size(); i++){
        if(i != n && s[i] < 'a'){
            cout << "WA" << endl;
            return 0;
        }
    }

    cout << "AC" << endl;

    return 0;
}










Measured memory_bytes: 256
import itertools

n,m=map(int,input().split())

lis=[]

for _ in range(m):
  lis.append(list(map(int,input().split())))

p=list(map(int,input().split()))

ans=0
for binary in itertools.product([0,1],repeat=n):
  check=0
  for i in range(m):
    numon=0
    ki=lis[i][0]
    for j in range(ki):
      numon+=binary[lis[i][j+1]-1]
    if (numon+p[i])%2!=0:
      check+=1
  if check==0:
    ans+=1

print(ans)

Measured memory_bytes: 9024
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<iterator>
#include<stack>
#include<queue>
#include<utility>
#include<functional>
#include<bitset>
#include<numeric>
#include<cstring>
#include<tuple>
using namespace std;

typedef vector< vector< long long > > Matrix;
int n, mod = 1e9 + 7;
long long k, ans = 0;
Matrix adj( 51, vector< long long >( 51, 0 ) ), I( 51, vector< long long >( 51, 0 ) );

Matrix mul( Matrix& a, Matrix& b )
{
	Matrix res( 51, vector< long long >( 51, 0 ) );
	for( int i = 1; i <= 50; ++i )
	{
		for( int j = 1; j <= 50; ++j )
		{
			for( int k = 1; k <= 50; ++k )
			{
				res[ i ][ j ] += a[ i ][ k ] * b[ k ][ j ];
				res[ i ][ j ] %= mod;
			}
		}
	}
	return res;
}

Matrix bin( long long n )
{
	if( n == 0 )
	{
		return I;
	}
	Matrix res;
	if( n & 1 )
	{
		res = bin( n - 1 );
		return mul( res, adj );
	}
	else
	{
		res = bin( n / 2 );
		return mul( res, res );
	}
}

int main( void )
{
	ios :: sync_with_stdio( 0 );
	cin.tie( 0 );
	
	for( int i = 1; i <= 50; ++i )
	{
		I[ i ][ i ] = 1;
	}
	cin >> n >> k;
	for( int i = 1; i <= n; ++i )
	{
		for( int j = 1; j <= n; ++j )
		{
			cin >> adj[ i ][ j ];		
		}		
	}
	adj = bin( k );
	for( int i = 1; i <= n; ++i )
	{
		for( int j = 1; j <= n; ++j )
		{
			ans += adj[ i ][ j ];
			ans %= mod;		
		}		
	}
	cout << ans << "\n";		
	return 0;
}

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

int A[100],n,s=0;

void selectionSort(int A[], int n){
    int minj;
    for(int i=0; i<n; i++){
        minj = i;
        for(int j=i; j<n; j++){
            if(A[j]<A[minj]){
                minj = j;
            }
        }
        if(i!=minj){
            s++;
            swap(A[i],A[minj]);
        }
    }
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> A[i];
    }
    
    selectionSort(A,n);
    
    for(int i=0; i<n; i++){
        if(i) cout << ' ';
        cout << A[i];
    }
    cout << endl;
    cout << s << endl;
    
    return 0;
}

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    string S;
    int Q;
    cin >> S >> Q;
    deque<char> l, r;
    bool flag = true;
    int T, F;
    char C;
    for (int i = 0; i < Q; i++) {
        cin >> T;
        if (T == 1) flag = !flag;
        else {
            cin >> F >> C;
            if (F == 1) {
                if (flag) l.push_front(C);
                else r.push_back(C);
            } else {
                if (flag) r.push_back(C);
                else l.push_front(C);
            }
        }
    }
    if (flag) {
        for (char c : l) cout << c;
        cout << S;
        for (char c : r) cout << c;
        cout << "\n";
    } else {
        while (!r.empty()) {
            cout << r.back();
            r.pop_back();
        }
        reverse(S.begin(), S.end());
        cout << S;
        while (!l.empty()) {
            cout << l.back();
            l.pop_back();
        }
        cout << "\n";
    }
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
int a[101];

int main() {
  int N;
  cin >> N;
  
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  
  sort(a, a + N);
  reverse(a, a + N);
  
  int A = 0, B = 0;
  
  for (int i = 0; i < N; i++) {
    if (i % 2 == 0) {
      A += a[i];
    }
    else {
      B += a[i];
    }
  }
  
    cout << A - B << endl;
    return 0;
}


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

int main(){
	ll n,k;
	cin>>n>>k;
	if (n==0||n==1){
		cout<<1<<endl;
		return 0;
	}
	cout<<int(ceil(log(n)/log(k)))<<endl;
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

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

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
    int w, h, n; cin >> w >> h >> n;
    vector<vector<int> > lis(w, vector<int>(h, 0));
    REP(i, 0, n){
        int x, y, a; cin >> x >> y >> a;
        if(a == 1){
            REP(l, 0, w){
                REP(j, 0, h){
                    if(l < x){
                        lis[l][j] = 1;
                    }
                }
            }
        }else if(a == 2){
            REP(l, 0, w){
                REP(j, 0, h){
                    if(l >= x){
                        lis[l][j] = 1;
                    }
                }
            }
        }else if(a == 3){
            REP(l, 0, w){
                REP(j, 0, h){
                    if(j < y){
                        lis[l][j] = 1;
                    }
                }
            }
        }else if(a == 4){
            REP(l, 0, w){
                REP(j, 0, h){
                    if(j >= y){
                        lis[l][j] = 1;
                    }
                }
            }
        }
    }
    int ans = w * h;
    REP(l, 0, w){
        REP(j, 0, h){
            ans -= lis[l][j];
        }
    }
    cout << ans << endl;
}

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

using namespace std;

int main() {
	int N;
	cin >> N;
	if (N == 1) cout << "Hello World" << endl;
	else if (N == 2) {
		int A, B;
		cin >> A >> B;
		cout << A + B << endl;
	}
	return 0;
}

Measured memory_bytes: 3540
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> x;
	x.resize(n);
	for(int i = 0; i < n; ++i) {
		cin >> x[i];
	}
	int ans = 1e9;
	for(int i = 1; i <= 100; ++i) {
		int tmp = 0;
		for(auto p : x) {
			tmp += (p - i) * (p - i);
		}
		ans = min(ans, tmp);
	}
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MAX = 2e6;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    ll x, y, i, j;
    cin >> x >> y;
    if ((x+y)%3!=0){
        cout << 0 << endl;
        return 0;
    }
    i = y - (x+y)/3;
    j = x - (x+y)/3;
    ll num = i + j;
    COMinit();
    ll ans = COM(i+j, i);
    cout << ans << endl;
}

Measured memory_bytes: 50476
S = input()
N = len(S)
for i in range(int((N-1)/2)):
  if S[i] != S[-(i+1)]:
    print("No")
    exit()
half = S[0:int((N-1)/2)]
for i in range(int((N-1)/4)):
  if half[i] != half[-(i+1)]:
    print("No")
    exit()
print("Yes")

Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
long long t,a,b,c,d,g;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>a>>b>>c>>d;
		g=__gcd(d,b);
		if(a<b||d<b||(a-(a-c-1)/g*g)-b<0)cout<<"No\n";else cout<<"Yes\n";
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
	
int main(){
	int i,j,k;
	int n,sum;
	int num[1000000];
	
	for(i=0;i<30;i++){
		if(EOF == scanf("%d",&n)) break;
		for(j=2;j<n+1;j++) num[j] = 1;
		
		sum = 0;
		
		for(j=2;j<=n;j++)
			if(num[j] == 1)
				for(k=j+j;k<=n;k+=j) num[k] = 0;
		
		for(j=2;j<=n;j++) sum += num[j];
		printf("%d\n",sum);
	}
	
	return 0;
}

Measured memory_bytes: 4500
#include <iostream>
#include <vector>
#include <unordered_map>
#include <iomanip>

using namespace std;

int main()
{
	unsigned long N;

	cin >> N;
	cout << endl;

	unordered_map<unsigned long, unsigned long> list; //数字，数量
	vector<unsigned long> num; //数字
	unordered_map<unsigned long,unsigned long> full; //数字,num番目を抜かない場合の各場合
	
	for (int i = 0; i < N; ++i) {
		unsigned long in;
		cin >> in;
		list[in] += 1;
		num.emplace_back(in);
	}

	unsigned long long sum = 0;

	for (const auto& elem : list) {
		full[elem.first] = elem.second*(elem.second - 1) / 2;
		sum += full[elem.first];
	}

	for (const auto& _num : num) {
		unsigned long long _sum = sum - full[_num] + (list[_num] - 1)*(list[_num] - 2) / 2;
		cout << _sum << endl;
	}
}

Measured memory_bytes: 16060
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  int N,K;
  cin >> N >> K;
  vector<int> A;
  int tmp;
  for(int i=0; i<N; i++){
    cin >> tmp;
    A.push_back(tmp);
  }
  sort(A.begin(), A.end());
  int result=0;
  for(int i=0; i<K; i++){
    result += A.at(i);
  }
  cout << result << endl;
  return 0;
}


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

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

  vector <int> M(101);

  //鏡餅の大きさを配列Mに格納する
  for (int i = 0; i < N; i++) {
    cin >> M.at(i);
    /* code */
  }
  //鏡餅を大きい順に並び替える
  sort(M.begin(),M.end());
  reverse(M.begin(),M.end());

  int ans = 0;
  //鏡餅の大きさを比較する
  for (int i = 0; i < N; i++) {
    if(M.at(i) > M.at(i+1)) ans++;     
  }
  cout << ans;


}


Measured memory_bytes: 256
import java.util.*

fun main(args : Array<String>) {
    println(inOutExec(null))
}

fun inOutExec(scanner: Scanner?): String {
    val (numOfPref, numOfCity) = readLine()!!.split(" ").map { it.toInt() }

    val citiesIn = mutableListOf<Pair<Int, Int>>()
    repeat(numOfCity) {
        val (pref, year) = readLine()!!.split(" ").map { it.toInt() }
        citiesIn.add(Pair(pref, year))
    }

    val cityCodeMap = citiesIn
            .asSequence()
            .groupByTo(mutableMapOf()) { it.first }
            .flatMap { entry -> entry.value
                    .sortedBy { info -> info.second }
                    .mapIndexed { index, pair ->
                        pair to "%06d%06d".format(pair.first, index + 1) }
            } // Pair<Pair<Int, Int>, String>
            .toMap()

    return citiesIn.joinToString(separator = "\n", postfix = "\n") { cityCodeMap[it]!! }
}


Measured memory_bytes: 155768
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n;i>=0;i--)
#define For(i,m,n) for(int i=m;i<n;i++)
#define Forr(i,m,n) for(int i=m;i>n;i--)
#define Sort(a) sort(a.begin(),a.end())
#define pb push_back
#define vl vector<ll>
#define vll vector<vector<ll>>
#define INF 999999999

int main(){
  int N,count=0;
  double x[9],y[9],dis[9][9],sum=0.0;
  cin>>N;
  vl p(N);
  rep(i,N){
    p[i]=i+1;
    cin>>x[i+1]>>y[i+1];
  }
  //距離計算(有向),Maxで64
  For(i,1,N+1){
      For(j,1,N+1){
        dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
      }
  }

  do{
    rep(i,N-1){//各場合の距離
      sum+=dis[p[i]][p[i+1]];
    }
    count++;
  }while(next_permutation(p.begin(),p.end()));

  cout<<fixed<<setprecision(7)<<sum/count<<endl;

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,a,b) for (int i = (b-1); i >= (a); i--)
#define REP(i,n) FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1e9+7;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

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

string s, t;

int dp[3100][3100] = {0};

int main () {
  cin >> s >> t;

  REP(i,s.size()) {
    REP(j,t.size()) {
      if (s[i] == t[j]) chmax(dp[i+1][j+1], dp[i][j]+1);
      chmax(dp[i+1][j+1], dp[i+1][j]);
      chmax(dp[i+1][j+1], dp[i][j+1]);
    }
  }

  string ans = "";
  int i = (int)s.size(), j = (int)t.size();
  while (i>0 && j>0) {
    if (dp[i][j] == dp[i-1][j]) {
      i--;
    }
    else if (dp[i][j] == dp[i][j-1]) {
      j--;
    }
    else {
      ans = s[i-1] + ans;
      i--, j--;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 37120
def main():
    num = int(input())
    sort_nums = list(map(int, input().split()))
    
    min_num_index = 0
    temp_counter = 0
    for i in range(0, num):
        min_num_index = i
        for j in range(i, num):
            if sort_nums[j] < sort_nums[min_num_index]:
                min_num_index = j

        if not sort_nums[i] == sort_nums[min_num_index]:
            temp_counter += 1

            temp = sort_nums[i]
            sort_nums[i] = sort_nums[min_num_index]
            sort_nums[min_num_index] = temp
        
    print(" ".join([str(n) for n in sort_nums]))
    print(temp_counter)

if __name__ == '__main__':
    main()


Measured memory_bytes: 5608
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
#include <sstream>
#include <cassert>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<long long,int> P;
static const int INF=1<<24;




string inst(int number){
	string res;
	stringstream ss;
	ss<<number;
	ss>>res;
	//cout<<res<<endl;
  return res;
}

bool foo(int a){
	//cout<<a<<endl;
	string s;
	s=inst(a);
	//cout<<s<<endl;
	rep(i,s.size()){
		if(s[i]!=s[s.size()-1-i]) return false;
	}
	return true;
}


int main(){
	int n;
	cin>>n;
	rep(i,INF){
		if(foo(n-i)){
			cout<<n-i<<endl;
			break;
		}
		else if(foo(n+i)){
			cout<<n+i<<endl;
			break;
		}
	}
	return 0;
}

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

int main(){
    int n, p;
    while(cin >> n >> p, n+p){
        int a[50] = {}, wan = p, step = 0;
        while(1){
            if(wan > 0) wan--, a[step%n]++;
            else if(a[step%n])  wan += a[step%n], a[step%n] = 0;
            if(a[step%n] == p)  break;
            step++;
        }
        cout << step%n << endl;
    }
    return 0;
}


Measured memory_bytes: 3080
n=int(input())
h=list(map(int,input().split()))

dp=[float('inf') for i in range(n)]

dp[0]=0
dp[1]=abs(h[1]-h[0])

for i in range(2,n):
 dp[i]=min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]))

print(dp[-1])

Measured memory_bytes: 52728
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 26 17:37:27 2020

@author: divyarth
"""

import sys
import heapq
import math

#sys.setrecursionlimit(50000)
#input=sys.stdin.readline
#print=sys.stdout.write

from collections import deque
from collections import defaultdict
from collections import Counter

modH=int(10**9)+7

I=lambda : list(map(int,input().split(' ')))
def PRINT(lst,sep=' '): print(sep.join(map(str,lst)))

n,m=I()
edges=[I() for i in range(m)]
graph=[[] for i in range(n)]

for src,des in edges:
    graph[src-1].append(des-1)
    graph[des-1].append(src-1)

def bfs(node):
    queue=deque()
    queue.append(node)
    while queue:
        cur=queue.popleft()
        for w in graph[cur]:
            if visited[w]==None:
                queue.append(w)
                visited[w]=1

visited=[None]*n
cmp=0
for i in range(n):
    if visited[i]==None:
        bfs(i)
        cmp+=1

print(cmp-1)

Measured memory_bytes: 98312
line = input()
n = int(input())

for _ in range(n):
    command = input().split()
    a = int(command[1])
    b = int(command[2])
    if command[0] == 'print':
        print(line[a:b+1])
    if command[0] == 'reverse':
        line = line[:a] + line[a:b+1][::-1] + line[b+1:]
    if command[0] == 'replace':
        line = line[:a] + command[3] + line[b+1:]


Measured memory_bytes: 5608
//Modular Inverse Template by Le Tang Phu Quy
#include<bits/stdc++.h>

#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define taskname "test"
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define LL long long
#define MOD 998244353
#define INF 1000000000000000000
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)

using namespace std;

const int maxN = 1e6+5;
LL fact[maxN], ifact[maxN];
LL powerMod(LL a, LL n, LL m);
void computeFactorials(int N);
LL combination(int n, int k);

int main()
{
	FASTIO;
	computeFactorials(maxN-4);
    LL N,A,B,K;
    cin >> N >> A >> B >> K;
    if (A<B) swap(A, B);
    int lim = min(N, K/A);
    LL ans = 0;
    for (int x=0; x<=lim; x++) {
        if ((K-A*x)%B) continue;
        int y = (K-A*x)/B;
      	if (y > N) continue;
        LL nWays = (combination(N,x) * combination(N,y)) % MOD;
        ans += nWays;
        ans %= MOD;
    }
    cout << ans;
	return 0;
}

LL powerMod(LL a, LL n, LL m) {
	if (n==0) return 1;
	if (n==1) return (a%m);
	LL ans = powerMod(a,n/2,m);
	ans *= ans, ans %= m;
	if (n%2) ans *= a, ans %= m;
	return ans;
}

void computeFactorials(int N) {
	fact[0]=1;
	for (int i=1; i<=N; i++)
		fact[i] = (i*fact[i-1])%MOD;
	ifact[N] = powerMod(fact[N], MOD-2, MOD);
	for (int i=N-1; i>=0; i--)
		ifact[i] = ((i+1)*ifact[i+1])%MOD;
}

LL combination(int n, int k) {
	return  ((fact[n]*ifact[k])%MOD * ifact[n-k])%MOD;
}
    

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

int main(){
	long long int n,h,w;
	cin>>n>>h>>w;
	long long a[n],b[n],count=0;
	for(int i=0;i<n;++i){
		cin>>a[i]>>b[i];
		if(h<=a[i] && w<=b[i]){
			count++;
		}
	}
	cout<<count;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <string>
#include <complex>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;

typedef complex<int> ci;

int n, m, x, y;
vector<vector<ci> > v;

bool equiv(vector<ci>& a, vector<ci>& b) {
	int np = a.size();
	if(np != b.size()) return false;

	repd(i,np-1,0) {
		a[i] -= a[0];
		b[i] -= b[0];
	}

	ci rot(0, 1);
	rep(i,4) {
		bool ret = true;
		rep(j,np) {
			if(a[j] != b[j]) {
				ret = false;
				break;
			}
		}
		if(ret) return true;

		rep(j,np) b[j] *= rot;
	}

	rep(i,np) {
		b[i] -= b[np-1];
	}
	
	rep(i,4) {
		bool ret = true;
		rep(j,np) {
			if(a[j] != b[np-j-1]) {
				ret = false;
				break;
			}
		}
		if(ret) return true;
		
		rep(j,np) b[j] *= rot;
	}

	return false;
}

void solve() {
	set<int> s;
	repa(i,1,n) {
		if(equiv(v[0], v[i])) {
			cout << i << endl;
		}
	}
	cout << "+++++" << endl;
}

int main() {
	while(cin>>n,n) {
		v = vector<vector<ci> >(n+1);
		rep(i,n+1) {
			cin >> m;
			v[i] = vector<ci>(m);
			rep(j,m) {
				cin >> x >> y;
				v[i][j] = ci(x, y);
			}
		}
		solve();
	}
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define pb push_back
#define mp make_pair
#define inff 100000
#define ff first
#define ss second
#define sz(x) ((int) (x).size())
#define fast cin.sync_with_stdio(0);cin.tie(0)
#define rep(i,N) for(int i = 0;i < N;i++)
#define frep(i,a,b) for(int i = a;i <= b;i++)
#define pii pair<int , int>
#define pll pair<ll , ll>
#define vii vector<int>
#define vpii vector< pii >
#define fill(A,v) memset(A,v,sizeof(A))
#define setbits(x) __builtin_popcountll(x)
#define print(A,j,k) for(int ii=j;ii<k;ii++)cout<<A[ii]<<" ";cout<<"\n"
#define all(x) (x).begin(), (x).end()
#define gcd __gcd
#define CASES int t;cin>>t;while(t--)
#define FILE freopen("inp.txt" , "r" , stdin);
#define ld long double


const int MOD = 1e9 + 7;
const int N = 1e6 + 5;
const int K = (1 << 17) + 10;
const ll INF = 2e18 + 500;
const int inf = 2e9 + 500;
const int SQRT = 500;
const int lgN = 20;

int main(int argc, char const *argv[])
{
	fast;

	int n;
	cin >> n;
	vii A(n);
	rep(i , n) cin >> A[i];
	sort(all(A));
	// print (A , 0 , A.size());
	ll ans = 0;
	for (int i = 1;i < n;i++) ans += A[i] - A[i - 1];
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//    std::sort(a.begin(), a.end(), std::greater<int>() );
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

using namespace std;
std::vector<std::string> split(const std::string &input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter))
    {
        result.push_back(field);
    }
    return result;
}

int main()
{
    string input;
    vector<vector<int>> data;
    vector<vector<int>> memo;
    while (cin >> input)
    {
        vector<int> hoge;
        vector<int> m;
        for (const std::string &s : split(input, ','))
        {
            hoge.push_back(stoi(s));
            m.push_back(0);
        }
        data.push_back(hoge);
        memo.push_back(m);
    }
    memo[0][0] = data[0][0];
    REP(i, 1, data.size())
    {
        rep(j, data[i].size())
        {
            if (i <= (data.size() / 2))
            {
                if (j == 0)
                    memo[i][j] = memo[i - 1][j] + data[i][j];
                else if (data[i - 1].size() == j)
                    memo[i][j] = memo[i - 1][j - 1] + data[i][j];
                else
                    memo[i][j] = max(memo[i - 1][j] + data[i][j], memo[i - 1][j - 1] + data[i][j]);
            }
            else
            {
                memo[i][j] = max(memo[i - 1][j] + data[i][j], memo[i - 1][j + 1] + data[i][j]);
            }
        }
    }
    cout << memo[memo.size() - 1][memo[memo.size() - 1].size() - 1] << endl;
    return 0;
}

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

char s[1000];

int main() {
    scanf("%s", s);
    int n = strlen(s);
    if (strcmp(s, "keyence") == 0) {
        puts("YES");
        return 0;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            static char t[1000];
            int tot = 0;
            for (int k = 0; k < n; ++k) {
                if (k < i || k > j) {
                    t[tot++] = s[k];
                }
            }
            t[tot] = 0;
            if (strcmp(t, "keyence") == 0) {
                puts("YES");
                return 0;
            }
        }
    }
    puts("NO");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VP = vector<P>;
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; }

int main(){
    int w, h, n;
    cin >> w >> h >> n;
    VVI mp(h, VI(w));
    rep(i,n){
        int x, y, a;
        cin >> x >> y >> a;
        if (a == 1){
            for(int j = 0; j < h; j++){
                for(int k = 0; k < x; k++){
                    mp[j][k] = 1;
                }
            }
        }else if (a == 2){
            for(int j = 0; j < h; j++){
                for(int k = x; k < w; k++){
                    mp[j][k] = 1;
                }
            }
        }else if (a == 3){
            for(int j = 0; j < y; j++){
                for(int k = 0; k < w; k++){
                    mp[j][k] = 1;
                }
            }
        }else{
            for(int j = y; j < h; j++){
                for(int k = 0; k < w; k++){
                    mp[j][k] = 1;
                }
            }
        }
    }
    int ans = 0;
    rep(i, h) rep(j, w){
        if (mp[i][j] == 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

Q = int(input())
ss = input()
t, A, B = map(int, ss.split())
PQ1, PQ2 = [-A], [A]
fr = to = A
minF = 0
accB = B
anss = []
for _ in range(Q-1):
    ss = input()
    if ss[0] == '1':
        t, A, B = map(int, ss.split())
        if fr <= A <= to:
            heappush(PQ1, -A)
            heappush(PQ2, A)
        elif A < fr:
            p = -heappop(PQ1)
            heappush(PQ2, p)
            heappush(PQ1, -A)
            heappush(PQ1, -A)
            minF += fr-A
        else:
            p = heappop(PQ2)
            heappush(PQ1, -p)
            heappush(PQ2, A)
            heappush(PQ2, A)
            minF += A-to
        fr = -heappop(PQ1)
        to = heappop(PQ2)
        heappush(PQ1, -fr)
        heappush(PQ2, to)
        accB += B
    else:
        anss.append((fr, minF+accB))

print('\n'.join(map(lambda x: str(x[0])+' '+str(x[1]), anss)))


Measured memory_bytes: 35928
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x))

using namespace std;

#define a first
#define b second

const ll INF = 1e18;

int main() {
#ifdef HOME
	ifstream cin("C.in");
	ofstream cout("C.out");
#endif
	int i, n, t;
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> t;
	vector <pair <int, int>> arr(n + 1);
	for(i = 1; i <= n; i++) {
		cin >> arr[i].a >> arr[i].b;
		arr[i].a++;
	}
	sort(next(arr.begin()), arr.end(), [&](const pair <int, int> &x, const pair <int, int> &y) {
		if(x.a == 1) {
			if(y.a == 1) return x.b < y.b;
			return true;
		}
		if(y.a == 1) {
			return false;
		}
		return 1LL * x.b * y.a + y.a + y.b > 1LL * y.b * x.a + x.a + x.b;
	});

	vector <ll> best(41, INF);
	best[0] = 0;

	while(arr.size() && arr.back().a >= 2) {
		vector <ll> cur(41, INF);
		for(int j = 0; j < 40; j++) {
			if(best[j] <= t) {
				cur[j + 1] = 1LL * (best[j] + 1) * arr.back().a + arr.back().b;
			}
		}
		for(int j = 0; j <= 40; j++) {
			best[j] = min(best[j], cur[j]);
		}
		arr.pop_back();
	}
	int ans = 0;
	for(int j = 0; j <= 40; j++) {
		if(best[j] >= t + 1) continue;

		ll cur = best[j];
		i = 1;
		while(i < (int)arr.size() && cur + arr[i].b + 1 <= t) {
			cur += arr[i].b + 1;
			i++;
		}
		ans = max(ans, j + i - 1);
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 1792