akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int H = scan.nextInt();
        int W = scan.nextInt();
        int N = scan.nextInt();
        int[] a = new int[N];

        for (int i = 0; i < N; i++) {
            a[i] = scan.nextInt();
        }

        int[][] ret = new int[H][W];
        int index = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < a[i]; j++) {
                int row = index / W;
                int tmp = index % W;
                if(row % 2 == 0) {
                    ret[row][tmp] = i;
                }
                else {
                    ret[row][W - tmp - 1] = i;
                }
                index++;
            }
        }
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                System.out.print(ret[i][j] + 1 + " ");
            }
            System.out.println();
        }
    }

}


Measured memory_bytes: 34912
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#define REP(i,n) for (int i=0;i<(n);i++)

using namespace std;

const int MAX_V = 1010;
vector<vector<int> > G(MAX_V); //??°???????????£??\???????????¨???
bool used[MAX_V]; //DFS??§??¢???????????????????????????????????°
int match[MAX_V]; //??????????????°????????¢

void init(int n){
	for(int i = 0;i < n;i++)G[i].clear();
}

void add_edge(int from, int to){
	G[from].push_back(to);
	G[to].push_back(from);
}

bool dfs(int v){
	used[v] = true;
	for(int i = 0; i < G[v].size(); i++){
		int u = G[v][i],w = match[u];
		if(w < 0 || (!used[w] && dfs(w))){
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}

int bipartite_matching(int V){
	int res = 0;
	fill(match, match + V,-1);
	for(int v = 0;v < V;v++){
		if(match[v] < 0){
			fill(used, used + V, false);
			if(dfs(v))res++;
		}
	}
	/*
	//??????????????????
	REP(i,V){
		if(match[i] >= 0) cout << i << ' ' << match[i] << endl;
		}*/
	return res;
}


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
	int m,n;
	while(cin >> m >> n,m){
		//		int s = m + n,t = s + 1;
		init(m+n);
		vector<int> b(m),r(n);
		REP(i,m){
			cin >> b[i];
			//			add_edge(s,i);//????????§????§??????????????????¶
		}
		REP(i,n){
			cin >> r[i];
			//			add_edge(i + m,t);//????????§???????????????????????¶
		}
		REP(i,m){
			REP(j,n){
				if(__gcd(b[i],r[j]) != 1){
					add_edge(i,j + m);
				}
			}
		}
		cout << bipartite_matching(m+n) << endl;
	}
  return 0;
}

Measured memory_bytes: 5136
program main
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: n,l=0,r,m
    character(100):: na, ma

    read*, n
    print'(i0)', 0
    read*, na
    r = n-1

    do while(r-l>1)
        m = (l+r)/2
        print'(i0)', m
        read*, ma
        if (btest(m,0) .eqv. ma == na) then
            r = m
        else
            l = m
        end if
    end do
    print'(i0)', r
end program main

Measured memory_bytes: 3816
#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int main(void)
{
	int a,b,h,m;
	double r,c,c2;
	scanf("%d %d %d %d",&a,&b,&h,&m);
	r=(double)m*M_PI/30.0-((double)h+(double)m/60.0)*M_PI/6.0;
	c=(double)a*a+(double)b*b-2.0*(double)a*b*cos(r);
	c2=sqrt(c);
	printf("%.9lf\n",c2);
	return 0;
}

Measured memory_bytes: 2556
#include<stdio.h>

int main()
{
	int n, i, x;
	scanf("%d", &n);

	for(i = 1; i <= n; i++) {
		x = i;
		if(x % 3 == 0) {
			printf(" %d", i);
			continue;
		}

		while(x) {
			if(x % 10 == 3) {
				printf(" %d", i);
				break;
			}
			x /= 10;
		}
	}
	printf("\n");

	return 0;
}



Measured memory_bytes: 2040
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort()
q.sort()
r.sort()

res = []
res += p[-X:]
res += q[-Y:]
res += r
res.sort()

print(sum(res[-(X+Y):]))

Measured memory_bytes: 22720
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

#define mod 1e9+7
#define ll long long int
#define epsilon 1e-7

ll min(ll x, ll y){
    if(x<y)return x;
    return y;
}
char s[8001];
int xx[4001];
int yy[4001];
int dx[16001][4001];//dx[j][i]はi-1番目まででj-xmaxが実現するか
int dy[16001][4001];
int main(void){
    int x, y;
    scanf("%s", &s);
    scanf("%d %d", &x, &y);
    int fo = 1;
    int xxx = 0;
    int yyy = 0;
    int me = 0;
    for(int i = 0;s[i]!='\0';i++){
        if(s[i]=='F')me++;
        else{
            if(fo == 1){
                xx[xxx] = me;
                me = 0;
                fo = 2;
                xxx++;
            }else{
                yy[yyy] = me;
                me = 0;
                fo = 1;
                yyy++;
            }
        }
    }
    if(me!=0){
        if(fo == 1){
            xx[xxx] = me;
            me = 0;
            fo = 2;
            xxx++;
        }else{
            yy[yyy] = me;
            me = 0;
            fo = 1;
            yyy++;
        }
    }
    int xmax = 0;
    int ymax = 0;
    for(int i = 0;i < xxx;i++){
        xmax += xx[i];
        //printf("%d ", xx[i]);
    }
    //printf("\n");
    for(int i = 0;i < yyy;i++){
        ymax += yy[i];
        //printf("%d ", yy[i]);
    }
    //printf("\n");
    for(int i = 0;i < xxx + 1;i++){
        for(int j = 0;j < 2*xmax + 1;j++){
            dx[j][i] = 0;
        }
    }
    for(int i = 0;i < yyy + 1;i++){
        for(int j = 0;j < 2*ymax + 1;j++){
            dy[j][i] = 0;
        }
    }
    dx[xmax + xx[0]][1] = 1;
    dy[ymax][0] = 1;
    for(int i = 0;i < xxx;i++){
        for(int j = 0;j < 2*xmax + 1;j++){
            if(dx[j][i]){
                dx[j - xx[i]][i+1] = 1;
                dx[j + xx[i]][i+1] = 1;
            }
        }
    }
    for(int i = 0;i < yyy;i++){
        for(int j = 0;j < 2*ymax + 1;j++){
            if(dy[j][i]){
                dy[j - yy[i]][i+1] = 1;
                dy[j + yy[i]][i+1] = 1;
            }
        }
    }
    if(x + xmax < 0 || y + ymax < 0)printf("No\n");
    else if(dx[x+ xmax][xxx] && dy[y+ ymax][yyy])printf("Yes\n");
    else printf("No\n");
    return 0;
}

Measured memory_bytes: 250624
#include <bits/stdc++.h>
    using namespace std;
    #define ll long long int
    #define pb push_back
    #define mp make_pair
    #define mod 1e9+7
    #define sz 100000
    #define f(i,n) for(ll i=0;i<n;i++)
    #define fab(i,a,b) for(ll i=a;i<b;i++)
    #define fr(i,n) for(ll i=n-1;i>=0;i--)
    #define fba(i,b,a) for(ll i=b-1;i>=a;i--)
    #define tc(t) ll t;cin>>t;while(t--)
     
    ll pw(ll x,unsigned ll y) 
    { 
        if (y==0) 
            return 1; 
        else if (y%2==0) 
            return pw(x,y/2)*pw(x,y/2); 
        else
            return x*pw(x,y/2)*pw(x,y/2);
    }
     
    int main() 
    {
        ios_base::sync_with_stdio(0);
        cin.tie(NULL);
        cout.tie(NULL);
        ll n, ok = 0;
        map<ll, ll> mp;
        cin >> n;
        ll a[n];
        f(i, n) {
            cin >> a[i];
            mp[a[i]]++;
            if(mp[a[i]] > 1)
                ok = 1;
        }
        if(ok)
            cout << "NO";
        else cout << "YES";
        return 0;
    }

Measured memory_bytes: 14412
import sys

S = list(str(input()))
T = list(str(input()))

Max = 0

for i in range(len(S)-len(T)+1):
    hoge = 0
    for j in range(len(T)):
        if S[i+j] == T[j]:
            hoge += 1
    Max = max(Max,hoge)
    
print(len(T)-Max)

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

int main()
{
	int h,w,d;
	cin >> h >> w >> d;
	vector<pair<int,int>> p(h*w);
	for(int i =0 ;i<h;i++)
	{
		for(int j = 0;j<w;j++)
		{
			int a;
			cin >> a;
			a--;
			p[a] = make_pair(i,j);
		}
	}

	vector<ll> sum(h*w+d+d);

	for(int i = 0;i<d;i++)
	{
		for(int j = i;j+d<h*w;j+=d)
		{
			sum[j+d] = sum[j] + abs(p[j+d].first-p[j].first)+abs(p[j+d].second-p[j].second);
		}
	}
	//cout<<sum.size()<<endl;
	int q;
	cin >> q;
	while(q--)
	{
		int l,r;
		cin >> l >>r ;
		l--;
		r--;
		cout<<sum[r]-sum[l]<<endl;
	}
	for(int i = 1;i<h*w+d;i+=d)
	{
		//cout<<sum[i]<<endl;
	}

}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define nl "\n";
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define db double
#define mod 1e9 + 7
#define lb lower_bound
#define ub upper_bound
#define vlli vector<lli>
#define mslli multiset<lli>
#define inf INT_MAX
#define sp " "
#define pb push_back
#define pie 3.14159265358979323846
#define test lli t; cin>>t; while(t--)
int main()
{
    /*#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);*/
	//fastio;
    lli n;
    cin>>n;
    lli a[n],ans=0;
    for(lli i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    if(n<=2)
        cout<<0;
        else
        {
    for(lli i=0;i<n-2;i++)
    {

        for(lli j=i+1;j<n-1;j++)
        {
            if(a[j]!=a[i])
            {
            for(lli k=j+1;k<n;k++)
            {
                if(a[k]!=a[j])
                {
                if((a[i]+a[j])>a[k])
                    ans++;
                }
            }
            }
        }
    }
    cout<<ans;}

}


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

double a, b, h, m, ans;
static const double pi = 3.141592653589793;

int main() {
  cin >> a >> b >> h >> m;
  ans = pow(a,2) + pow(b,2) - 2 * a * b * cos(2*pi*abs((h+m/60)/12-m/60));
  ans = sqrt(ans);
  cout << fixed << setprecision(15) << ans << endl;
  return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

typedef long long ll;
#define READ(a) int a; cin >> a;
#define READARR(a, n) int a[(n) + 1]; FOR(i, 1, (n)) {cin >> a[i];}
#define READMAT(a, n, m) int a[n + 1][m + 1]; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}
#define pb(x) push_back(x)
#define vi vector <int>
#define pi pair <int, int>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	READ(n);
	READ(d);
	d = 2*d + 1;
	if (n % d == 0) cout << n/d;
	else cout << n/d + 1;
}

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

using namespace std;
#define int long long
#define INF 1000007
#define MOD 1000000007
#define maxn 100
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)

typedef std::pair<int, int> P;

vector<bool> prime(maxn + 1, true); //素数テーブル
void prime_table(void) {
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= maxn; i++) {
        if (!prime[i]) {
            continue;
        }
        for (int j = i + i; j <= maxn; j += j + i) {
            prime[j] = false;
        }
    }
}

