akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define INF (1e9)
typedef pair<int, int> pii;
const int MAX_N = (1<<18);

struct RMQ {
    int n;
    pii dat[MAX_N];
    void init(int n_)
    {
        n = 1;
        while (n < n_) {
            n *= 2;
        }
        for (int i = 0; i < 2*n-1; i++) {
            dat[i] = pii(-INF, -INF);
        }

        for (int i = 0; i < n_; i++) {
            update(i, 0);
        }
    }

    void update(int k, int a)
    {
        int nk = k;
        k += n - 1;
        dat[k] = pii(a, -nk);
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = max(dat[k*2+1], dat[k*2+2]);
        }
    }

    pii query(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l) return pii(-INF, -INF);
        if (a <= l && r <= b) {
            return dat[k];
        } else {
            pii vl = query(a, b, k*2+1, l, (l + r) / 2);
            pii vr = query(a, b, k*2+2, (l + r) / 2, r);
            return max(vl, vr);
        }
    }    
};

int main()
{
    int N, R, L;
    cin >> N >> R >> L;
    int d, t, x, pt = 0;
    int point[MAX_N] = {};
    RMQ r;
    r.init(N);
    for (int i = 0; i < R; i++) {
        cin >> d >> t >> x; d--;
        point[-r.query(0, N, 0, 0, r.n).second] += t - pt;
        r.update(d, x + r.dat[d + r.n - 1].first);
        pt = t;
    }
    point[-r.query(0, N, 0, 0, r.n).second] += L - pt;
    int mx = 0, num = -1;
    for (int i = 0; i < N; i++) {
        if (mx < point[i]) {
            mx = point[i];
            num = i+1;
        }
    }
    cout << num << endl;
    return 0;
}

Measured memory_bytes: 6208
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://beta.atcoder.jp/contests/abc045/tasks/arc061_a

int main() {
    string S; cin >> S;
    int len = S.length();

    ll ans = 0;
    for (int mas = 0; mas < 1 << (len-1); mas++) {
        ll num = S[0] - '0';

        for (int i = 0; i < len-1; i++) {
            if (mas & 1 << i) {
                ans += num;
                num = 0;
            }

            num = num * 10 + (S[i+1] - '0');
        }

        ans += num;
    }

    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
using namespace std;
using ll = long long;

int main(){
        ll i,dmod=1,mod=0,ans=0;
        string S;
        cin >> S;
        vector<ll> m(2019); ++m.at(0);
        for(i=0;i<S.length();++i){
                if(i>0) dmod = (dmod*10)%2019;
                mod = ((ll)(S[S.length()-1-i]-'0')*dmod+mod)%2019;
                ++m.at(mod);
        }
        for(i=0;i<2019;++i){
                if(m.at(i)>1) ans += m.at(i)*(m.at(i)-1)/2;
        }
        cout << ans << endl;
        return 0;
}

Measured memory_bytes: 3712
s = int(input())
a = [s]
flg = False


def even(n):
    return n / 2


def odd(n):
    return 3 * n + 1


for i in range(1000001):
    if a[i] % 2 == 0:
        a.append(a[i] / 2)
    else:
        a.append(3 * a[i] + 1)

for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] == a[j]:
            print(j + 1)
            flg = True
            break
    if flg == True:
        break


Measured memory_bytes: 91116
// Example program
#include<bits/stdc++.h>
using namespace std;
void changeString(string &temp,string s,int x){
 if(x)
  temp=s+"s";
  else
  temp = s+"es";
}
int main()
{
    string s,temp;
    cin>>s;
    int n=s.length();
    if(s[n-1]=='s')
     changeString(temp,s,0);
    else 
     changeString(temp,s,1);
    cout<<temp; 
}


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

typedef long long                   ll;
typedef long double                 ld;
typedef pair<ll,ll>                 pll;
typedef pair<ld,ld>                 pld;


#define all(x)          (x).begin(),(x).end()
#define Sort(x)         sort(all(x))
#define sep             ' '

#define endl            '\n'
#define tab             '\t'
#define X               first
#define Y               second
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define set_random      mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 1e9 + 7,
         MAXN= 1e6+10,
         INF=1e18;
