akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
	string s,t;
	cin >> s >> t;
	for(int i = s.length() - t.length(); i >= 0; i--){
		int j;
		REP(j,t.length()){
			if(!(s[i + j] == t[j] || s[i + j] == '?')) goto no;
		}
		REP(j,t.length()){
			if(s[i + j] == '?') s[i + j] = t[j];
		}
		REP(j,s.length()){
			if(s[j] == '?') s[j] = 'a';
		}
		cout << s << endl;
		return 0;
		no:;
	}
	cout << "UNRESTORABLE" << endl;
}

Measured memory_bytes: 256
#include<iostream>

const int INF = 1 << 24, MAX_N = 101;
int n, cost[MAX_N][MAX_N], d[MAX_N], used[MAX_N];

int dijkstra(int s, int g){
	for(int i=1;i<=n;i++){
		d[i] = INF;
		used[i] = false;
	}
	d[s] = 0;

	while(true){
		int v = -1;
		for(int i=1;i<=n;i++){
			if(!used[i] && (v == -1 || d[i] < d[v])){
				v = i;
			}
		}

		if(v == -1)break;
		used[v] = 1;

		for(int i=1;i<=n;i++){
			d[i] = std::min(d[i], d[v] + cost[v][i]);
		}
	}

	return d[g];
}

int main(){
	int k;
	while(std::cin >> n >> k, n){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cost[i][j] = INF;
			}
		}

		while(k--){
			int f, c, d, e;
			std::cin >> f;
			if(f == 0){//注文が入りましたよー
				std::cin >> c >> d;
				int res = dijkstra(c, d);
				if(res == INF){
					std::cout << -1 << std::endl;
				}else{
					std::cout << dijkstra(c, d) << std::endl;
				}
			}else{//運行情報
				std::cin >> c >> d >> e;
				cost[c][d] = std::min(cost[c][d], e);
				cost[d][c] = cost[c][d];
			}
		}
	}
}

Measured memory_bytes: 1196
#!/usr/bin/env python3
#CADDi D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
flg = 0
for i in a:
    if i % 2:
        flg = 1
if flg == 0:
    print('second')
else:
    print('first')


Measured memory_bytes: 44252
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <utility>
#include <queue>

using namespace std;

vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};

template<typename T> 
void show(T a){
  for(auto i : a){ cout << i << " "; }
  cout << endl;
}
template<typename T> 
void showmatrix(T a){
  for(auto j: a){for(auto i : j){ cout << i; }cout << endl;}
  cout << endl;
}
template<typename T> 
void showmatrix_new(T a){
  for(auto j: a){for(auto i : j){ if(i == -1)cout << "."; else cout << "#"; }cout << endl;}
  cout << endl;
}

int main(int argc, char *argv[]){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  
  int h, w;
  cin >> h >> w;
  vector< vector<int> > v(h, vector<int>(w, -3));
  for(auto& i : v){
    for(auto& j : i){
      char c ; cin >> c;
      j = c == '.' ? -1 : 0;// white: . black: # 
      //white: -1 black: 0
    }
  }
  
  if(v[0][0] == 0 || v[h-1][w-1] == 0) {cout << -1 << endl; return 0;}
  
  int whitenum = 0;
  int blacknum = 0;
  for(auto& i : v){for(auto& j : i){ if(j== -1) whitenum++; else blacknum++;}};
  
  
  //bfs
  v[0][0] = 0;
  
  queue<pair<int, int>> q;
  q.push({0,0});
  while(!q.empty()){
    pair<int, int> point = q.front();
    q.pop();
    
    int x = point.first;
    int y = point.second;
    for(int i = 0; i < 4; i++){
      int xx = x + dx[i];
      int yy = y + dy[i];
      //cout << "check point " <<x << " " << y << " " <<xx << " " << yy << " queue:" << q.size()<< endl;
      if(xx >= h || yy >= w || xx < 0 || yy < 0) continue;
      if(v[xx][yy] >= 0) continue;
      //showmatrix_new(v);
      q.push({xx, yy});
      v[xx][yy] = 1 + v[x][y];
    }
  }
  
  //cout << "final check point" << endl;
  if(v[h-1][w-1] < 0) {cout << -1 << endl; return 0;}
  
  int step = v[h-1][w-1] + 1;
  int ans = whitenum - step;
  
  cout << ans << endl;

}

Measured memory_bytes: 256
#include<cstdio>

int main(){
  int a,b,c,h,i,j;
  j=0;
  scanf("%d %d %d",&a,&b,&c);
  for(i=a;i<=b;i++){
    h=c%i;
    if(h==0)
      j++;
  }
  printf("%d\n",j);
  return 0;
}

Measured memory_bytes: 1028
Ass = Array.new(3) { gets.split.map(&:to_i) }
N = gets.to_i
bs = Array.new(N) { gets.to_i }

ans_arr = Array.new(3) { Array.new(3){'no'} }

cond = false

bs.each do |bingo|
    Ass.each_with_index do |arr, arr_i|
        arr.each_with_index do |num, num_i|
        ans_arr[arr_i][num_i] = 'yes' if num == bingo
        end
    end
end

ans_arr.each do |arr|
    cond = true if arr.uniq.count == 1 && arr[0] == 'yes'
end