bool IsPrime(int num) //素数判定
{
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

vector<int> divisor(int n) //約数列挙
{
    vector<int> ret;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i - 1);
            if (i * i != n) {
                ret.push_back((n / i) - 1);
            }
        }
    }
    sort(ret.begin(), ret.end());
    return (ret);
}

int a, b;

void f(int x) {
    a = x % 10;
    b = 0;
    while (x) {
        b = x;
        x /= 10;
    }
}

signed main() {
    int N, M;
    cin >> N >> M;
    vector<int> ans(N);
    bool check = true;
    rep(i, N) {
        ans[i] = 10;
    }
    rep(i, M) {
        int s, c;
        cin >> s >> c;
        if (ans[s - 1] != c && ans[s - 1] != 10) {
            check = false;
            break;
        } else {
            if (s == 1 && c == 0 && N != 1) {
                check = false;
                break;
            } else
                ans[s - 1] = c;
        }
    }
    if (check)
        rep(i, N) {
            if (ans[i] == 10) {
                if (i == 0 && N != 1)
                    cout << 1;
                else
                    cout << 0;
            } else {
                cout << ans[i];
            }
        }
    else
        cout << "-1";
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define FOR(i,s,e) for((i)=(s);(i)<(int)(e);(i)++)
#define REP(i,e) FOR(i,0,e)
 
#define all(o) (o).begin(), (o).end()
#define psb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
 
typedef long long ll;
typedef pair<int, int> PII;
 
const double EPS = 1e-10;
 
const int H = 10;
const int W = 5;
int h;
int c[H][W];
 
int main() {
  int i, j, k, l;
  int res;
 
  while (1) {
    scanf("%d ", &h); 
    if (!h) break;
 
    for (i=0; i<h; i++)
      for (j=0; j<W; j++)
        scanf("%d ", &(c[i][j]));
 
    res = 0;
    bool update = true;
    while (update) {
      update = false;
      for (i=h-1; i>=0; i--) {
        for (j=0; j<3; j++) {
          k = 1;
          while (c[i][j]!=0 && j+k<W && c[i][j+k]==c[i][j]) k++;
          if (k >= 3) {
            res += k * c[i][j];
            for (l=j; l<j+k; l++) c[i][l] = 0;
            update = true;
            break;
          }
        }
      }
 
      for (i=h-2; i>=0; i--)
        for (j=0; j<W; j++) {
          int d = i;
          while (d+1<h && c[d+1][j]==0) d++;
          if (i!=d) {
            c[d][j] = c[i][j];
            c[i][j] = 0;
          }
        }
    }
 
    printf("%d\n", res);
  }
 
  return 0;
}

Measured memory_bytes: 1192
import java.util.Scanner;
class Main{
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int s = scan.nextInt();
        int w = scan.nextInt();
        if(s <= w){
            System.out.println("unsafe");
        }else{
            System.out.println("safe");
        }

    }
}