ll x,a;
int main()
{
    fast_io;
    cin>>x>>a;
    if(x<a)cout<<0;
    else cout<<10;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define test ll t; t=1; while(t--)
typedef long long int ll;
int main() {
    FIO;
    test{
        ll n,wt,i,j;
        cin>>n>>wt;
        ll w[n],v[n];
        for(i=0;i<n;i++){
            cin>>w[i]>>v[i];
        }
        ll dp[100001][2];
        memset(dp,0,sizeof(dp));
        dp[0][1]=1;
        for(i=0;i<n;i++){
            for(j=100000;j>=0;j--){
                if(dp[j][1]==1){
                    if(dp[j][0]+w[i]<=wt ){
                        if(dp[j+v[i]][1]==1){
                        dp[j+v[i]][0]=min(dp[j+v[i]][0],dp[j][0]+w[i]);
                        }
                        else{
                        dp[j+v[i]][1]=1;
                        dp[j+v[i]][0]=dp[j][0]+w[i];
                       }
                }
            }
        }
        }
        i=100000;
        while(dp[i][1]!=1){
            i--;
        }
        cout<<i<<endl;
    }
	return 0;
}


Measured memory_bytes: 1792
import sys
#DEBUG = True
DEBUG = False
if DEBUG:
    f=open("202007_1st/B_input.txt")
else:
    f=sys.stdin
N=int(f.readline())
V=[f.readline().strip() for _ in range(N)]
R=[0,0,0,0]
for _ in range(N):
    if V[_]=='AC':
        R[0]+=1
    elif V[_]=='WA':
        R[1]+=1
    elif V[_]=='TLE':
        R[2]+=1
    elif V[_]=='RE':
        R[3]+=1
    else:
        pass
print("AC x {0}".format(R[0]))
print("WA x {0}".format(R[1]))
print("TLE x {0}".format(R[2]))
print("RE x {0}".format(R[3]))
f.close()

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

int main() {
	int n,k;
	cin >> n >> k;
	vector<int> a(n);
	rep(i,n){
		cin >> a[i];
	}
	sort(a.begin(), a.end(),greater<int>());
	int sum = 0;
	rep(i,k) {
		sum += a[i];
	}
	cout << sum << endl;
}



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

int N, K;
int x[100000], y[100000];
long long tiles[4000][4000];


int main(){
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        char c;
        cin >> x[i] >> y[i] >> c;
        if(c == 'W'){
            x[i] += K;
        }
        x[i] %= 2*K;
        y[i] %= 2*K;
    }


    for(int i = 0; i < N; i++){
        tiles[x[i]][y[i]] += 1;
        tiles[x[i]+K][y[i]] -= 1;
        tiles[x[i]][y[i]+K] -= 1;
        tiles[x[i]+K][y[i]+K] += 2;
        tiles[x[i]+K][y[i]+2*K] -= 1;
        tiles[x[i]+2*K][y[i]+K] -= 1;
        tiles[x[i]+2*K][y[i]+2*K] += 1;
    }

    /*
    for(int i = 0; i < 4*K; i++){
        for(int j = 0; j < 4*K; j++){
            printf("%02lld ", tiles[i][j]);
        }
        puts("");
    }
    puts("");
    */
    for(int j = 0; j < 4*K; j++){
        for(int i = 1; i < 4*K; i++){
            tiles[i][j] += tiles[i-1][j];
        }
    }
    for(int i = 0; i < 4*K; i++){
        for(int j = 1; j < 4*K; j++){
            tiles[i][j] += tiles[i][j-1];
        }
    }

    for(int i = 0; i < 2*K; i++){
        for(int j = 2*K; j < 4*K; j++){
            tiles[i][j-2*K] += tiles[i][j];
        }
    }
    for(int i = 2*K; i < 4*K; i++){
        for(int j = 0; j < 2*K; j++){
            tiles[i - 2*K][j] += tiles[i][j];
        }
    }
    for(int i = 2*K; i < 4*K; i++){
        for(int j = 2*K; j < 4*K; j++){
            tiles[i - 2*K][j - 2*K] += tiles[i][j];
        }
    }
    long long ans = 0;
    for(int i = 0; i < 2*K; i++){
        for(int j = 0; j < 2*K; j++){
            //printf("%lld ", tiles[i][j]);
            ans = max(ans, tiles[i][j]);
        }
        //puts("");
    }
    cout << ans << endl;
}

Measured memory_bytes: 126080
import numpy as np


k, q = map(int, input().split())
d = np.array(list(map(int, input().split())), dtype=np.int64)
queries = [tuple(map(int, input().split())) for _ in range(q)]