3.times do |index|
    array = [ans_arr[0][index], ans_arr[1][index], ans_arr[2][index]]
    cond = true if array.uniq.count == 1 && array[0] == 'yes'
    
end

array = [ans_arr[0][0], ans_arr[1][1], ans_arr[2][2]]
cond = true if array.uniq.count == 1 && array[0] == 'yes'
array = [ans_arr[0][2], ans_arr[1][1], ans_arr[2][0]]
cond = true if array.uniq.count == 1 && array[0] == 'yes'

puts cond ? 'Yes' : 'No'


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

int main(){
    ll k,n; cin >> k >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    for(ll i=0;i<n;i++){
        cin >> a[i];
        if(a[i] >= k){
            a[i] -= k; 
        }
    }

    sort(a.begin(),a.end());

    ll ans = 0;
    for(ll i=0;i<n-1;i++){
        b[i] = a[i+1]-a[i];
    }
    b[n-1] = k - (a[n-1] - a[0]);

    sort(b.begin(),b.end());
    for(int i=0;i<n-1;i++){
        ans += b[i];
    }
    cout << ans << endl;
}


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

p = []
sz = []

def find(x):
    if(p[x] == x):
        return x
    p[x] = find(p[x])
    return p[x]

def join(u, v):
    u = find(u)
    v = find(v)
    if(u == v):
        return

    if(sz[u] > sz[v]):
        u ^= v
        v ^= u
        u ^= v

    sz[v] += sz[u]
    p[u] = v

for i in range(n+1):
    p.append(i)
    sz.append(1)

for i in range(m):
    a, b = map(int, input().split())
    join(a, b)

mx = 0
for i in range(1, n+1):
    if(p[i] != i):
        continue
    mx = max(mx, sz[i])

print(mx)

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

int main() {
    int N;
    int t[110000], x[110000], y[110000];
    cin >> N;
    t[0] = x[0] = y[0] = 0;  // 初期状態
    for (int i = 0; i < N; ++i) cin >> t[i+1] >> x[i+1] >> y[i+1];  // 1-index にしておく

    bool can = true;
    for (int i = 0; i < N; ++i) {
        int dt = t[i+1] - t[i];
        int dist = abs(x[i+1] - x[i]) + abs(y[i+1] - y[i]);
        if (dt < dist) can = false;
        if (dist % 2 != dt % 2) can = false;  // dist と dt の偶奇は一致する必要あり！
    }

    if (can) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

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

int main() {

    int N;
    cin >> N;

    vector<int> H(N);

    rep(i,N)    cin >> H[i];

    int ans = 0;
    int mx = 0;

    rep(i,N){
        if(H[i] >= mx){
            ans++;
            mx = H[i];
        }
    }
    show(ans);

    return 0;
}


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

int main(){
    int x,y;
    cin>>x>>y;
    bool ok=x*2<=y;
    ok=ok&&(y-x*2)%2==0;
    ok=ok&&(y-x*2)/2<=x;
    cout<<(ok?"Yes":"No")<<endl;
}


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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

typedef long long LL;
typedef pair<int, int> pii;

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
long double eps = 1.0e-14;
#define pow10(n) int(1e##n + n)

struct edge
{
    LL s, t, l;
};

void solve()
{
    LL L;
    cin >> L;

    vector<edge> G;

    int s = 1;
    while ((1LL << s) <= L)
    {
        G.push_back(edge{s, s + 1, 0});
        G.push_back(edge{s, s + 1, 1LL << (s - 1)});
        s++;
    }

    LL p2 = (1LL << (s - 1));
    LL N = s;

    for (int t = N - 1; t > 0; t--)
    {
        if (p2 + (1LL << (t - 1)) <= L)
        {
            L -= (1LL << (t - 1));
            G.push_back(edge{t, N, L});
        }
    }
    cout << N << " " << G.size() << endl;
    for (auto e : G)
    {
        cout << e.s << " " << e.t << " " << e.l << endl;
    }
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}


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

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver2 {
 public:
  int n, m;
  vector<map<int, int>> t;
  Solver2(LL n, LL m) : n(n), m(m), t(n){};

  void solve() {
    for (int i = 0; i < m; ++i) {
      int a, b;
      cin >> a >> b;
      t[--a][--b] = 0;
      t[b][a] = 0;
    }
    bool ans = true;
    int ans2 = 0;
    int cnt6 = 0;
    vector<int> v4;
    for (int i = 0; i < n; ++i) {
      if (t[i].size() % 2) ans = false;
      ans2 += max(0, (int)t[i].size() - 2);
      if (t[i].size() >= 6) cnt6++;
      if (t[i].size() == 4) v4.push_back(i);
    }
    if (ans && ans2 >= 4) {
      if (ans2 >= 6 || cnt6) {
        cout << "Yes" << endl;
      } else {
        cout << (check(v4[0], v4[1]) ? "Yes" : "No") << endl;
      }
    } else {
      cout << "No" << endl;
    }
  }
  bool check(int s, int v) {
    int now = s;
    vector<int> res;
    while (1) {
      if (now == s || now == v) {
        res.push_back(now);
      }
      bool found = false;
      for (auto e : t[now]) {
        if (e.second == 0) {
          t[now][e.first] = 1;
          t[e.first][now] = 1;
          now = e.first;
          found = true;
          break;
        }
      }
      if (!found) break;
    }
    res.pop_back();
    for (int i = 0; i < res.size(); ++i) {
      rotate(res.begin(), res.begin() + 1, res.end());
      if (res[0]==res[1]) return true;
    }
    return false;
  }
};
}  // namespace Problem

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(12);
  long long n = 0, m;
  std::cin >> n >> m;

  Problem::Solver2 sol(n, m);
  sol.solve();
  return 0;
}