Measured memory_bytes: 35820
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    ll N;
    cin >> N;
    ll m1 = (N / 500) * 1000 + ((N % 500) / 5) * 5;
    ll m2 = (N / 5) * 5;
    cout << max(m1, m2) << '\n';
}


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

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

using namespace std;

int main(){
  ll a,b,c,k;cin>>a>>b>>c>>k;
  if(k%2==0)cout<<a-b;
  else cout<<b-a;

  return 0;
}

Measured memory_bytes: 256
s = input()

stack = []

for i in s:
    if i == 'S':
        stack.append(i)
    if i == 'T':
        if not stack:
            stack.append(i)
            continue
        last = stack.pop()
        if last == 'S':
            continue
        else:
            stack.append(last)
            stack.append(i)

print(len(stack))


Measured memory_bytes: 5092
N,M = map(int,input().split())
P  = list(map(int,input().split()))
xy = [list(map(int,input().split())) for _ in range(M)]


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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def groupsize(self):
        self.cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
        else:
            self.par[y] = x
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def count(self, x):
        return -self.root[self.find(x)]
#
#graph = [[] for _ in range(N)]
#
#for x,y in xy:
#    graph[x-1].append(y-1)
#    graph[y-1].append(x-1)
        
    
uf = UnionFind(N)
for x,y in xy:
    uf.union(x-1,y-1)
    
for i in range(N):
    uf.find(i)
    
idxlist = [[] for _ in range(N)]

for i,t in enumerate(uf.par):
    idxlist[t].append(i)
    
import bisect
ans = 0
for idxs in idxlist:
    for idx in idxs:
        tmpidx = bisect.bisect_left(idxs,P[idx]-1)
        if tmpidx >= len(idxs):continue
        if idxs[tmpidx] == P[idx]-1:
            ans += 1
print(ans)
    
      

Measured memory_bytes: 47108
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <algorithm>
#include <bitset>
#include <math.h>
#include <utility>

typedef long long ll;
typedef unsigned long long ull;

#define vi std::vector<int>
#define vl std::vector<ll>
#define floop(n) for(int i = 0; i < n; ++i)
#define print(x) std::cout << x << std::endl;

const ll INF = 1e18;