for n, x, m in queries:
    d_mod = d % m
    rem_d_mod = d_mod[: (n - 1) % k]
    print(n - 1 - (x % m + ((n - 1) // k) * np.sum(d_mod) + np.sum(rem_d_mod)) // m
          - ((n - 1) // k) * np.count_nonzero(d_mod == 0) - np.count_nonzero(rem_d_mod == 0))


Measured memory_bytes: 21788
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long X;
  cin >> X;
  
  long money = 100;
  int year = 0;
     
  while (money < X)
  {
    money += money / 100;
    year++;
  }
  
  cout << year << endl;
  
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i< (int)(b); ++i)
using namespace std;
const int mod=1e9+7;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a,b,c,ans; cin >> a >> b >> c;
    if(a==b) ans=c;
    if(b==c) ans=a;
    if(c==a) ans=b;
    cout << ans << endl;
 }    


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin>>n;
	string ans="";
        map<ll,char> m;
        m[0]='z';
        char c='a';
        for(int i=1;i<26;i++)
        {
            m[i]=c;
            c++;
        }
        while(n!=0)
        {
            int y=n%26;
            ans=m[y]+ans;
            if(y!=0)
            {
                n=n/26;
            }
            else
            {
                n=n/26;
                n--;
            }
        }
        cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 3660
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())

    for i in range(26):
        for j in range(15):
            if N == 4 * i + 7 * j:
                print('Yes')
                exit()
    print('No')

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
n = int(input())
a = list(map(int, input().split()))
r = []
c = 0
for j in range(n):
  if j % 2 == 1:
    c -= a[j]
  else:
    c += a[j]
r.append(c)
for i in range(n-1):
  r.append((a[i] - r[i] // 2) * 2)
print(*r)

Measured memory_bytes: 14092
numbers = gets.chomp
n1 = numbers.split()[0].to_i
n2 = numbers.split()[1].to_i
#p n1
#p n2
if n1 == n2
  puts n1 + n2
elsif n1 > n2
  puts 2*n1-1
else
  puts 2*n2-1
end

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

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define long long long
typedef pair < long , long > pii;

class BCommonRaccoonVsMonster {
public:
	void solve(std::istream& in, std::ostream& out) {
	    long x,y;
	    in>>x>>y;
	    long ans =0;
	    long f;
	    while (y--){
	        in>>f;
	        ans+=f;
	    }
	    if(ans<x) out<<"No\n";
	    else out<<"Yes\n";

	}
};


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


Measured memory_bytes: 256
#include <cstdio>
int main(){
	int a,b,c,sq=0,di=0;
	while(scanf("%d,%d,%d",&a,&b,&c)!=EOF){
		if(a*a+b*b==c*c)sq++;
		else if(a==b)di++;
	}
	printf("%d\n%d\n",sq,di);
	return 0;
}

Measured memory_bytes: 0
/*g++ main.cpp -o main.out*/
/*./main.out*/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

int main()
{
    LL n,a,b;
    cin>>n>>a>>b;
    LL ans=a*(n/(a+b));
    LL r=n%(a+b);
    ans+=(r>a)?a:r;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
from heapq import heappop, heappush, heapify

class Graph():  #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.deg[e[1] - indexed] += 1

    def dijkstra(self, s, INF=10**18, restore_to=None):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    heappush(heap, (dist[adj], adj))
        if restore_to is not None:
            g = restore_to
            if dist[g] == INF:
                return dist, False
            path = [g]
            node = g
            while node != s:
                node = prev[node]
                path.append(node)
            return dist, path[::-1]
        return dist

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
E = list()

for _ in range(M):
    l, r, c = map(int, input().split())
    E.append((l - 1, r - 1, c))

for i in range(N - 1):
    E.append((i + 1, i, 0))

g = Graph(N, E, 0)
res = g.dijkstra(0)[N - 1]

print(res if res != 10**18 else -1)

Measured memory_bytes: 97960
#include <vector>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <functional>

const int INF = 1001001000;
const int MOD = (int)1e9 + 7;

using ll = long long;

using namespace std;

typedef pair<int,int> P;

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

int main(){
  int n,a,b;
  int ans = 0;
  int sum;
  int tmp;

  cin >> n >> a >> b;

  for( int i = 1; i <= n; ++i){
    tmp = i;
    sum = 0;
    while(tmp){
      sum += tmp%10;
      tmp /= 10;
    }
    if( a <= sum && sum <= b){
      ans += i;
    }
  }

  cout << ans << endl;

}


Measured memory_bytes: 256
x=0
y=0
n=int(input())
F=list(input())

alist=[]
alist.append(x)
for token in F:



    if token=="I":
        x=x+1
        if x>y:
            y=x
    else:
        x=x-1
        alist.append(x)





print(y)

Measured memory_bytes: 2940
n, k = map(int,input().split())

# グラフ構築に必要な辺の本数は、最低n-1本
# 少なくとのn-1組の頂点対は距離1である
# 全頂点対の組み合わせの数 n*(n-1)/2 から n-1を引いたものが、作成可能な頂点対個数の最大値

if k > (n-1)*(n-2)/2:
    ans = -1
    print(ans)

# 頂点対の数が、(n-1)*(n-2)/2以下であるとき、n頂点からなるスターを考える
# ref. https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%BC_(%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96)
# n頂点スターにおける、距離2の頂点対の組み合わせは(n-1)*(n-2)/2である
# スターの頂点以外の、ある2頂点をつなぐと、組み合わせは1つ減る
# (n-1)*(n-2)/2 - k 辺を用いて、頂点間を結ぶと、k個の距離2である頂点対が完成する
else:
    # 1を含まない(n-1)*(n-2)/2個の頂点対を用意しておく
    Cand = []
    for i in range(2, n):
        for j in range(i+1, n+1):
            Cand.append([str(i),str(j)])
    Ans = []
    for i in range(2,n+1):
        Ans.append([str(1),str(i)])
    for i in range(int((n-1)*(n-2)/2)-k):
        Ans.append(Cand[i])
    
    print(len(Ans))
    for i in range(len(Ans)):
        print(' '.join(Ans[i]))

Measured memory_bytes: 4356
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i = 0; i < (n); i++)
typedef long long ll;
// Welcome to my source code!

int main() {
    int n;
    cin >> n;
    int i = 1;
    for (; i*i <= n; i++);
    cout << (i-1)*(i-1) << endl;
}

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



int main(){
	int num;
	string ss;
	cin>>num;
	for(int z=0;z<num;z++){
		cin>>ss;
		int cnt=ss.size();
		int dt[cnt];
		for(int i=0;i<cnt;i++){
			dt[i]=ss[i]-'0';
		}
		sort(dt,dt+cnt);
		long long max=0,min=0;
		for(int i=0;i<cnt;i++){
			max+=dt[i]*pow(10,i);
			min+=dt[cnt-(i+1)]*pow(10,i);
		}
		cout<<max-min<<endl;
	}
	return 0;
}

Measured memory_bytes: 1260
#include <stdio.h>
int F[100];

Fibo(int n){
  if(n == 0 || n == 1){
    return F[n]=1;
  }
  if(F[n] != -1){
    return F[n];
  }
  return F[n] = Fibo(n-2)+Fibo(n-1);
}

int main(){
  int i,n;
for(i=0; i<100; i++){
    F[i] = -1;
  }

  scanf("%d",&n);
  printf("%d\n",Fibo(n));

  return 0;
}

Measured memory_bytes: 596
(let*
  ((h(read))
  (w(read))
  (s(loop for i from 1 to h collect(read-line)))
  (dx'(0 1 0 -1 1 1 -1 -1))
  (dy'(1 0 -1 0 1 -1 1 -1)))
  (dotimes(i h)
    (dotimes(j w)
      (format t"~A"
        (if(char=(char(nth i s)j)#\.)
          (princ-to-string
            (loop for r from 0 to 7 count
              (let((tx(+(nth r dx)i))(ty(+(nth r dy)j)))
                (and(>= tx 0)(>= ty 0)(< tx h)(< ty w)
                  (char=(char(nth tx s)ty)#\#)))))
           "#")))
    (format t"~%")))

Measured memory_bytes: 11104
import java.util.*;
import java.io.*;
public class Main {
    static InputStreamReader r;
    public static void main(String[] args) throws Exception {
        r = new InputStreamReader(System.in);
        int N = nextInt();
        int[] h = new int[N+5];
        for (int i = 1; i <= N; i++) {
            h[i] = nextInt();
        }

        int[] DP = new int[N+5];
        Arrays.fill(DP, Integer.MAX_VALUE);
        for (int i = 1; i <= N; i++) {
            if (i == 1) {
                DP[i+1] = Math.abs(h[i+1] - h[i]);
                DP[i+2] = Math.abs(h[i+2] - h[i]);
                continue;
            }
            DP[i+1] = Math.min(DP[i+1], DP[i] + Math.abs(h[i+1] - h[i]));
            DP[i+2] = Math.min(DP[i+2], DP[i] + Math.abs(h[i+2] - h[i]));
        }

        System.out.println(DP[N]);
    }

    public static String nextString() throws Exception {
        String res = "";
        while (true) {
            int c = r.read();
            if (c == 32 || c == 10 || c == -1) {
                break;
            }
            res += (char)c;
        }
        return res;
    }

    public static int nextInt() throws Exception {
        return Integer.parseInt(nextString());
    }

    public static long nextLong() throws Exception {
        return Long.parseLong(nextString());
    }
}

Measured memory_bytes: 44192
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int sz = 1e6+5;

int nk, csub[sz], trie[26][sz], dp[26][sz];

int fnc(int ch, int u) {
   int &w = dp[ch][u];
   if(w < 0) {
      w = 0;
      for(int i=0; i<26; i++) {
         int v = trie[i][u];
         if(v < 0) continue;
         if(i == ch) w += csub[v];
         else w += fnc(ch, v);
      }
   }
   return w;
}

void tsc(int x) {
   for(int i=0; i<26; i++) {
      int y = trie[i][x];
      if(y < 0) continue;
      tsc(y);
      csub[x] += csub[y];
   }
}

int main() {
   ios_base::sync_with_stdio(0); cin.tie(0);
   memset(dp, -1, sizeof(dp));
   memset(trie, -1, sizeof(trie));

   int n;
   cin >> n;
   vector <pair<int,int>> qs;
   for(int i=0; i<n; i++) {
      string s;
      cin >> s;
      reverse(s.begin(), s.end());
      int b = 0, p;
      for(char x : s) {
         int j = x - 'a';
         p = b;
         if(trie[j][b] >= 0) b = trie[j][b];
         else {
            trie[j][b] = ++nk;
            b = nk;
         }
      }
      csub[b]++;
      qs.emplace_back(s.back() - 'a', p);
   }

   tsc(0);

   ll ans = 0;
   for(auto p : qs) ans += fnc(p.first, p.second);

   cout << ans - n << endl;
}


Measured memory_bytes: 286560
N = int(input())
S = []
for i in range(N):
    S.append(list(map(int, input().split())))
tn = 0
xn = 0
yn = 0
isOk=True
for sl in S:
    ti = sl[0]
    xi = sl[1]
    yi = sl[2]
    t = ti-tn
    distance = abs(xi-xn)+abs(yi-yn)
    if (t>=distance)&((t-distance)%2==0):
        pass
    else:
        isOk=False
        break
if isOk:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 60376
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(ll i = (a); i < (b); i++)
#define FORR(i, a, b) for(ll i = (a); i >= (b); i--)
#define REP(i, n) for(ll i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* exchange */
#define CHMIN(a, b) (a) = min((ll)(a), (ll)(b))
#define CHMAX(a, b) (a) = max((ll)(a), (ll)(b))

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll X = 0;
ll ret = 0;
string s;
ll MAX_ARR = 1000;

int main(void){
  IN(X);

  vl arr(MAX_ARR);
  REP(i, MAX_ARR) {
    arr[i] = i*i*i*i*i;
  }

  REP(i, MAX_ARR) {
    ll A5 = arr[i];
    ll tar1 = A5 - X;
    ll tar2 = X - A5;
    ll tar3 = A5 + X;
    // DEBUG(A5);
    // DEBUG(tar1);
    // DEBUG(tar2);
    // DEBUG(tar3);
    // LN();

    if (tar1 >= 0) {
      auto itr1 = lower_bound(ALL(arr), tar1);
      if (*itr1 == tar1) {
        cout << i << " " << distance(arr.begin(), itr1);
        break;
      }
    }

    
    if (tar2 >= 0) {
      auto itr2 = lower_bound(ALL(arr), tar2);
      if (*itr2 == tar2) {
        cout << i << " " << -distance(arr.begin(), itr2);
        break;
      }
    }

    
    if (tar3 >= 0) {
      auto itr3 = lower_bound(ALL(arr), tar3);
      if (*itr3 == tar3) {
        cout << -i << " " << -distance(arr.begin(), itr3);
        break;
      }
    }
  }
  cout << endl;
}


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

int main()
{
    int m,n,sum = 0;
    cin >> n >> m;
    int a[1000];
    for( int i = 0; i < n; i++ )
    {
        cin >> a[i];
        sum = sum + a[i];
    }
    
    int ans = 0;
    for( int i = 0; i < n; i++ )
    {
        if( double(a[i]) < double(double(sum) / double((4*m))) ){
            continue;
        }
        ans++;
    }

    if( ans >= m ){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}


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

int main(){
  ll N, K;
  cin >> N >> K;

  int max = 100001;
  
  vector<ll> tmp(max, 0);
  for (int i = 0; i < N; i++){
    ll a, b;
    cin >> a >> b;
    tmp.at(a) += b;
  }
  
  ll count = 0;
  for (int ans = 1; ans < max; ans++) {
    count += tmp[ans];
    if (count >= K) {
      cout << ans << endl;
      break;
    }
  }
  
  return 0;
}


Measured memory_bytes: 4004
#include "bits/stdc++.h"
using namespace std;
int main()
{
	long long x, y;
	scanf("%lld %lld", &x, &y);
	if(x % y)
	{
		for(long long i = 1; ; ++i)
		{
			if(x * i % y)
			{
				printf("%lld\n", x * i);
				break;
			}
		}
	}
	else
	{
		printf("-1\n");
	}
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(c-(a-b)>=0){
        cout << c - (a - b) << endl;
    }else{
        cout << 0 << endl;
    }
    return 0;
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

char a, b;

int main() {
	cin >> a >> b;
	
	cout << (a == b ? "H" : "D") << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin >> s;
	int fg1=0,fg2=0;
	for(int i=0;i<3;i++){
		if(s[i]=='A')
		fg1=1;
		else
		fg2=1;
	}
	if(fg1&&fg2) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
} 

Measured memory_bytes: 256
N = int(input())
sticks = list(map(int, input().split()))
sticksSum = sum(sticks)
diffMin = sum(sticks)
plusSticks = 0
for i in range(len(sticks)):
    plusSticks += sticks[i]
    diffMin = min(diffMin, abs(2*plusSticks-sticksSum))
print(diffMin)


Measured memory_bytes: 26764
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

S = input()
ans = S.count('R')
if ans == 0:
    exit(0)

if S[1] == 'S':
    ans = 1
print(ans)


Measured memory_bytes: 67892
#include<iostream>
#include<cmath>
#include<cstdio>

int main(){
  int a,pre_d=90,d;
  double x=0,y=0;

  while(1){
    scanf(" %d,%d",&a,&d);
    if(a==0&&d==0) break;
    //std::cout << (double)a << (double)d <<std::endl;
    x += (double)a*cos((double)pre_d*M_PI/180);
    y += (double)a*sin((double)pre_d*M_PI/180);
    pre_d += -d;
  }
  //std::cout << (double)a << std::endl;
  printf("%d\n%d\n",(int)x,(int)y);

}

Measured memory_bytes: 3408
def main():
    A, B, K = (int(i) for i in input().split())
    ans = []
    for i in range(1, 101):
        if A % i == 0 and B % i == 0:
            ans.append(i)
    ans.sort(reverse=True)
    print(ans[K-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
N, D = map(int, input().split())
 
# 前から最適に配置せよ
# 一人目は, 1,...,D, D+1, D+2,...,2D+1 を監視
# 二人目は, 2D+2,..., 3D+2, ...,4D+2 を監視
# x人まで繰り返すと、1,...,x(2D+1)まで監視できる
 
# x(2D+1) > N を満たす最小のxは？
# x_min = ceil(N/(2D+1))
 
print(-(-N//(2*D+1)))

Measured memory_bytes: 9144
m=int(input())
d,c=[],[]
ans=-1
for i in range(m):
  dd,cc=map(int,input().split())
  d.append(dd)
  c.append(cc)
  ans+=cc
a=0
for i in range(m):
  a+=d[i]*c[i]
  dd=(a-1)//9
  ans+=dd
  a-=dd*9
print(ans)

Measured memory_bytes: 71768
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int LG = 60;
struct Bazis {
  
int a[LG];

Bazis() {
    memset(a, 0, sizeof a);
}

void add(int x) {
    for (int i = LG - 1; i >= 0; --i) {
        if ((x >> i) & 1) {
            if (!a[i]) {
                a[i] = x;
                break;
            }   
            x ^= a[i];
        }
    }   
}   
bool check(int x) {
    for (int i = LG - 1; i >= 0; --i) {
        if ((x >> i) & 1) {
            if (!a[i]) {
                return 0;
                break;
            }   
            x ^= a[i];
        }
    }   
    return x == 0;
}   

};  

void solve() {
    int n;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) 
        cin >> a[i];
    string s;
    cin >> s;

    Bazis b;
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == '0') {
            b.add(a[i]);
        }   
        if (s[i] == '1') {
            if (!b.check(a[i])) {
                cout << 1 << endl;
                return;
            }   
        }
    }   
    cout << 0 << endl;
}

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int t;
    cin >> t;
    while (t--) 
        solve();
}

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

using namespace std;

int main()
{
    int n, g1=0, g2=0;
    long long S=0;
    cin >> n;
    int a[n];
    vector <int> A, B;
    vector <pair<int,int>> V;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] > 0)
        {
            g1 = 1;
            A.push_back(a[i]);
            S += a[i];
        }
        else
        {
            g2 = 1;
            B.push_back(a[i]*-1);
            S -= a[i];
        }
    }
    if (g1 == 1 && g2 == 1)
    {
        cout << S << "\n";
        int s1 = A[0], s2=-1*B[0];
        for (int i = 1; i < B.size(); i++)
        {
            V.push_back({s1, -1*B[i]});
            s1 -= -1*B[i];
        }
        for (int i = 1; i < A.size(); i++)
        {
            V.push_back({s2, A[i]});
            s2 -= A[i];
        }
        V.push_back({s1, s2});
        for (int i = 0; i < V.size(); i++)
        {
            cout << V[i].first << " " << V[i].second << "\n";
        }
        return 0;
    }
    if (n == 1)
    {
        cout << a[0];
        return 0;
    }
    if (n == 2)
    {
        if (a[1] - a[0] > a[0] - a[1])
        {
            cout << a[1] - a[0] << "\n";
            cout << a[1] << " " << a[0];
        }
        else
        {
            cout << a[0] - a[1] << "\n";
            cout << a[0] << " " << a[1];
        }
        return 0;
    }
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    int s;
    if (g1 == 1)
    {
        S -= A[0];
        S -= A[1];
        S += A[1] - A[0];
        s = A[0];
        V.push_back({A[0], A[1]});
        s -= A[1];
        for (int i = 2; i < n-1; i++)
        {
            V.push_back({s, A[i]});
            s -= A[i];
        }
        V.push_back({A[n-1], s});
    }
    else
    {
        S -= B[0];
        S -= B[1];
        S += B[1] - B[0];
        s = B[0]*-1;
        V.push_back({s, -1*B[1]});
        s -= -1*B[1];
        for (int i = 2; i < n-1; i++)
        {
            V.push_back({s, -1*B[i]});
            s -= -1*B[i];
        }
        V.push_back({s, -1*B[n-1]});
    }
    cout << S << "\n";
    for (int i = 0; i < V.size(); i++)
    {
        cout << V[i].first << " " << V[i].second << "\n";
    }
    return 0;
}


Measured memory_bytes: 3828
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>       // for next_permutation
#include <vector>
#include <cstdlib>
#define INF 998244353

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pi;

const ll MOD = 1e9+7;

static long gcd(long a, long b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
/*
long long int facctorialMethod(int k){//階乗
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}*/

long long int tousasum(long long int n){//等差数列
    return n*(n+1)/2;
}

unsigned GetDigit(unsigned num){//桁数
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

bool is_prime(const unsigned n){
    switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: // fall-through
        case 3: return true;
    } // n > 3 が保証された

    if(n%2 == 0) return false;
    if(n%3 == 0) return false;
    // 2と3の倍数でないので6の倍数ではないことが保証された

    if(n%6 != 1 && n%6 != 5) return false;
    // 6の倍数前後の数(素数かもしれない数)であることが保証された

    // 6の倍数前後の数を使って試し割りをする
    for(unsigned i=5;i*i<=n;i+=6){
        if(n%i     == 0) return false; // 6n-1
        if(n%(i+2) == 0) return false; // 6n+1
    }

    return true;
}

map< ll, ll > prime_factor(ll n) {//素因数分解
    map< ll, ll > ret;
    for(ll i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1) ret[n] = 1;
    return ret;
}

ll calcNumOfCombination(ll n, ll r){
    ll num = 1;
    for(ll i = 1; i <= r; i++){
        num = num * (n - i + 1) / i;
    }
    return num;
}

int bubblesort(vector<int> array,int size){//バブルソート　転倒数
    int kaisu = 0;
    for(int i = 0; i < size; i++){
        for(int j = i + 1; j < size; j++){
            if(array[i] > array[j]){
                int number = array[i];
                array[i] = array[j];
                array[j] = number;
                kaisu++;
            }
        }
    }
    return kaisu;
}

ll facctorialMethod(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum = (sum * i)%MOD;
    }
    return sum;
}

// nPnの順列に対して処理を実行する
void foreach_permutation(int n, std::function<void(int *)> f) {
    int indexes[n];
    for (int i = 0; i < n; i++) indexes[i] = i;
    do {
        f(indexes);
    } while (std::next_permutation(indexes, indexes + n));
}





int main() {
 int N,M;
 cin >> N >> M;
 if(N==M){
     cout << "Yes" << endl;
 }else{
     cout << "No" << endl;
 }
}













Measured memory_bytes: 256
#define dbg(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#define dpri(x) dbg(#x ": %d\n", x)
#define dprs(x) dbg(#x ": %s\n", x)
#include <stdio.h>
typedef long long ll;
const int MYINF = 1e9+7;

static int A[128];
int N, swap_count;

void swap(int *a, int *b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
	swap_count++;
}

void bubble_sort() {
	int i, j;
	for (i = 0; i < N; i++) {
		for (j = N - 1; j > i; j--) {
			if (A[j] < A[j-1]) swap(A+j, A+j-1);
		}
	}
}

int main(int argc, char **argv)
{
	int i;
	const char *sp = "";
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	bubble_sort();
	for (i = 0; i < N; i++) {
		printf("%s%d", sp, A[i]);
		sp = " ";
	}
	putchar('\n');
	printf("%d\n", swap_count);
	return 0;
}

Measured memory_bytes: 604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
//const ll mod = 1000000007;
ll N, T;
ll M[1005], L[1005], K[1005];

bool f(ll border) {
    ll op = border;
    ll clear = 0;
    vector<ll> mpop(2020);
    vector<bool> cleared(N);
    for(int t = 0; t <= T; t++) {
        clear += mpop[t];
        op += mpop[t];
        int idx = -1;
        while(op and idx < N) {
            idx++;
            if(idx == N) break;
            if(cleared[idx]) continue;
            //cerr << t << " " << op << " " << idx << endl;
            ll timer = t % (L[idx] + K[idx]);
            if(timer > L[idx]) continue;
            mpop[t+M[idx]]++;
            op--;
            cleared[idx] = true;
        }
    }
    return clear == N;
}

void solve() {
    for(int i = 0; i < N; i++) {
        cin >> M[i] >> L[i] >> K[i];
    }
    for(int i = 1; i <= N; i++) {
        if(f(i)) {
            cout << i << endl;
            return;
        }
    }
}

int main() {
    while(cin >> N >> T) {
        if(N == 0) break;
        solve();
    }
    return 0;
}


Measured memory_bytes: 3112
#include"bits/stdc++.h"
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,m,n) for(int i=m;i<(n);i++)
#define ALL(x) x.begin(),x.end()
#define ll long long


string lhs[15], rhs;
bool notzero[26];
int c2id[26];
char id2c[26];
ll pow_10[11];
ll l_val[26];
ll r_val[26];
void init() {
	REP(i, 26) {
		notzero[i] = false;
		l_val[i] = 0;
		r_val[i] = 0;
		c2id[i] = 0;

	}
}
void dfs_left(int t, ll res, int K, map<ll, int>&pattern, const vector<int>&l_used) {
	if (t == K) {
		pattern[res]++;
		return;
	}
	int id = l_used[t];
	if (!notzero[id])dfs_left(t + 1, res, K, pattern, l_used);
	FOR(num, 1, 10) {
		dfs_left(t + 1, res + l_val[id] * num, K, pattern, l_used);
	}
}

void dfs_right(int t, ll res, int K, int &ans, map<ll, int>&pattern, const vector<int>&r_used) {
	if (t == K) {
		//cout << res << endl;
		ans += pattern[res];
		return;
	}
	int id = r_used[t];
	if (!notzero[id])dfs_right(t + 1, res, K, ans, pattern, r_used);
	FOR(num, 1, 10) {
		ll tmp = res;
		tmp -= l_val[id] * num;
		tmp += r_val[id] * num;
		dfs_right(t + 1, tmp, K, ans, pattern, r_used);
	}
}

void solve() {
	int N; cin >> N;
	if (N == 0)exit(0);
	vector<int>keta[9];
	init();
	set<char>st;
	REP(i, N - 1) {
		cin >> lhs[i];
		for (auto c : lhs[i])st.insert(c);
	}
	cin >> rhs;
	for (auto c : rhs)st.insert(c);
	int id = 0;
	for (auto c : st) {
		int num = c - 'A';
		c2id[num] = id;
		id2c[id] = c;
		id++;
	}
	REP(i, N - 1) {
		if (lhs[i].size() == 1)continue;
		int id = c2id[lhs[i][0] - 'A'];
		notzero[id] = true;
	}
	if(rhs.size()>1)
	notzero[c2id[rhs[0] - 'A']] = true;

	int M = st.size();
	vector<bool>r_used(M);
	for (auto c : rhs) {
		int num = c - 'A';
		r_used[c2id[num]] = true;
	}
	vector<int>l_used;
	REP(i, M) {
		if (!r_used[i])l_used.push_back(i);
	}

	//init l_val
	REP(i, N - 1) {
		int l = lhs[i].size();
		REP(j, lhs[i].size()) {
			int id = c2id[lhs[i][j] - 'A'];
			l_val[id] += pow_10[l - j - 1];
		}
	}
	REP(j, rhs.size()) {
		int id = c2id[rhs[j] - 'A'];
		r_val[id] += pow_10[(int)rhs.size() - j - 1];
	}

	int K = l_used.size();
	map<ll, int>pattern;
	vector<int>r_used_id;
	REP(i, M) {
		if (r_used[i])r_used_id.push_back(i);
	}
	int ans = 0;
	//dfs_left(0, 0, K, pattern,l_used);
	//for (auto x : pattern) {
	//	cout << x.first << " " << x.second << endl;
	//}
	//cout << "M:" << M << " K:" << K << endl;
	//dfs_right(0, 0, M - K,ans,pattern,r_used_id);


	int perm[10];
	REP(i, 10)perm[i] = i;
	//set<ll>vis;
	do {
		ll rval = 0;
		ll lval = 0;
		REP(i, 10) {
			if (perm[i] == 0 && notzero[i])goto END;
		}

		REP(i, 10) {
			int num = perm[i];
			rval += r_val[i] * num;
			lval += l_val[i] * num;
		}
		if (rval == lval) {
			ans++;
			//cout << rval << endl;
			//vis.insert(rval);
		}
	END:;
	} while (next_permutation(perm, perm + 10));
	int divi = 1;
	FOR(i, 1, 10-M+1)divi *= i;
	ans /= divi;
	cout << ans << endl;

}
signed main() {
	ll tmp = 1;
	REP(i, 10) {
		pow_10[i] = tmp;
		tmp *= 10;
	}
	while (true) {
		solve();
	}
}


Measured memory_bytes: 3092
N = int(input()) 
A = list(map(int, input().split()))

biggest = 0
humidai = 0

result = 0

tmp_list = []

tmp=sum(A)

for i in range(N-1):

    # for j in range(i+1,N):
        # tmp += A[j]
    tmp -= A[i]
    
    result += A[i]*tmp

    if result>10**9+7:
        result = result%(10**9+7)

result = result%(10**9+7)

print(result)

Measured memory_bytes: 31428
import java.awt.Frame;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import javax.sql.rowset.FilteredRowSet;
import javax.swing.BorderFactory;
import javax.xml.parsers.DocumentBuilder;
import javax.xml.stream.events.EndDocument;
import java.math.BigInteger;
import java.time.chrono.MinguoChronology;
import java.util.Scanner;

public class Main {
  static InputReader in;
  static PrintWriter out;
  
  static class Solution {
    void solve() throws IOException {
      while (true) {        
        String firstorder = in.next();
        String order = firstorder;
        if (firstorder.equals("-")) {
          break;
        }
        int n = firstorder.length();
        int m = in.nextInt();
        int h[] = new int[m];
        for (int i = 0; i < m; i++) {
          h[i] = in.nextInt();
        }
        
        for (int i = 0; i < m; i++) {          
          order = order.substring(h[i], n) + order.substring(0, h[i]);
        }
        
        out.println(order);
      }
      
      
      
      
//      End solve()
    }
    
//  End solution
  } 
  

  public static void main(String[] args) throws IOException {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out);
    Solution solver = new Solution();
    solver.solve();
    out.close();
}

  static class InputReader {
    public BufferedReader br;
    public StringTokenizer st;
    
    public InputReader(InputStream stream) {
      br = new BufferedReader(new InputStreamReader(stream));
    }
   
    public int nextInt() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return Integer.parseInt(st.nextToken());
    }
    
    public long nextLong() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return Long.parseLong(st.nextToken()); 
    }
    
    public String next() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return st.nextToken();
    }
    
    public double nextDouble() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return Double.parseDouble(st.nextToken());
    }
    
  }
  
}

Measured memory_bytes: 24564
#include<stdio.h>
#include<math.h>
typedef struct {
  double x, y;
} Point;
void print(Point e){ printf("%.8f %.8f\n", e.x, e.y); }
void plot(int n, Point p1, Point p2){
  Point a, t, u;
  double th = 60.0*(acos(-1)/180.0);
  if ( n == 0 ) return;
  a.x = (2.0 * p1.x + 1.0 * p2.x)/3.0;
  a.y = (2.0 * p1.y + 1.0 * p2.y)/3.0;
  t.x = (1.0 * p1.x + 2.0 * p2.x)/3.0;
  t.y = (1.0 * p1.y + 2.0 * p2.y)/3.0;
  u.x = (t.x - a.x) * cos(th) - (t.y - a.y ) * sin(th) + a.x;
  u.y = (t.x - a.x) * sin(th) + (t.y - a.y ) * cos(th) + a.y;  
  plot(n-1, p1, a);
  print(a);
  plot(n-1, a, u);
  print(u);
  plot(n-1, u, t);
  print(t);
  plot(n-1, t, p2);
}
int main(){
  Point p1, p2;
  int n;
  scanf("%d", &n);
  p1.x = 0;
  p1.y = 0;
  p2.x = 100;
  p2.y = 0;
  print(p1);
  plot(n, p1, p2);
  print(p2);
  return 0;
}





Measured memory_bytes: 2132
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<int> fact;
vector<int> ifact;
vector<int> inv;
vector<int> pow2;
const int MOD = 998244353;
int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
int choose(int a, int b)
{
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
	return modpow(a,MOD-2);
}
void init(int _n)
{
	fact.clear(); ifact.clear(); inv.clear(); pow2.clear();
	fact.resize(_n+1);
	ifact.resize(_n+1);
	inv.resize(_n+1);
	pow2.resize(_n+1);
	pow2[0]=1;
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=_n;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		fact[i]=mult(fact[i-1],i);
		//ifact[i]=mult(ifact[i-1],inv[i]);
	}
	ifact[_n] = inverse(fact[_n]);
	for(int i=_n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
	for(int i=1;i<=_n;i++)
	{
		inv[i] = mult(fact[i-1],ifact[i]);
	}
}

vi solve(vi a, vi b)
{
	int n=a.size();
	if(n==1)
	{
		if(a[0]==0) return {0};
		else return {mult(b[0],inverse(a[0]))};
	}
	vi a1,a2,b1,b2;
	for(int i=0;i<n;i+=2)
	{
		a1.pb(add(a[i],a[i+1]));
		b1.pb(add(b[i],b[i+1]));
		a2.pb(add(a[i],MOD-a[i+1]));
		b2.pb(add(b[i],MOD-b[i+1]));
	}
	vi c1 = solve(a1,b1);
	vi c2 = solve(a2,b2);
	vi x(n);
	for(int i=0;i<n/2;i++)
	{
		x[i*2]=add(c1[i],c2[i]);
		x[i*2+1]=add(c1[i],MOD-c2[i]);
		x[i*2]=mult(x[i*2],inv[2]);
		x[i*2+1]=mult(x[i*2+1],inv[2]);
	}
	return x;
}
	
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	int N = (1<<n);
	init(355555);
	vi a(N); int s=0;
	for(int i=0;i<N;i++)
	{
		cin>>a[i];s+=a[i];
	}
	int iS=inverse(s);
	for(int i=0;i<N;i++)
	{
		a[i]=mult(a[i],iS);
	}
	a[0]=add(a[0],MOD-1);
	vi nw;
	for(int i=0;i<N;i++)
	{
		if(i==0) nw.pb(N-1);
		else nw.pb(MOD-1);
	}
	vi c = solve(a,nw);
	int ss = c[0];
	for(int i=0;i<N;i++)
	{
		c[i]=add(c[i],MOD-ss);
		cout<<c[i]<<'\n';
	}
}	


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

int main()
{
  int n;
  int d[100100];
  int h[100100];
  cin >> n;
  for (int i = 1; i <= n; ++i)
  {
    cin >> h[i];
  }

  d[1] = 0;
  d[2] = abs(h[2] - h[1]);
  for (int i = 3; i <= n; ++i)
  {
    auto cost1 = abs(h[i] - h[i - 1]) + d[i - 1];
    auto cost2 = abs(h[i] - h[i - 2]) + d[i - 2];
    d[i] = min(cost1, cost2);
  }
  cout << d[n] << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
typedef int64_t llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define ld PRId64

int main(){
    string s;
    cin >> s;
    cout << s[0] << s.length() -2 << s[s.length() -1 ] << endl;
}




Measured memory_bytes: 256