Measured memory_bytes: 14336
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int h,a[102],b,c,d[102],n,n1;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	scanf("%d ",&a[i]);
	scanf("%d",&a[n]);
	
	scanf("%d",&n1);
	while(n1--)
	{
		h=0;
		for(int i=1;i<=n;i++)
		d[i]=a[i];
		scanf("%d %d",&b,&c);
		d[b]=c;
		for(int i=1;i<=n;i++)
		h+=d[i];
		printf("%d\n",h);
	}
	return 0;
}

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

using lli = long long int;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

template <class T>ostream &operator<<(ostream &o,const pair<T, T>&p)
{o<<"("<<p.first<<", "<<p.second<<")";return o;}

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

const lli MOD = 1000000007LL;

lli modpow(lli a, lli n){
    lli res = 1;

    for(lli ai = a; n; n>>=1){
        if(1&n) res = (res*ai)%MOD;
        ai=(ai*ai)%MOD;
    }
    return res;
}

lli inv(lli n){
    return modpow(n, MOD-2);
}

lli modperm(lli n, lli k){
    lli res = 1;
    rep(i, k){
        res = (res*(n-i))%MOD;
    }
    return res;
}

lli modcomb(lli n, lli k){
    return (modperm(n, k)*inv(modperm(k, k)))%MOD;
}

lli posmod(lli n){
    lli res = n;
    res %= MOD;
    if(res < 0) res += MOD;
    return res;
}
int a, b, c, d;

int main(void){
    cin >> a >> b >> c >> d;
    int n1 = (c+b-1)/b;
    int n2 = (a+d-1)/d;
    if(n1 <= n2) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) int((x).size())
#define OUT(x) cout << (x) << endl
typedef long long ll;
typedef vector<int> V;
typedef vector<vector<int>> VV;
typedef pair<int, int> P;
typedef map<string, int> M;
typedef unordered_map<int, int> HM;
typedef set<int> S;
typedef queue<int> Q;