int main()
{
    std::string S;
    std::string T;
    int max = 0, cur = 0;

    std::cin >> S;
    std::cin >> T;

    int len_S = S.length(), len_T = T.length();
    max = len_T;

    for(int i = 0; i <= len_S-len_T; ++i)
    {
        cur = 0;
        for(int j = 0; j < len_T; ++j)
        {
            if(S[i+j] != T[j])
                cur++;
        }

        if(cur < max)
            max = cur;
        
        if(max == 0)
            break;
    }
   

    print(max);
    return 0;
}

Measured memory_bytes: 3588
#include<stdio.h>
#include<stdlib.h>
int main(void){
int n,i;
int data[10000];
int min,max;
double sum;

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

for(i=1;i<n;i++){
  if(min>data[i]){min=data[i];}
  if(max<data[i]){max=data[i];}
  sum=sum+data[i];
}
printf("%d %d %.0f\n",min,max,sum);


	return 0;
}

Measured memory_bytes: 676
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ul  unsigned long long int
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define mod
//ll divide(ll a, ll b)  //euler's theorem(a/b)%mod
//{
//   return a*power(b,mod-2)%mod;  //only when mod is prime
//}

ll power(ll x, ll y)
{
    ll res = 1;
   while (y > 0) {
        if (y & 1)
            res = res * x;
        y = y >> 1;
        x = x * x;
    }
    return res;
}
int n,w;
ll a[3][107];
ll dp[107][100006];
ll solve(int i,int w)
{
	if(i==n+1)
	return 0;
	ll cnt1=0,cnt2=0;
	if(dp[i][w]!=-1)
	return dp[i][w];
	
	if(a[1][i]<=w)
	cnt1=max(a[2][i]+solve(i+1,w-a[1][i]),solve(i+1,w));
	else
	cnt1=solve(i+1,w);
	return dp[i][w]=cnt1;
}

int main()
{
    speed;
    cin>>n>>w;
    for(int i=0;i<107;i++)
    	for(int j=0;j<100006;j++)
    		dp[i][j]=-1;
    for(int i=1;i<=n;i++) cin>>a[1][i]>>a[2][i];
	cout<<solve(1,w);							    
								
							
	return 0;
}


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

using ll = long long;
using pii = pair<int, int>;

#define     endl               "\n"
#define     fast_io            ios::sync_with_stdio(false); cin.tie(0);
#define     file_io            freopen("input.txt", "r", stdin);   \
                               freopen("output.txt", "w", stdout);
#define     all(x)             begin(x), end(x)
#define     debug(x)           cerr <<"Line "<< __LINE__ <<" : "<< #x " = "<< x <<endl;
 
template<typename T, typename TT>
ostream& operator<<(ostream &os, const pair<T, TT> &t) { return os<<"("<<t.first<<", "<<t.second<<")"; }
template<typename T>
ostream& operator<<(ostream& os, const vector<T> &t) { for(auto& i: t) os<<i<<" "; return os; }


/**
 * Input: a, b, m
 * Output: (a * b) % m
 * 
 * Complexity: O(lg(min(a, b))
 * */

ll bigMul(ll a,ll b,ll m) {
	if(a < b) swap(a, b);
	ll result = 0; a %= m;
	while(b) { if(b&1LL) result=(result+a)%m; a=(a+a)%m; b>>=1LL; }
	return result;
}

/**
 * Input: b, e, m
 * Output: (b^e) % m
 * 
 * Complexity: O(lg(b)) normally
 * 			   O(lg(min(b, m)) * lg(b)) in case of m and b are huge
 * */

//using bigMul(a, b, m) makes it slow.....!!!
ll bigMod(ll b, ll e, ll m) {
	ll res = 1LL%m; b %= m;
	while(e) {
	   
		if(e & 1LL) res = bigMul(res, b, m); // check the ith bit
		e >>= 1LL; // move the (i+1)th bit at pos 0
		b = bigMul(b, b, m); // b = b^(2^(i+1))
		/*
		if(e & 1LL) res = (res * b) % m; /// check the ith bit
		e >>= 1LL; /// move the (i+1)th bit at pos 0
		b = (b * b) % m; /// b = b^(2^(i+1))
		*/
	}
	return (res + m) % m;	/// non negative modulo value
}




int main(int argc, char** argv) {
    fast_io
   
	int m, n, mod = 1e9 + 7;
	cin >> m >> n;
	cout << bigMod(m, n, mod) << endl;

    return 0;
}















Measured memory_bytes: 3160
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<queue>
//#include<bits/stdc++.h>
#define int long long
#define for0(i, n) for(int i = 0; i < (n); i++)
#define for1(i, n) for(int i = 1; i <= (n);i++)
#define mp make_pair
#define all(x) x.begin(),x.end()
#define puts(x) cout << x << "\n"
constexpr int mod = 1000000007;
using namespace std;
int input() { int r; cin >> r; return r; }
signed main() {
	int a; string b; cin >> a >> b;
	int c = (b[0] - '0') * 100 + (b[2] - '0') * 10 + (b[3] - '0');
	a *= c;
	puts(a / 100);
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define dbg(n) cout<<#n<<' '<<n<<endl;
int main(){ 
	int n;
	cin>>n;
	map<string,int>m;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		m[s]++;
		}
		cout<<m.size()<<endl;
	
}



Measured memory_bytes: 19192
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>
#include <cstring>

using namespace std;

#define int long long
#define rep(i, n) for (int i=0;i<(int)n;++i)
#define rep1(i, n) for (int i=1;i<=(int)n;++i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using ll=long long;
using vi=vector<int>;
using pii=pair<int, int>;

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
ll read(){ll a;scanf("%lld",&a);return a;}

const int inf = TEN(9) + 10;
const int mod = TEN(9) + 10;

int N;

signed main()
{
	cin>>N;
	int sum=0;
	for(int i=1;i<=N;++i){
		if (i%3==0 and i%5==0) continue;
		if (i%3==0)continue;
		if (i%5==0) continue;
		sum+=i;
	}
	cout<<sum<<endl;
}




Measured memory_bytes: 3624
n = gets.chomp.to_i
h_n = gets.chomp.split.map(&:to_i)

results = []
n.times do |_|
  results << Float::INFINITY
end

h_n.each.with_index(0) do |h_i, i|
  next results[i] = 0 if i == 0

  cost_from_previous_one = results[i-1] + (h_i - h_n[i-1]).abs
  results[i] = cost_from_previous_one if results[i] > cost_from_previous_one

  next if i == 1

  cost_from_previous_two = results[i-2] + (h_i - h_n[i-2]).abs
  results[i] = cost_from_previous_two if results[i] > cost_from_previous_two
end

puts results[-1]

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 300005;

/* ...o(^-^)o... */

int main(){
    lint n; cin >> n;
    lint ans = 0;
    repn(i, n){
        if(i % 3 == 0 || i % 5 == 0) continue;
        ans += i;
    }
    out(ans);
}

Measured memory_bytes: 3632
use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::cmp;

fn calc(h: i64, w: i64) -> i64 {
    let mut min: i64 = w;
    for h1 in 1..(h + 1) {
        let s1: i64 = h1 * w;
        let h2: i64 = h - h1;
        let w1: i64 = w / 2;
        let w2: i64 = w - w1;

        let s2: i64 = w1 * h2;
        let s3: i64 = w2 * h2;

        let mut max = cmp::max((s1 - s2).abs(), (s1 - s3).abs());
        max = cmp::max(max, (s2 - s3).abs());

        min = cmp::min(min, max);
    }
    min
}

fn main() {
    let mut sc = Scanner::new();
    let h = sc.parse::<i64>();
    let w = sc.parse::<i64>();
    if h % 3 == 0 || w % 3 == 0 {
        println!("0");
        return;
    }

    let ans = cmp::min(calc(h, w), calc(w, h));
    println!("{}", ans);
}


struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