int main(){
    int n,k; cin >> n >> k;
    vector<P> vec(n);
    for(int i=0; i<n; i++){
        int t,d; cin >> t >> d;
        vec[i] = P(d,t);
    }
    sort(ALL(vec),greater<P>());
    S s;
    priority_queue<int, V, greater<int>> q;
    ll ans = 0, tmp = 0;
    for(int i=0; i<n; i++){
        int t = vec[i].second, d = vec[i].first;
        if(i < k){
            if(s.find(t) == s.end()) s.insert(t);
            else q.push(d);
            tmp += d;
        }
        else if(s.find(t)==s.end() && !q.empty()){
            s.insert(t);
            tmp += d;
            tmp -= q.top();
            q.pop();
        }
        ll x = ll(s.size());
        ans = max(ans, tmp+x*x);
    }
    OUT(ans);
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
static const bool DEBUG = true;
int main()
{
    ifstream fIn("input.txt");
    if (DEBUG)
    {
        if(fIn.is_open()) cin.rdbuf(fIn.rdbuf());
    }
    int n;
    cin >> n;
    int d[n];
    rep(i,n) cin >> d[i];
    int ans = 0;
    rep(i,n) for(int j = i + 1; j < n; ++j){
        ans += d[i] * d[j];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7


def main():
  N = int(readline())
  A = []
  for i in range(N):
    s, p = input().split()
    p = int(p)
    A.append((s, -p, i+1))
  A.sort()
  for s, p, i in A:
    print(i)
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 3060
def train():
    n=int(input())
    al=[]
    for _ in range(n):
        a=int(input())
        al.append(a)
    id=0
    ans=1
    for _ in range(n):
        if al[id]==2:
            print(ans)
            return
        else:
            id=(al[id])-1
            ans+=1
    print(-1)
train()

Measured memory_bytes: 13052
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<class T>using numr=std::numeric_limits<T>;
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; }
const int INF = 1e9;
const ll LLINF = 1e16;
const int MOD = 1000000007;
const int MOD2 = 998244353;

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int a,b;
    cin >> a >> b;
    for(int i = 0; i < 10000;i++){
        if(i * 8 /100 == a && i * 10/100 == b){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

Measured memory_bytes: 256
package main

import "fmt"

func f(x int) int {
	switch x % 4 {
	case 3:
		return 0
	case 0:
		return x
	case 1:
		return x ^ (x - 1)
	case 2:
		return x ^ (x - 1) ^ (x - 2)
	}
	return 0
}
func main() {
	var A, B int
	_, _ = fmt.Scan(&A, &B)
	fmt.Println(f(A-1) ^ f(B))
}

Measured memory_bytes: 512
import java.util.Scanner;

class Main{
    static Scanner scan=new Scanner(System.in);
    public static void main(String args[]){
        int n=scan.nextInt();
        boolean bool=false;
        int ans;
        for(int i=n;true;i++){
            String s=Integer.toString(i);
            bool=false;
            for(int j=0;j+1<s.length();j++){
                if(s.charAt(j)!=s.charAt(j+1)){
                    bool=true;
                    break;
                }
            }    
            if(!bool){
                ans=i;
                break;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
  long int N;
  cin >> N;
  long int H[100010];
  long int count[100010] = {0};
  for(int i=0;i<N;i++){
    cin >> H[i];
  }
  
  for(int i=0;i<N;i++){
    if(H[i+1] <= H[i]) count[i+1] = count[i] + 1;
  }
  sort(count, count+N, greater<int>());
  cout << count[0] << endl;

  return 0;
}

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

int main(){
	string s;	cin >> s;
  	int count = 0;
  	for(int i = 0; i < 3; i++){
    	if(s.at(i) == 'A'){count++;}
    }
	if(count == 0 || count == 3){cout << "No" << endl;} 
  	else{cout << "Yes" << endl;}
  
 // 		cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define call(var) cout<<#var<<"="<<var<<endl;
#define dup(x,y) (((x)+(y)-1)/(y))
using ll=long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;
const int INTMAX = 2147483647;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;

  int sz;
  vector< Monoid > seg;

  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }

  template< typename C >
  int find_subtree(int a, const C &check, Monoid &M, bool type) {
    while(a < sz) {
      Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
      if(check(nxt)) a = 2 * a + type;
      else M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }


  template< typename C >
  int find_first(int a, const C &check) {
    Monoid L = M1;
    if(a <= 0) {
      if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
      return -1;
    }
    int b = sz;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) {
        Monoid nxt = f(L, seg[a]);
        if(check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }

  template< typename C >
  int find_last(int b, const C &check) {
    Monoid R = M1;
    if(b >= sz) {
      if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
      return -1;
    }
    int a = sz;
    for(b += sz; a < b; a >>= 1, b >>= 1) {
      if(b & 1) {
        Monoid nxt = f(seg[--b], R);
        if(check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};

int main(){
    int n;cin >> n;
    SegmentTree<int> seg(n, [](int a,int b){return __gcd(a,b);}, 0);
    rep(i,n){
        int a;cin >> a;
        seg.set(i,a);
    }
    seg.build();

    int ans = 0;
    rep(i,n){
        if(i==0){
            chmax(ans, seg.query(1, n));
        }else if(i==n-1){
            chmax(ans, seg.query(0, n-1));
        }else{
            chmax(ans, __gcd(seg.query(0,i), seg.query(i+1,n)));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1280
#include<iostream>
using namespace std;
int main(){
    long long n,c,max,min,sum,x;
    c=0;
    max=-1000000;
    min=1000000;
    sum=0;
    cin >> n;
    while(c<n){
        cin >> x;
        c+=1;
        sum+=x;
        if(max<x) max=x;
        if(min>x) min=x;
    }
    cout << min <<" "<<max<<" "<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3108
#include <iostream>
#include <bitset>
#include <vector>

using namespace std;

vector<vector<int>> mem;
vector<int> bs;

int rec(int l, int r) {
  if(mem[l][r] >= 0) return mem[l][r];
  if(l >= r) {
    mem[l][r] = 0;
  } else {
    int d = r - l + 1;
    if(rec(l+1, r-1) == d - 2 && abs(bs[l] - bs[r]) <= 1) {
      mem[l][r] = d;
    } else {
      int ans = 0;
      for(int k = l; k < r; k++) {
        ans = max(ans, rec(l, k) + rec(k+1, r));
      }
      mem[l][r] = ans;
    }
  }
  return mem[l][r];
}

int main(int argc, char *argv[])
{
  for(;;) {
    int m;
    cin >> m;
    if(m == 0) break;
    bs.clear();
    for(int i = 0; i < m; i++) {
      int b;
      cin >> b;
      bs.push_back(b);
    }
    mem = vector<vector<int>>(m, vector<int>(m, -1));
    int ans = rec(0, m-1);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3652
import java.util.Scanner;
public class Main {
  public static void display(int[][] m) {
    for (int i = 0; i < m.length; i++) {
      for (int j = 0; j < m.length; j++) {
        System.out.print(m[i][j]);
        if (j < m.length - 1)
          System.out.print(" ");
      }
      System.out.print("\n");
    }
  }
  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    int[][] m = new int[n][n];
    for (int i = 0; i < n; i++) {
      int u = s.nextInt();
      int k = s.nextInt();
      for (int j = 0; j < k; j++) {
        int neighbor = s.nextInt();
        m[u-1][neighbor-1] = 1;
      }
    }
    s.close();
    display(m);
  }
}



Measured memory_bytes: 34668
#include <iostream>
using namespace std;
int main(){
	int n,ans=0;
	cin >> n;
	int P[n];
  	for(int i = 0;i<n;i++){
    	cin >> P[i];
    }
  	for(int i = 1;i < n-1;i++){
     	 //cout << P[i-1] << P[i] << P[i+1] <<endl;
    	if(P[i-1] < P[i]&&P[i] < P[i+1] || P[i-1] > P[i]&&P[i] > P[i+1]){
         //cout << P[i-1] << P[i] << P[i+1] << endl;
        ans +=1;
          
             
        }
    }
  	cout << ans;
}

Measured memory_bytes: 256
#include<queue>
#include<stack>
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
#include<functional>
#include<deque>
#include<list>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  int i,n,a[20],b[20],c[20];
  cin >> n;
  for(i=0;i<n;i++){
    cin >> a[i];
  }
  int ans=0;
  for(i=0;i<n;i++){
    cin >> b[i];
    ans+=b[i];
  }
  for(i=0;i<n-1;i++){
    cin >> c[i];
  }
  for(i=0;i<n-1;i++){
    if(a[i]+1==a[i+1]){
      ans+=c[a[i]-1];
    }
  }
  cout << ans << endl;
  return 0;
}

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

signed main(void)
{
	long long k, a, b, ans;

	cin >> k >> a >> b;
	k++;
	if (b - a <= 2)
		ans = k;
	else
	{
		ans = a;
		ans += (k - a) / 2 * (b - a) + (k - a) % 2;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, n, k) for (int i = n; i < k; i++)
#define P(p) cout << (p) << endl;
#define sP(p) cout << setprecision(15) << fixed << p << endl;
#define vi vector<int>
#define printv(v)                      \
    for (int i = 0; i < v.size(); i++) \
        P(v[i]);
#define printt(a, b) cout << a << " " << b << endl;
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int MOD = 1e9 + 7;

void solve()
{
    ll n;
    cin >> n;
    map<ll, ll> m;

    vector<ll> v;
    rep(i, n)
    {
        ll a;
        cin >> a;
        v.push_back(a);
        m[a]++;
    }
    ll sum = 0;
    for (auto it = m.begin(); it != m.end(); it++)
    {
        sum += (it->second * (it->second - 1)) / 2;
    }
    rep(i, n)
    {
        ll ans = sum - (m[v[i]] * (m[v[i]] - 1)) / 2 + ((m[v[i]] - 1) * (m[v[i]] - 2)) / 2;
        P(ans);
    }
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 11120
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N = int(input())
    S = [0] * N

    for i in range(N):
        S[i] = input().rstrip()

    def isSame(a):
        for i in range(N):
            for j in range(N):
                if S[(i + a) % N][j] != S[(j + a) % N][i]:
                    return False
        return True

    ans = 0
    for a in range(N):
        if isSame(a):
            ans += N

    print(ans)

sol()

Measured memory_bytes: 41500
from collections import deque

M,K = map(int,input().split())
if K >= 2**M or M==K==1:
    print(-1)
    exit()
if M == 1:
    print(0,0,1,1)
    exit()

ans = deque([K])
for n in range(2**M):
    if n==K: continue
    ans.append(n)
    ans.appendleft(n)
ans.appendleft(K)
print(*ans)

Measured memory_bytes: 15612
from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    dist[i][i] = 0
for i in range(1,N+1):
    for j,d in G[i]:
        dist[i][j] = d
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
dmin = 10**8
for x in permutations(range(R),R):
    d = 0
    for k in range(1,R):
        d += dist[r[x[k]]][r[x[k-1]]]
    dmin = min(dmin,d)
print(dmin)

Measured memory_bytes: 76920
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt();
		int[] a = sc.nextIntArray(n);

		long total = 0;
		for (int i = 0; i < n; i++) {
			total += a[i];
		}

		long ans = 1145141919810l;
		long snuke = 0;
		for (int i = 0; i < n - 1; i++) {
			snuke += a[i];
			ans = Math.min(ans, Math.abs((total - snuke) - snuke));
		}

		out.println(ans);
		out.flush();
	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) return true;
		else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) return false;
		}
		return true;
	}

	private byte readByte() {
		if (hasNextByte()) return buffer[ptr++];
		return -1;
	}

	private boolean isPrintableChar(byte c) {
		return '!' <= c && c <= '~';
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public String next() {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		byte b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public int nextInt() {
		if (!hasNext()) throw new NoSuchElementException();
		int n = 0;
		boolean minus = false;
		byte b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public long nextLong() {
		if (!hasNext()) throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		byte b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}
}

Measured memory_bytes: 23032
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n, m;
    cin >> n >> m;
    VLL x(n), y(m);
    REP(i,0,n) cin >> x[i];
    REP(i,0,m) cin >> y[i];
    sort(all(x));
    sort(all(y));
    VLL dx(n-1), dy(m-1);
    REP(i,0,n-1) dx[i] = x[i+1] - x[i];
    REP(i,0,m-1) dy[i] = y[i+1] - y[i];
    LL sumx = 0;
    --n;
    --m;
    // REP(i,0,n+1) cerr << "x[" << i << "]=" << x[i] << endl;
    // REP(i,0,n) cerr << "dx[" << i << "]=" << dx[i] << endl;
    // REP(i,0,m) cerr << "dy[" << i << "]=" << dy[i] << endl;
    REP(i,0,n) sumx = (sumx + dx[i] * (LL)(n - i) * (LL)(i + 1)) % (LL)1000000007;
    LL sumy = 0;
    REP(i,0,m) sumy = (sumy + dy[i] * (LL)(m - i) * (LL)(i + 1)) % (LL)1000000007;
    LL sum = (sumx * sumy) % (LL)1000000007;
    cout << sum << endl;
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 3328
import java.io.*;
class Main
{
public static void main(String args[])throws IOException
{
BufferedReader input=new BufferedReader(new InputStreamReader(System.in));

String n=input.readLine();
if(n.equals("1 0 0"))System.out.println("Close");
else if(n.equals("0 1 0"))System.out.println("Close");
else if(n.equals("1 1 0"))System.out.println("Open");
else if(n.equals("0 0 1"))System.out.println("Open");
else if(n.equals("0 0 0"))System.out.println("Close");

}
}

Measured memory_bytes: 16868
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h,w,d;
  cin>>h>>w>>d;
  vector<string> vs(h);
  FOR(i,0,h) cin >> vs[i];
  int ans = 0;
  FOR(i,0,h){
    FOR(j,0,w){
      if(j+d-1>=w) break;
      bool ok = true;
      FOR(k,0,d){
        if(vs[i][j+k]=='#') ok = false;
      }
      ans += ok;
    }
  }
  FOR(i,0,h){
    if(i+d-1>=h) break;
    FOR(j,0,w){
      bool ok = true;
      FOR(k,0,d){
        if(vs[i+k][j]=='#') ok = false;
      }
      ans += ok;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3228
N = int(input())

def factorization(num):
    res = []
    n = num
    div_max = int(num ** 0.5)
    for i in range(2, div_max+1):
        if n % i == 0:
            count = 0
            while n % i == 0:
                count += 1
                n //= i
            res.append([i, count])

    if n != 1:
        res.append([n, 1])

    if len(res) == 0:
        res.append([num, 1])

    return res

res = factorization(N)

ans = 0
for i in range(len(res)):

    p, n = res[i]
    if p != 1:
        j = 1
        while n - j >= 0:
            ans += 1
            n -= j
            j += 1

print(ans)

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

using namespace std;

int main(){
    int n,k;

    cin>>n>>k;

    long long x=n/k,y;





    if(k%2==0){
        y=n/k;
        if(n%k>=(k/2)) y++;
    }else{
        y=0;
    }


    cout<<x*x*x+y*y*y<<endl;
}

Measured memory_bytes: 256
F = []
for i in range(5):
    F.append(int(input()))

n = 0
m = 10
for idx, i in enumerate(F):
    if i % 10 == 0:
        continue
    if i % 10 < m:
        m = i % 10
        n = idx

T = F[n]
for idx, i in enumerate(F):
    if idx == n:
        continue
    T += (int(i) + 9) // 10 * 10

print(T)


Measured memory_bytes: 3060
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<numeric>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
long long a[101][8][1001];
long long f(int p,int q,int r){
  int i;
  if(q==-1)
    return p<=r&&r<=100;
  if(a[p][q][r]>=0)
    return a[p][q][r];
  long long sm=0;
  for(i=p;i<=99-q&&(q+2)*i<r;++i)
    sm+=f(i+1,q-1,r-i);
  return a[p][q][r]=sm;
}
int main(){
  memset(a,-1,sizeof(a));
  int p,q;
  while(cin>>p>>q,p||q)
    cout<<f(0,p-2,q)<<endl;
  return 0;
}

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

char S[10], A[10], D[3][10];
bool F[10];

bool dfs(int pos, bool &flag, const int N) {
  if (pos == N) {
    if (flag) {
      strncpy(D[2], S, N);
      return true;
    }
    if (!strcmp(S, A)) flag = true;
    strncpy(D[0], D[1], N);
    strncpy(D[1], S, N);
  } else {
    for (int i = 0; i < N; ++i) {
      if (F[i]) continue;
      S[pos] = (i + 1) + '0';
      F[i] = true;
      bool ret = dfs(pos + 1, flag, N);
      if (ret) return true;
      F[i] = false;
    }
  }
  return false;
}

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

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

  bool flag = false;
  dfs(0, flag, N);

  for (int i = 0; i < 3; ++i) {
    if (!strlen(D[i])) continue;
    for (int j = 0; j < N; ++j) {
      if (j > 0) cout << ' ';
      cout << D[i][j];
    }
    cout << endl;
  }

  return 0;
}



Measured memory_bytes: 3112
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, 0, n) cin >> a[i];
  sort(a.rbegin(), a.rend());

  int alice = 0, bob = 0;
  rep(i, 0, n) {
    if (i & 1)
      bob += a[i];
    else
      alice += a[i];
  }
  cout << alice - bob << endl;
}


Measured memory_bytes: 256
#include <iostream>

static int MAX = 100000;

int main()
{
  int a[MAX];     //aiが選ばれるとi番目のボタンが光る
  int N;          //ボタンの数
  int b=1;          //現在光っているボタン
  int j=0;          //カウント変数

  std::cin >> N;
  for(int  i=1;i<=N;++i){
    std::cin >> a[i];
  }
  do{
    if(j==N){
      std::cout << -1 << '\n';
      return (0);
    }
    b = a[b];
    ++j;
  }while(b!=2);
  std::cout << j << '\n';

  return (0);
}


Measured memory_bytes: 640
if __name__ == '__main__':
    N = int(input())

    answer = -1
    for i in range(N, 1000):
        i_str = str(i)
        if i_str[0] == i_str[1] and i_str[1] == i_str[2]:
            answer = i_str
            break
    print(i_str)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdlib.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> T;
typedef pair<long double , ll> Ps;
typedef pair<ll, bool> Pb;

const ll INF = 1e18;
const ll fact_table = 3200008;
long double Pi = 3.1415926535897932384626;

priority_queue <ll> pql;
priority_queue <P> pqp;
priority_queue <P> bag;
//big priority queue
priority_queue <ll, vector<ll>, greater<ll> > pqls;
priority_queue <P, vector<P>, greater<P> > pqps;
//small priority queue
//top pop

ll dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
ll dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};
char dir[] = "DRUL";
//↓,→,↑,←

/*
#define endl "\n"
#ifdef ENJAPMA
#undef endl
#endif
*/
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)();
#define pc(x) cout << x << ",";
#define rep(i, n) for (ll i = 0; i < (n); i ++)

const ll mod = 998244353ll;
// const ll mod = 1000000007ll;

ll mypow(ll a, ll b, ll mod) {ll x = 1; while (b) {while (!(b & 1)) {(a *= a) %= mod; b >>= 1;}(x *= a) %= mod; b--;} return x;}
void YES(bool cond) { if (cond) { p("YES");} else { p("NO");} return;}
void Yes(bool cond) { if (cond) { p("Yes");} else { p("No");} return;}
void line() { p("--------------------"); return;}

/*
ll fact[fact_table + 5],rfact[fact_table + 5];

void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = mypow(fact[fact_table],mod - 2, mod);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
*/

bool multicase = false;

ll n, m, k, num, a, b, c, d, e, h, q, ans, sum;

typedef vector<ll> vec;
typedef vector<vector<ll>> mat;

ll x[500005], y[500005];

string s, t;

void solve() {
    cin >> n;
    p(n + n * n + n * n * n);
    return;
}

int main() {
    // init();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll q, testcase = 1;
    if (multicase) {
        cin >> q;
    } else {
        q = 1;
    }
    while (q--) {
        // pu("Case ");pu("#");pu(testcase);pu(": ");
        solve();
        testcase++;
    }
    // solve();
    return 0;
}



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

long int a(long int x){
    long int n=1;
    for(long int i=x;i>x-2;--i){
        n *= i;
    }
    return n/2;
}

int main()
{
    int n;
    cin >> n;
    string s[n];
    for(int i=0;i<n;++i){
        cin >> s[i];
        sort(s[i].begin(),s[i].end());
    }
    sort(s,s+n);
    long int count=0;
    for(int i=0;i<n;++i){
        long int c=0;
        for(int j=i;j<n;++j){
            if(s[i]==s[j]) ++c;
            else break;
        }
        count += a(c);
        i += c-1;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
  int n,x,i,count=0,bit=0;
  cin >> n >> x;
  vector<int> s(n);
  for(i=0;i<n;i++)
  {
    cin >> s[i];
  }
  for(i=0;i<n;i++)
  {
    x -= s[i];
    count++;
  }
  sort(s.begin(),s.end());
  while (x >= s[0])
  {
    x -= s[0];
    count++;
  }
  
  cout << count;
  return 0;
}

Measured memory_bytes: 3620
ROOT = 3
MOD = 998244353
roots  = [pow(ROOT,(MOD-1)>>i,MOD) for i in range(24)] # 1 の 2^i 乗根
iroots = [pow(x,MOD-2,MOD) for x in roots] # 1 の 2^i 乗根の逆元

def untt(a,n):
    for i in range(n):
        m = 1<<(n-i-1)
        for s in range(1<<i):
            w_N = 1
            s *= m*2
            for p in range(m):
                a[s+p], a[s+p+m] = (a[s+p]+a[s+p+m])%MOD, (a[s+p]-a[s+p+m])*w_N%MOD
                w_N = w_N*roots[n-i]%MOD

def iuntt(a,n):
    for i in range(n):
        m = 1<<i
        for s in range(1<<(n-i-1)):
            w_N = 1
            s *= m*2
            for p in range(m):
                a[s+p], a[s+p+m] = (a[s+p]+a[s+p+m]*w_N)%MOD, (a[s+p]-a[s+p+m]*w_N)%MOD
                w_N = w_N*iroots[i+1]%MOD
            
    inv = pow((MOD+1)//2,n,MOD)
    for i in range(1<<n):
        a[i] = a[i]*inv%MOD

def convolution(a,b):
    la = len(a)
    lb = len(b)
    deg = la+lb-2
    n = deg.bit_length()
    if min(la, lb) <= 50:
        if la < lb:
            la,lb = lb,la
            a,b = b,a
        res = [0]*(la+lb-1)
        for i in range(la):
            for j in range(lb):
                res[i+j] += a[i]*b[j]
                res[i+j] %= MOD
        return res

    N = 1<<n
    a += [0]*(N-len(a))
    b += [0]*(N-len(b))
    untt(a,n)
    untt(b,n)
    for i in range(N):
      a[i] = a[i]*b[i]%MOD
    iuntt(a,n)
    return a[:deg+1]

def convolution_all(polys):
    if not polys: return [1]
    polys.sort(key=lambda x:len(x))
    N = len(polys)
    height = (N-1).bit_length()
    N0 = 1<<(height)
    data = [None]*(N0*2)
    data[N0:N0+N] = polys
    data[N0+N:] = [[1] for _ in range(N0-N)]
    
    #print(data)
    #print(polys)
    for k in range(N0-1,0,-1):
        data[k] = convolution(data[2*k], data[2*k+1])        

    return data[1]

SIZE=10**5 + 10 #998244353 #ここを変更する

inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    fac[i] = fac[i-1]*i%MOD
finv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(SIZE-1,0,-1):
    finv[i-1] = finv[i]*i%MOD
    inv[i] = finv[i]*fac[i-1]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

dfac = [0]*SIZE  # fac[j] = j! mod MOD
dfac[0] = dfac[1] = 1
for i in range(2,SIZE):
    dfac[i] = dfac[i-2]*i%MOD

import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*h = map(int, read().split())
from collections import Counter

def get(k): # k 個の頂点からiペア作れる場合の数
    res = [1]
    for i in range(k//2):
        res.append(res[-1]*choose(k-2*i,2)%MOD)
    for i in range(2,k//2 + 1):
        res[i] = res[i]*finv[i]%MOD
    return res        


d = Counter(h)
res = []
for k,v in d.items():
    if v >= 2: res.append(get(v))
    if v > n: 
        print(0)
        exit()
    
bad = convolution_all(res)

#print(bad)
#bad = [1,5,7,3]
ans = 0
sgn = 1
for i,ai in enumerate(bad):
    ans += sgn*(dfac[2*n-2*i-1] if i < n else 1)*ai  
    ans %= MOD
    sgn *= -1
    #print(ans)

print(ans%MOD)

Measured memory_bytes: 105904
#include<stdio.h>
int main(void){
    int a;
    int c=0;
    scanf("%d",&a);
    int b[a];
    for(int i=0;i<a;i++){
        scanf("%d",&b[i]);
    }
    //scanf("%d",&b);
    for(int j=0;j<a;j++){
        for(int k=j+1;k<a;k++){
            c=c+b[j]*b[k];
        }
    }
    printf("%d",c);

    return 0;
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Text;

class Program
{
	static void Main(string[] args)
	{
		string[] input = Read();
		int n = int.Parse(input[0]);
		Write(n%1000==0 ? 0 : 1000 - n%1000);
	}

	static string[] Read()
	{
		return Console.ReadLine().Split(' ');
	}

	static void Write(object o)
	{
		Console.WriteLine(o.ToString());
	}
}



Measured memory_bytes: 27520
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,K;
bool vis[11];
bool check(int x) {
    while(x) {
	if(vis[x % 10]) return false;
	x /= 10;
    }
    return true;
}

void Solve() {
    read(N);read(K);
    int d;
    for(int i = 1 ; i <= K ; ++i) {
	read(d);vis[d] = 1;
    }
    for(int i = N ; ; ++i) {
	if(check(i)) {out(i);enter;return;}
    }
}

int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	
	string s;
	cin>>s;
	int flag=0;
	for(int i=0;i<s.length();i++){
		for(int j=0;j<s.length()-i;j++){
			string s1 = s;
			s1.erase(i,j);
			if(s1=="keyence"){
				flag=1;
				break;	
			}
		}
	}
	if(flag) cout<<"YES\n";
	else cout<<"NO\n";
  
}


Measured memory_bytes: 256
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#define inf  1000000000
#define mod  1e9+1
#pragma GCC optimization ("O3")
using namespace std;
const long long int N = 6999999;
#define all(x) begin(x),end(x)
int main()
{
   
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  deque<char>s;
  int f = 0,q;
  string s1;
  cin >> s1;
  for (int i = 0; i < s1.size(); ++i)
  {
    s.push_back(s1[i]);
  }
  cin >> q;
  while(q--)
  {
    int t,t1;
    char c;
    cin >> t;
    if(t == 1){
      if(f==0)
        f = 1;
      else
        f = 0;
    }
    else
    {
      cin >> t1 >> c;
      if(f ==1){
        if(t1 == 1){
          s.push_back(c);
        }
        else
          s.push_front(c);
      }
      else{
         if(t1 == 1){
          s.push_front(c);
        }
        else
          s.push_back(c);
      }
    }
  }
  if (f == 1)
  {
    for (auto it = s.rbegin(); it != s.rend(); ++it) 
      cout << *it; 
  }
  else
  {
    for (auto it = s.begin(); it != s.end(); ++it) 
      cout << *it;
  }
	return 0;
}	

Measured memory_bytes: 896
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
long long n,m,q,i,j,dp[1<<18][18],l,r,x,y,ans,now,wx[100005];
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	for (i=1;i<=n;i++) cin>>wx[i];
	cin>>m;
	for (i=1;i<=n;i++)
	{
		while (j<n&&wx[i]+m>=wx[j+1]) j++;
		dp[i][0]=j;
	}
	for (j=1;j<=17;j++)
	{
		for (i=1;i<=n;i++)
		{
			dp[i][j]=dp[dp[i][j-1]][j-1];
		}
	}
	cin>>q;
	for (i=1;i<=q;i++)
	{
		cin>>l>>r;
		if (l>r) swap(l,r);
		ans=0;
		for (j=17;j>=0;j--)
		{
			while (dp[l][j]<r)
			{
				l=dp[l][j];
				ans+=1<<j;
			}
		}
		cout<<ans+1<<endl;
	}
	return 0;
}

Measured memory_bytes: 17280