Measured memory_bytes: 4352
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var N = int.Parse(Console.ReadLine());
            var X = Console.ReadLine().Split().Select(elem => int.Parse(elem)).ToArray();

            int answer = int.MaxValue;
            foreach (var P in Enumerable.Range(1, 100))
            {
                int sum = 0;
                foreach (var i in Enumerable.Range(0, N))
                {
                    sum += (int)Math.Pow(X[i] - P, 2);
                }

                if (sum <= answer)
                {
                    answer = sum;
                }
            }

            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 13396
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    a, b, x = map(int, input().split())
    print(b // x + 1 - max(0, (a - 1) // x + 1))


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 38384
import numpy as np

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

c = np.array(c)

last = [0] * 26
satisfied = 0
for i in range(1, D+1):
    last_d = [c[j]*(i-last[j]) for j in range(26)]
    last_d_sum = sum(last_d)
    #選択肢A 満足度の高いものから選ぶ
    s_d = np.array(s[i-1])
    maxindexA = np.argmax(s_d)
    cost_optA = last_d_sum - last_d[maxindexA]
    
    #選択肢B コストが大きいものから選ぶ
    last_d = np.array([c[j]*(i-last[j]) for j in range(26)])
    maxindexB = np.argmax(last_d)
    cost_optB = last_d_sum - last_d[maxindexB]

    if cost_optA <= cost_optB:
        #Aを選択
        print(maxindexA+1)
        last[maxindexA] = i
    else:
        #Bを選択
        print(maxindexB+1)
        last[maxindexB] = i

    



Measured memory_bytes: 27636
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vv vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define INF 100000000000
#define eps 1e-7
#define mod 998244353
#define itn int
#define int ll
using namespace std;

int N;
int a[330];
int dp[90000+10];
//dp[k]:合計kになるような部分和の作り方の場合の数
int dp2[90000+10];
//dp[k]:合計kになるような部分和の作り方の場合の数（ただし２色の場合）

signed main(void) {
    cin>>N;
    int sum=0;
    REP(i, 1, N) {
        cin>>a[i];
        sum+=a[i];
    }
    memset(dp, 0, sizeof(dp));
    dp[0]=1;

//    REP(i, 0, sum) {
//        cerr<<dp[i]<<"\t";
//    }
//    cerr<<endl;

    REP(i,1,N) {
        for(int j=sum; j>=0; j--) {
            if (a[i] <= j) {
                dp[j] = (dp[j] * 2 +  dp[j-a[i]]) % mod;
            } else {
                dp[j] = (dp[j] * 2) % mod;
            }
        }

//        REP(i, 0, sum) {
//            cerr<<dp[i]<<"\t";
//        }
//        cerr<<endl;
    }
//    cerr<<endl;

    if (sum%2==0) {
        memset(dp2, 0, sizeof(dp2));
        dp2[0]=1;

//        REP(i, 0, sum/2) {
//            cerr<<dp2[i]<<"\t";
//        }
//        cerr<<endl;

        REP(i,1,N) {
            for(int j=sum/2; j>=0; j--) {
                if (a[i] <= j) {
                    dp2[j] += dp2[j-a[i]];
                    dp2[j] %= mod;
                }
            }

//            REP(i, 0, sum/2) {
//                cerr<<dp2[i]<<"\t";
//            }
//            cerr<<endl;
        }
//        cerr<<"全合計："<<accumulate(dp, dp+sum+1, 0LL)<<endl;
//        cerr<<"引くやつ："<<accumulate(dp+sum/2, dp+sum+1, 0LL)<<endl;
//        cerr<<"足すやつ："<<dp2[sum/2]<<endl;
        int allsum=0;
        for(int i=0; i<=sum; i++) {
            allsum += dp[i];
            allsum %= mod;
        }
        int minus=0;
        for(int i=sum/2; i<=sum; i++) {
            minus += dp[i];
            minus %= mod;
        }
        minus  = (minus * 3)%mod;
        cout<<(allsum + mod - minus + dp2[sum/2] * 3) % mod<<endl;
    } else {
        int allsum=0;
        for(int i=0; i<=sum; i++) {
            allsum += dp[i];
            allsum %= mod;
        }
        cerr<<allsum<<endl;
        int minus=0;
        for(int i=sum/2+1; i<=sum; i++) {
            minus += dp[i];
            minus %= mod;
        }
        minus  = (minus * 3)%mod;
        cerr<<minus<<endl;
        cout<<(allsum + mod - minus) % mod<<endl;
    }
    return 0;
}

Measured memory_bytes: 1664
a, b = gets.split(' ')
sum = 0
2.times do
    if a.to_i > b.to_i then
        sum = sum + a.to_i
        a = a.to_i - 1
    else
        sum = sum + b.to_i
        b = b.to_i - 1
    end
end

print sum

Measured memory_bytes: 1916
#include <iostream>
#include <cstdio>
using namespace std;
long long n;
char s[4010];
long long cnt[4010][3];//0:R 1:G 2:B
long long ans;
long long f(char c) {
	if (c == 'R') return 0;
	if (c == 'G') return 1;
	return 2;
}
long long g(char a, char b) {
	return (3 - f(a) - f(b)) % 3;
}
int main() {
	scanf("%lld%s", &n, s + 1);
	for (long long i = n; i >= 1; i--) {
		cnt[i][0] = cnt[i + 1][0];
		cnt[i][1] = cnt[i + 1][1];
		cnt[i][2] = cnt[i + 1][2];
		cnt[i][f(s[i])]++;
	}
	for (long long i = 1; i < n - 1; i++) {
		for (long long j = i + 1; j < n; j++) {
			if (s[i] == s[j]) continue;
			ans += cnt[j + 1][g(s[i], s[j])];
			if (j + j - i <= n && f(s[j + j - i]) == g(s[i], s[j])) ans--;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

/**
 * Pattern - Largest Square
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;

		line = br.readLine();

		int H, W;
		H = parseInt(line.substring(0, line.indexOf(' ')));
		W = parseInt(line.substring(line.indexOf(' ') + 1));

		int[][] dp = new int[H + 1][W + 1];

		for (int i = 1; i <= H; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= W; j++) {
				dp[i][j] = parseInt(st.nextToken()) == 1 ? 0 : 1;
			}
		}

		int max = 0;

		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				if (dp[i][j] == 1) {
					dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
					max = Math.max(max, dp[i][j]);
				}
			}
		}

		System.out.println(max * max);

	}
}

Measured memory_bytes: 91508
#include <stdio.h>
#include <string.h>

int main() {
    char cards[201], subbuff1[201], subbuff2[201];
    int m, h, len, i;
    while (scanf("%s", cards) && strcmp(cards, "-")) {
        len = strlen(cards);
        scanf("%d", &m);
        for (i = 0; i < m; i++) {
            scanf("%d", &h);
            memcpy(subbuff1, &cards, h);
            subbuff1[h] = '\0';
            memcpy(subbuff2, &cards[h], len - h);
            subbuff2[len - h] = '\0';
            strcpy(cards, strcat(subbuff2, subbuff1));
        }
        printf("%s\n", cards);
    }
    return 0;
}

Measured memory_bytes: 620
#include <bits/stdc++.h>
#define sz(arr) (int)(arr).size()
#define rng(arr) arr.begin(), arr.end()
#define show(x) cout << #x << " = " << x << endl;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
typedef long long int ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

#define Cins(T, n, xs) \
  vector<T> xs(n);     \
  for (int i = 0; i < n; ++i) cin >> xs[i]

void Main();
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(15);
  Main();
  return 0;
}

void Main() {
  Cin(int, n);
  Cins(int, n, a);

  int b1, b2, b4;
  b1 = b2 = b4 = 0;
  for (auto e : a) {
    if (e % 4 == 0)
      b4++;
    else if (e % 2 == 0)
      b2++;
    else
      b1++;
  }
  if (b2 >= 1) b1++;

  cout << (b1 <= b4 + 1 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 640
import java.util.*
import java.math.*
import java.lang.Math.*

private val readString: ()->String = {readLine()!!}
private val readInt: ()->Int = { readLine()!!.toInt() }
private val readLong: ()->Long = { readLine()!!.toLong() }
private val readListInt: ()->List<Int> = { readLine()!!.split(' ').map(String::toInt) }
private val readListLong: ()->List<Long> = { readLine()!!.split(' ').map(String::toLong) }
private val errPrintln: (String)->Unit = { msg -> System.err.println(msg) }
private val MOD = 1e9.toLong()+7


class UnionFind(val N: Int) {
    private val dt = IntArray(N+1){-1}
    tailrec fun root(key: Int): Int {
        if (this.dt[key] < 0) {
            return key
        } else {
            this.dt[key] = this.root(this.dt[key])
            return this.dt[key]
        }
    }
    fun unite(KX: Int, KY: Int): Boolean {
        var kx = this.root(KX); var ky = this.root(KY)
        if (kx == ky) {
            return false
        }
        if (this.size(kx) < this.size(ky)) {
            val tmp = kx
            kx = ky
            ky = tmp
        }
        this.dt[kx] += this.dt[ky]
        this.dt[ky] = kx
        return true;
    }
    fun size(key: Int): Int {
        val rk = this.root(key)
        return -this.dt[rk]
    }
    fun isConnect(kx: Int, ky: Int): Boolean {
        return this.root(kx) == this.root(ky)
    }
}


fun solveD(N: Int, M: Int, A: IntArray, B: IntArray): LongArray {
    val uf = UnionFind(N)
    val ans = LongArray(M+1)
    ans[M] = N.toLong()*(N-1)/2

    for(i in M-1 downTo 0) {
        val a = A[i]; val b = B[i]
        if (uf.isConnect(a, b)) {
            ans[i] = ans[i+1]
        } else {
            ans[i] = max(0L, ans[i + 1] - uf.size(a).toLong() * uf.size(b))
            uf.unite(a, b)
        }
    }

    return ans
}


fun main(args: Array<String>) {
    val (N, M) = readListInt()
    //val AB = Array(M){Pair(0,0)}
    val A = IntArray(M)
    val B = IntArray(M)
    for(i in 0 until M) {
        val (a, b) = readListInt().map { it -1 }
        A[i] = a
        B[i] = b
    }

    val ans = solveD(N, M, A, B)

    for (i in 1..M) {
        println(ans[i])
    }
}


Measured memory_bytes: 57844
#include<bits/stdc++.h>
using namespace std;
int a[100000+2];
int main()
{
	int n;
	cin>>n;
	int s=0;
	for(int i=1;i<=n;i++)
	{
		int b;
		cin>>b;
		if(b==0)
		s++;
		else
		a[b-1]++;
		a[b]++;
		a[b+1]++;
	}
	int max=s;
	for(int i=0;i<100000+2;i++)
	if(a[i]>max)
	max=a[i];
	cout<<max;
	return 0;
 } 

Measured memory_bytes: 640
N = int(input())
ans = N
def F(a,b):
    return max([len(str(i))for i in [a,b]])
for i in range(1,N+1):
    if i*i>N:break
    if N%i==0:
        a,b = i,N//i
        ans = min(ans,F(a,b))
print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long ll;

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

	vector<int> member(a);
	rep(i, a) cin >> member.at(i);

	int cnt = 0;
	rep(i, a) {
		if (member.at(i) >= b) cnt++;
	}

	cout << cnt << endl;

	return 0;
}

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

using namespace std;

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

  int n, m;
  cin >> n >> m;
  vector< pair<int,int> > cost(n);
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    cost[i] = make_pair(a, b);
  }
  sort(cost.begin(), cost.end());

  long long sum = 0;
  int num = 0;
  for (int i = 0; i < n; i++) {
    int price, cnt;
    tie(price, cnt) = cost[i];
    int buy = min(cnt, m - num);
    sum += (long long) buy * price;
    num += buy;
  }
  cout << sum << '\n';
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <random>
//-------------------------------------------------------------------------
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define prv(v) for (auto i : v) { cout << i << " ";}
#define prmat(v) for (auto i : v) { prv(i); cout << "\n";}
#define cout(x) cout << fixed << setprecision(x)
#define read(v) for (int i_ = 0; i_ < v.size(); i_++) { cin >> v[i_];}
#define fast_io ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define all(v) (v.begin()), (v.end())
#define rall(v) (v.rbegin()), (v.rend())
#define pii pair<int, int>
//------------------------------------------------------------------------
struct lca{
    vector<vector<int>> g;
    vector<pii> t;
    int n, on;
    int timer = 0;
    vector<int> order, vorder, h, tin;
    void dfs0(int v, int p = -1){
        for(auto to : g[v]){
            if(to != p){
                h[to] = h[v] + 1;
                dfs0(to, v);
            }
        }
    }
    void dfs(int v, int p = -1){
        order.push_back(h[v]);
        vorder.push_back(v);
        for(auto to : g[v]){
            if(to != p){
                dfs(to, v);
                order.push_back(h[v]);
                vorder.push_back(v);
            }
        }
    }
    
    void build(int v, int tl, int tr){
        if(tl == tr){
            t[v] = {order[tl], tl};
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm + 1, tr);
        t[v] = min(t[v * 2], t[v * 2 + 1]);
    }
    
    pii get(int v, int tl, int tr, int l, int r){
        if(tl > r || tr < l){
            return pii{1e9, 1e9};
        }
        if(tl >= l && tr <= r){
            return t[v];
        }
        int tm = (tl + tr) / 2;
        return min(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
    }
    lca(vector<vector<int>> &tt){
        g = tt;
        n = (int)tt.size();
        tin.resize(n, 1e9);
        h.resize(n);
        dfs0(0);
        dfs(0);
        on = (int)order.size();
        for(int i = 0; i < vorder.size(); i++){
            tin[vorder[i]] = min(tin[vorder[i]], i);
        }
        t.resize(on * 4);
        build(1, 0, on - 1);
    }
    int get(int i, int j){
        
        int x = tin[i];
        int y = tin[j];
        if(x > y){
            swap(x, y);
        }
        pii a = get(1, 0, on - 1, x, y);
        return vorder[a.second];
    }
};
void solve(){
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for(int i = 0; i < n; i++){
        int m;
        cin >> m;
        for(int j = 0; j < m; j++){
            int x;
            cin >> x;
            g[i].push_back(x);
            g[x].push_back(i);
        }
    }
    lca x(g);
    int q;
    cin >> q;
    while(q--){
        int a, b;
        cin >> a >> b;
        cout << x.get(a, b) << "\n";
    }
}
int main() {
    fast_io;
#ifdef LOCALKA
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    solve();
}



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

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 1000000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

int main(){
    map<string, int> m;
    int N;
    string S;
    cin >> N;
    ll count = 0;
    FOR(i,1,N) {
        cin >> S;
        if (m.find(S) == m.end()){
            m[S] = 1;
            count += 1;
        }
        else m[S] += 1; 
    }
    cout << count << endl;
}

Measured memory_bytes: 19116
A,B = map(int,input().split())
S = str(input())
for i in range(len(S)):
  if i < A:
    if not S[i].isnumeric():
      print("No")
      exit()
  elif i == A:
    if S[i] != "-":
      print("No")
      exit()
  else:
    if not S[i].isnumeric():
      print("No")
      exit()
print("Yes")

Measured memory_bytes: 9092
#include<iomanip>
#include<iostream>
#include<cstring>
#include<cmath>
#include<time.h>
#include<stdlib.h>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	if(a<=b)puts("unsafe");
	else puts("safe");
    return 0;
}


Measured memory_bytes: 3616
#include<iostream>
using namespace std;
#define int long long
string a;
int k;
bool f=1;
int ans;
int tot=1;
bool pd()
{
	int k1=1;
	for(int i=1;i<a.length();i++)
	{
		if(a[i]==a[i-1])
			k1++;
	}
	int k2=1;
	for(int i=a.length()-2;i>=0;i--)
		if(a[i]==a[i+1])
			k2++;
	if(k1%2==1&&k2%2==1)
		return 1;
	return 0;
}
signed main()
{
	cin>>a;
	cin>>k;
	for(int i=1;i<a.length();i++)
	{
		if(a[i]!=a[i-1])
			f=0;
	}
	if(f)
	{
		cout<<((k*a.length())>>1);
		return 0;
	}
	int he;
	int ta;
	int j;
	for(int i=0;i<a.length();i=j)
	{
		for(j=i;j<a.length();j++)
		{
			if(a[j]!=a[i])
				break;
		}
		ans+=(j-i)/2;
		if(!i)
			he=j-i;
		if(j==a.length())
			ta=j-i;
	}
	if(he==a.length()&&ta==a.length())
	{
		cout<<k*a.length()/2;
		return 0;
	}
	if(a[0]==a[a.length()-1]&&he/2+ta/2<(he+ta)/2)
		cout<<ans*k+k-1;
	else
		cout<<ans*k;
	return 0;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
a = LI()

x = 0
for i in range(N):
    x = x ^ a[i]
ANS = [0]*N
for i in range(N):
    ANS[i] = a[i] ^ x

print(*ANS)

Measured memory_bytes: 98648
unittest
{
	assert( [ "4 3 6" ].parse.expand.solve == "safe" );
	assert( [ "6 5 1" ].parse.expand.solve == "delicious" );
	assert( [ "3 7 12" ].parse.expand.solve == "dangerous" );
}



import std.conv;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto xab = input.front.split.to!( long[] );
	return tuple( xab[ 0 ], xab[ 1 ], xab[ 2 ] );
}

auto solve( long x, long a, long b )
{
	if( a + x < b ) return "dangerous";
	if( a     < b ) return "safe";
	return "delicious";
}


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

int main(int argc, char const *argv[]) {
  int k;scanf("%d", &k);
  int ans = 0;
  vector<int> num(k+1, 0);
  for(int i=k;i>0;i--){
    int tmp = (k/i);
    tmp = tmp * tmp * tmp;
    num[i] += tmp;
    for(int j=2;j*j<=i;j++){
      if(i%j!=0) continue;
      num[j] -= num[i];
      if(j*j!=i) num[i/j] -= num[i];
    }
    if(i!=1) num[1] -= num[i];
  }
  for(int i=1;i<=k;i++) ans += num[i]*i;
  printf("%d\n", ans);
}



Measured memory_bytes: 3192
#include<bits/stdc++.h>
using namespace std;
int A,B,C,D,num[110]={};

int main(){
  cin >> A >> B >> C >> D;
  for(int i=A;i<B;i++){
    num[i]++;
  }
  for(int i=C;i<D;i++){
    num[i]++;
  }
  int ans=0;
  for(int i=0;i<110;i++){
    if(num[i]==2) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

vector<bool> isVisited;
vector<vector<int>> neighbors;

void dfs(int node, vector<int>& result)
{
    isVisited[node] = true;
    result.push_back(node);

    for (int nxt : neighbors[node]) {
        if (!isVisited[nxt]) {
            dfs(nxt, result);
            break;
        }
    }
}

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

    isVisited.resize(n, false);
    neighbors.resize(n);
    rep(i, m)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        neighbors[a].push_back(b);
        neighbors[b].push_back(a);
    }

    vector<int> p1, p2;
    dfs(0, p1);
    dfs(0, p2);

    cout << p1.size() + p2.size() - 1 << endl;
    rrep(i, p1.size())
    {
        cout << p1[i] + 1 << " ";
    }
    rep(i, p2.size())
    {
        if (i != 0) {
            cout << p2[i] + 1 << " ";
        }
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 9592
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> h.at(i);
	}
	vector<int> max(n);
	max.at(0)=h.at(0);
	int count;
	for (int i = 0; i < n-1; ++i)
	{
		if(max.at(i)>h.at(i+1)){
			max.at(i+1)=max.at(i);
		}
		else{
			max.at(i+1)=h.at(i+1);
			count++;
		}
	}
  cout << count+1 << endl;
}


Measured memory_bytes: 256