akhauriyash/Code-Regression huggingface dataset:
import queue

INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2

def dijkstra(n, adj):
    pq = queue.PriorityQueue()
    d = [INFTY] * n
    color = [WHITE] * n

    d[0] = 0
    pq.put((0, 0))
    color[0] == GRAY

    while not pq.empty():
        f = pq.get()
        u = f[1]
        color[u] = BLACK

        if d[u] < f[0]:
            continue

        for j in range(len(adj[u])):
            v = adj[u][j][0]
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + adj[u][j][1]:
                d[v] = d[u] + adj[u][j][1]
                pq.put((d[v], v))
                color[v] = GRAY

    for i in range(n):
        out = d[i]
        if out == INFTY:
            out = -1
        print('{0} {1}'.format(i, out))


n = int(input())
adj = [[] for i in range(n)]
for i in range(n):
    line = [int(v) for v in input().split()]
    u = line[0]
    k = line[1]
    for j in range(k):
        v = line[2*j + 2]
        c = line[2*j + 3]
        adj[u].append((v, c))

dijkstra(n, adj)


Measured memory_bytes: 70296
using System;
using System.Linq;

namespace AtCoder
{
    class B_Shiftonly_081
    {
        public static void Main()
        {
            var length = int.Parse(Console.ReadLine());
            var inputs = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var count = 0;
            while (true)
            {
                var flg = false;
                var tmp = inputs;
                for (var i = 0; i < length; ++i)
                {
                    if (tmp[i] % 2 == 0) { tmp[i] /= 2; }
                    else { flg = true; break; }
                }

                if (flg) { break; }

                inputs = tmp;
                ++count;
            }

            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  int answer = 0;
  bool zero = false;
  cin >> n;
  vector<int> h(n,0);
  for(int i = 0;i < n;i++) cin >> h[i];
  for(int i = 0;i < 101;i++){
    if(h[0] != 0) answer++;
    for(int j = 0;j < n-1;j++){
      if(h[j] == 0 && h[j+1] != 0) answer++;
      if(h[j] != 0) h[j]-= 1;
    }
    if(h[n-1] != 0) h[n-1]-= 1;
  }
  cout << answer << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(i, x.size()) cerr << x[i] << (i == x.size() - 1 ? "\n" : " ")
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

//=============================
int N,M,K;
string S,T;
//=============================
void input()
{
    cin>>N>>M;
}
//=============================
void func(){}
//=============================
void solve()
{
    cout<<(N-1)*(M-1)<<endl;
}
//=============================
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 256
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
int n,k;
int p[N],q[N],p_[N],q_[N],A[N];
void inv(int p_[],int p[]){
	static int r[N];
	for (int i=1;i<=n;++i)
		r[p[i]]=i;
	memcpy(p_,r,sizeof(int)*(n+1));
}
void multi(int f[],int p[],int q[]){
	static int r[N];
	for (int i=1;i<=n;++i)
		r[i]=p[q[i]];
	memcpy(f,r,sizeof(int)*(n+1));
}
void getpow(int p[],int k){
	static int vis[N],r[N],q[N];
	memset(vis,0,sizeof(int)*(n+1));
	for (int i=1;i<=n;++i)
		if (!vis[i]){
			int cnt=0;
			for (int x=i;!vis[x];x=p[x])
				vis[x]=1,q[cnt++]=x;
			for (int j=0;j<cnt;++j)
				r[q[j]]=q[(j+k)%cnt];
		}
	memcpy(p,r,sizeof(int)*(n+1));
}
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;++i)
		scanf("%d",&p[i]);
	for (int i=1;i<=n;++i)
		scanf("%d",&q[i]);
	inv(p_,p),inv(q_,q);
	memcpy(A,q,sizeof(int)*(n+1));	
	multi(A,A,p_),multi(A,A,q_),multi(A,A,p);
	int r=(k-1)%6;
	for (int i=0;i<r;++i){
		inv(p,p);
		multi(p,q,p);
		swap(p,q);
	}
	getpow(A,(k-1)/6);
	multi(p,A,p);
	inv(A,A);
	multi(p,p,A);
	for (int i=1;i<=n;++i)
		printf("%d ",p[i]);
	return 0;
}















Measured memory_bytes: 5536
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define LIMIT(d_in, d_min, d_max) max(d_min, min(d_max, d_in))
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	int N;
	cin >> N;
	if (N == 1)
		cout << "Hello World" << endl;
	else
	{
		int a, b;
		cin >> a >> b;
		cout << a + b << endl;
	}
	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 256
def not_in_D(N, D):
    for i in range(100000):
        N_list = list(str(N+i))
        N_list = [int(n) for n in N_list]
        can = True
        for n in N_list:
            if n in D:
                can = False
        if can == True:
            print(N + i)
            break
def main():
    N ,K = map(int, input().split())
    D = list(map(int, input().split()))
    not_in_D(N, D)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
//ITNOA
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <iomanip>

using namespace std;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;


#define rep(i, s, e) for(int i = s; i < e; i ++)
#define int long long
#define X first
#define Y second

typedef long long ll;
typedef long double ld;

const int maxN = 200*1000 + 5;
const int mod = 1000*1000*1000 + 7;
const int base = 701;
const int SQ = 500;
const int maxL = 20;

vector<int> a[maxN];
int32_t main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	for(int i = 0; i < m; i ++) {
		int u, v; cin >> v >> u;
		v --; u --;
		a[v].push_back(u);
		a[u].push_back(v);
	}	

	for(int i = 1; i < n-1; i++) {
		bool f1 = 0, fn = 0;
		for(int j = 0; j < a[i].size(); j ++) {
			if(a[i][j] == 0)
				f1 = true;
			if(a[i][j] == n-1)
				fn = true;	
		}
		if(f1 && fn) {
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}

	cout << "IMPOSSIBLE" << endl;
	return 0;
}


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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int H, W; scanf("%d %d", &H, &W);
  int N; scanf("%d", &N);
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &A[i]);
  }

  vector<vector<int>> grid(H, vector<int>(W, -1));
  int r = 0, c = 0, dir = 1, color = 1;
  for (int i = 0; i < N; ++i) {
    while (A[i]-- > 0) {
      grid[r][c] = color;
      c += dir;
      if (c == W) {
        dir = -1;
        c = W - 1;
        ++r;
      }
      else if (c == -1) {
        dir = 1;
        c = 0;
        ++r;
      }
    }
    ++color;
  }

  for (int i = 0; i < H; ++i) {
    printf("%d", grid[i][0]);
    for (int j = 1; j < W; ++j) {
      printf(" %d", grid[i][j]);
    }
    printf("\n");
  }
  return 0;
}


Measured memory_bytes: 384
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, D;
    cin >> N >> D;
    vector<vector<ll>> X(N, vector<ll>(D));
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < D; j++) {
            cin >> X[i][j];
        }
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = i + 1; j < N; j++) {
            ll sum = 0;
            for (ll k = 0; k < D; k++) {
                sum += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
            }

            for (ll k = 0; k * k <= sum; k++) {
                if (k * k == sum) {
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long int ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
const int MOD=1000000007;

bool isPowerOfTwo (ll x)  
{  
    return x && (!(x&(x-1)));  
}
bool isPrime(int n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
}
int highestPowerof2(unsigned int n) 
{ 
    // Invalid input 
    if (n < 1) 
        return 0; 
  
    int res = 1;
    for (int i=0; i<8*sizeof(unsigned int); i++) 
    { 
        int curr = 1 << i; 
        if (curr > n) 
           break; 
  
        res = curr; 
    } 
  
    return res; 
} 
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}       
////////////////////////////////////////////////////////////////////
const int NMMAX=50;
int A[NMMAX],B[NMMAX],C[NMMAX],D[NMMAX];
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);  
  cout.tie(NULL);
  ll t=1;
  while(t--)
  {
    int n,m;
    cin>>n>>m;
    REP(i,n){
        cin>>A[i];cin>>B[i];
    }
    REP(i,m)
    {
        cin>>C[i]>>D[i];
    }
    REP(i,n)
    {
        int mn=abs(A[i]-C[0])+abs(B[i]-D[0]),ch=1;
        for(int j=1;j<m;j++)
        {
            int cur=abs(A[i]-C[j])+abs(B[i]-D[j]);
            if(cur<mn){
                ch=j+1;
                mn=cur;
            }
        }
        cout<<ch<<"\n";
    }
  }  
  return 0;
}

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

int main(){

  int A, B, K;
  cin >> A >> B >> K;

  int cnt = 0; //今まで見つかった数
  for (int i = min(A, B); i >= 1; i--){
    if (A % i == 0 && B % i ==0){
      cnt++;  //cntを1増やす
      if (cnt == K){
        cout << i << endl;
        return 0;
      }
    }
  }
}

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

int main(){
    int n; cin>>n;
    int bin = 1;
    while(n != 0){
        n /= 2;
        bin *= 2;
    }
    cout << bin/2 << endl;
}

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

int N, M;
vector<vector<int>> A;

void dfs (vector<int> v, int d) {
  if (d == N) {
    A.push_back(v);
    return;
  }
  int mx = (v.size()) ? *max_element(v.begin(), v.end()) : 1;
  for (int i = mx; i <= M; i++) {
    vector<int> nv = v;
    nv.push_back(i);
    dfs(nv, d + 1);
  }
}

int main() {
  cin >> N >> M;
  vector<int> start;
  dfs(start, 0);

  int Q;
  cin >> Q;
  vector<vector<int>> V(Q, vector<int>(4));
  for (int i = 0; i < Q; i++) {
    for (int j = 0; j < 4; j++) {
      cin >> V.at(i).at(j);
    }
  }

  int ans = 0;
  for (auto a : A) {
    int sum = 0;
    for (auto v : V) {
      if (a.at(v.at(1) - 1) - a.at(v.at(0) - 1) == v.at(2)) {
        sum += v.at(3);
      }
    } 
    ans = max(ans, sum);
  }
  cout << ans << "\n";
}

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

typedef long long ll;

int main()
{
	ll n, a, b; cin >> n >> a >> b;
	if (a > b) cout << 0 << endl;
	else if (n == 1)
	{
		if (a == b) cout << 1 << endl;
		else cout << 0 << endl;
	} else
		cout << ((n-2)*(b-a)+1) << endl;
	return 0;
}


Measured memory_bytes: 256
///apigs property
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define F first
#define S second
#define pb push_back
#define vll vector< ll >
#define vi vector< int >
#define pll pair< ll , ll >
#define pi pair< int , int >
#define all(s) s.begin() , s.end()
#define sz(s) s.size()
using namespace std;
typedef long long ll;
ll q, dp[3005][3005], a[555555] , b[555555], k, l, m, n, o, p;
map < ll , ll > mp;
vll adj[555555];
const ll mod = 1e9+7;
string s , t;
int main() {
    fast , cin >> s >> t;
    n = sz(s) , m = sz(t);
    s = ' ' + s;
    t = ' ' + t;
    for(ll i = 1 ; i <= n ; i++){
    	for(ll j = 1 ; j <= m ; j++){
    		if(s[i] == t[j]){
    			dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]); 
			}
		}
	}
	string ss;
	while(n >= 1 && m >= 1){
		if(s[n] == t[m]){
			ss.pb(s[n]);
			n-- , m--;
		}
		else{
			if(dp[n - 1][m] > dp[n][m - 1])n--;
			else m--;
		}
	}
	reverse(all(ss));
	cout << ss;
}


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

int main()
{
	for (int i = 0; i < 3; i++){
		int hin, min, sin, hout, mout, sout, ht, mt, st, total;
		cin >> hin >> min >> sin;
		cin >> hout >> mout >> sout;

		total = hout * 3600 + mout * 60 + sout - hin * 3600 - min * 60 - sin;

		ht = total / 3600;
		mt = (total - ht * 3600) / 60;
		st = total % 60;

		cout << ht << " " << mt << " " << st << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
(function main() {
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());
  const MAX = 1000;

  let i, j, X, Y, xlen, ylen, maxlen;
  const c = Array.from(Array(MAX + 1), () => []);
  while ((X = lines.shift()) && (Y = lines.shift())) {
    xlen = X.length;
    ylen = Y.length;
    for (i = 0; i <= xlen; i++) c[i][0] = 0;
    for (j = 0; j <= ylen; j++) c[0][j] = 0;

    for (i = 1; i <= xlen; i++) {
      for (j = 1; j <= ylen; j++) {
        if (X[i-1] === Y[j-1]) c[i][j] = c[i - 1][j - 1] + 1;
        else c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
      }
    }
    console.log(c[xlen][ylen]);
  }
})();



Measured memory_bytes: 35936
#include<iostream>
using namespace std;
int main(){
	int n ,x=0 ,max=0;
	scanf("%d",&n);
	char s[n];
	for(int i=0 ;i<n;){
	 cin>>s[i];
	 if(s[i]=='I') {
	 	++x;
	 	++i;
	 	
	 }
	 else if(s[i] =='D'){
	 	--x;
     	++i;
	 }
	 if(x>max)
	 max=x;
	}
	printf("%d",max);
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
    int N,i,v,j,k;
    scanf("%d",&N);
    int A[N]; 
    for(i=0; i<N; i++){
        scanf("%d",&A[i]);
    }
    for(i=0; i<N; i++){
        v = A[i];
        j = i-1;
        while( j>= 0 && A[j] > v){
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        for(k=0; k<N; k++){
            printf("%d",A[k]);
            if(k<N-1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}



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

ll gcd(ll b, ll c){
    return c ? gcd(c, b % c) : b;
}

ll lcm(ll b, ll c){
    return b / gcd(b, c) * c;
}

ll func(ll a, ll b, ll c){
    ll s = a;
    s -= a / b;
    s -= a / c; 
    s += a / lcm(b, c);
    return s;
}

int main(){
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    ll ans = func(B, C, D) - func(A - 1, C, D);
    cout << ans << endl;
    return 0;
} 

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kishan Sairam Adapa
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define ll long long int
#define MOD ((int)(1e9) + 7)

using namespace std;

class DCaracalVsMonster {
public:
    void solve(istream& cin, ostream& cout) {
        ll h;
        cin >> h;
        ll ans = 1;
        while(h) {
            ans *= 2;
            h /= 2;
        }
        cout << ans -1 << '\n';
    }
};


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


Measured memory_bytes: 256
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())

R=[a,b,c,d,e]
TT=0
t=[0]*5
T=[0]*5

for i in range(10):
	if (R[0]+i)%10 == 0:
		t[0]=a+i
	if (R[1]+i)%10 == 0:
		t[1]=b+i
	if (R[2]+i)%10 == 0:
		t[2]=c+i
	if (R[3]+i)%10 == 0:
		t[3]=d+i
	if (R[4]+i)%10 == 0:
		t[4]=e+i

for k in range(5):
    TT+=t[k]

for j in range(5):
    T[j]=TT-t[j]+R[j]
print(min(T))

Measured memory_bytes: 3064
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main(){
    let n: u32 = read();

    for i in 1..10{
        if n % i == 0 && n / i<= 9 {
            println!("Yes");
            return
        }else if i == 9{
            println!("No");
        }
    }
}


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

int getMoney(int x)
{
    if (x == 1) return 300000;
    if (x == 2) return 200000;
    if (x == 3) return 100000;

    return 0;
}

int main()
{
    int x, y;
    cin >> x >> y;

    int ans = 0;

    ans += getMoney(x);
    ans += getMoney(y);

    if (x == 1 && y == 1) ans += 400000;
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <utility>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <array>
#include <math.h>
#include <numeric>
#include <sstream>
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    string s;
    cin >> s;
    vector<int> a;
    ll n = stoll(s);
    for (int i = 0; i < s.length(); ++i) {
        a.push_back(n % 10);
        n /= 10;
    }
    reverse(a.begin(), a.end());
    //for (auto g : a) cout << g << std::endl;
    vector<int> b;
    for (int i = 0; i < s.length()-2; ++i) {
        b.push_back(a[i]*100+a[i+1]*10+a[i+2]);
    }
    int min = 1 << 29;
    for (int i = 0; i < s.length()-2; ++i) {
        int x = abs(b[i]-753);
        if (x < min) min = x;
    }
    cout << min << std::endl;
    return 0;
}

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

int A[103], B[103], cnt;

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++)
	{
		scanf("%d", &A[i]);
		cnt += (A[i] & 1);
	}
	if(cnt > 2) return puts("Impossible"), 0;
	if(m == 1 && A[1] == 1) return printf("1\n1\n1\n"), 0;
	if(m == 1) return printf("%d\n2\n%d 1\n", A[1], A[1] - 1), 0;
	sort(A + 1, A + 1 + m, [](int x, int y) { return (x & 1) > (y & 1); });
	swap(A[2], A[m]);
	for(int i = 1; i <= m; i++)
		printf("%d%c", A[i], " \n" [i == m]);
	printf("%d\n%d ", A[m] > 1 ? m : m - 1, A[1] + 1);
	for(int i = 2; i < m; i++)
		printf("%d ", A[i]);
	if(A[m] > 1) printf("%d\n", A[m] - 1);
	return 0;
}


Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Control.Monad.ST
-- import qualified Data.ByteString as BS
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
--import qualified Data.Sequence as Sequence
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
import Data.Array
--import Data.Array.Unboxed
--import Data.Array.IArray
import Data.Array.MArray
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
import GHC.ST
-- import System.IO.Unsafe
 
-- templete
readInt = read :: String -> Int
readInteger = read :: String -> Integer
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getInteger = readLn :: IO Integer
getIntegers = map readInteger . words <$> getLine
getDouble = readLn :: IO Double
getDoubles = map readDouble . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
tjoin :: (Show a, Show b) => (a, b) -> String
tjoin (x, y) = show x ++ (' ' : show y)
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
binMap :: (a -> a -> b) -> [a] -> [b]
binMap f (x:xs@(y:_)) = f x y : binMap f xs
binMap _ _ = []
splitRec :: Int -> [a] -> [[a]]
splitRec _ [] = []
splitRec n xs = let (y,ys) = splitAt n xs in y : splitRec n ys
infixl 7 `divCeil`
divCeil :: Integral a => a -> a -> a
x `divCeil` y = (x+y-1) `div` y
coverC :: Ord a => (a, a) -> a -> Bool
coverC (l,r) x = l<=x && x<=r
coverH :: Ord a => (a, a) -> a -> Bool
coverH (l,r) x = l<=x && x<r
ibsearch :: (Int -> Bool) -> (Int,Int) -> Int
ibsearch f (ok,ng) = if abs (ok-ng) <= 1 then ok else let mid = (ok + ng) `div` 2 in ibsearch f (if f mid then (mid,ng) else (ok,mid))
whenM :: Monad m => m Bool -> m () -> m ()
whenM c a = c >>= flip when a
-- templete

--readF :: String -> Rational
readF s = ipart + fpart
  where
    [i,f] = wordsBy (=='.') s
    ipart = readInteger i % 1
    fpart = fsub deci f
    fsub w ('(':xs) = let cpart = init xs in w / deci * (readInteger cpart % (10^(length cpart) - 1))
    fsub w (x:xs) = let d = (toInteger . digitToInt) x in w * (d % 1) + fsub (w*deci) xs
    fsub w [] = 0
    deci = 1 % 10

showR r = show (numerator r) ++ "/" ++ show (denominator r)

main = getLine >>= putStrLn . showR . readF



Measured memory_bytes: 3764
function Main(input) {
  input = input.split("\n");
  tmp = input[0].split(" ");
  var n = Number(tmp[0]);
  var x = Number(tmp[1]);
  tmp2 = input[1].split(" ");
  a = new Array(n);
  b = new Array(n).fill(0);
  var ans=0;
  for(i=0; i<n; i++){
    a[i]=Number(tmp2[i]);
  }
  for(i=0; i<n; i++){
    if(a[i]>x){
      ans=ans+a[i]-x;
      a[i]=x;
    }
  }
  for(i=0; i<n; i++){
    if(a[i]+a[i+1]>x){
      if(a[i+1]>a[i]+a[i+1]-x){
        ans=ans+(a[i]+a[i+1]-x);
        a[i+1]=a[i+1]-(a[i]+a[i+1]-x);
      }else{
        ans=ans+(a[i]+a[i+1]-x);
        a[i+1]=0;
      }
    }
  }

  console.log('%s', ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29592
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int D, N, T[200], A[200], B[200], C[200], dp[200][200];
int rec(int today,int atai){
  if(today == D) return 0;
  if(dp[today][atai]) return dp[today][atai];
  int ret = 0;
  for(int i = 0 ; i < N ; i++ ){
    if(T[today] >= A[i] && T[today] <= B[i]){
      ret = max( ret, rec( today + 1, C[i]) + (today ? abs(atai - C[i]) : 0));
    }
  }
  return dp[today][atai] = ret;
}
int main(){
  cin >> D >> N;
  for(int i = 0 ; i < D ; i++ ) cin >> T[i];
  for(int i = 0 ; i < N ; i++ ) cin >> A[i] >> B[i] >> C[i];
  cout << rec(0,0) << endl;
}

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

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m+1):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])

for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])
    

for l,r in al:
    print(cost[r]-cost[l])
            
                


Measured memory_bytes: 39976
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	ll k,a,b;
	cin >> k >> a >> b;
	if(b-a<=2 || k<a+1){
		cout << 1+k << endl;
	}else{
		k -= (a-1);
		if(k == 0) cout << a << endl;
		else if(k==1) cout << a+1 << endl;
		else if(k%2==0){
			cout << b+(k/2-1)*(b-a) << endl;
		}else{
			cout << b+(k/2-1)*(b-a)+1 << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



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

	int A, B, C;
	cin >> A >> B >> C;
	vector<bool> used(B, false);
	int i = A;
	while (1) {
		if (i%B == C) {
			cout << "YES\n";
			return 0;
		}
		if (used[i%B]) {
			cout << "NO\n";
			return 0;
		}
		used[i%B] = true;
		i += A;
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <numeric>
using namespace std;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;

int main()
{
    string s, t;
    cin >> s >> t;
    int difnum = 0;
    rep(i, t.length())
    {
        if (s[i] != t[i])
        {
            difnum++;
        }
    }
    if (difnum > 1)
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3104
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>
using namespace std;

/*--- Macro ---*/
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rep1(i, n) for(int i=1; i<(int)n; i++)
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

/*---  Type ---*/
typedef long long ll;

/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;

// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

// Util
int max(int a, int b, int c) {return max(a, max(b, c));}
int min(int a, int b, int c) {return min(a, min(b, c));}
ll max(ll x, ll y) {return x > y ? x : y;}
ll min(ll x, ll y) {return x < y ? x : y;}
ll max(ll a, ll b, ll c) {return max(a, max(b, c));}
ll min(ll a, ll b, ll c) {return min(a, min(b, c));}

// -------------------------------------------------------------------------------------



int main() {
  int n;
  cin >> n;
  if(n % 2 == 0) cout << n << endl;
  else cout << 2 * n << endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//String s = sc.next();
		//String t = sc.next();
		//String g = sc.next();
		long n = sc.nextLong();
		long m = sc.nextLong();
		long k = sc.nextLong();
		//long l = sc.nextLong();
		long count=0;
		long[] array=new long[3];
		array[0] = n;
		array[1] = m;
		array[2] = k;

		/*for(int i=0;i<=3;i++) {
			if(s.substring(i,i+1).equals("+")) {
				count++;
			}else {
				count--;
			}
		}*/
		Arrays.sort(array);
		/*if() {
			System.out.println(n);
		}else{
			System.out.println(n*2);
		}*/
		//System.out.println((int)Math.ceil((n+m)/2.0));
		System.out.println(Math.abs(array[2]-array[1])+Math.abs(array[1]-array[0]));
	}
}




Measured memory_bytes: 23764
#include<bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;
using Graph = vector<vector<int>>;

int main(){
    int N,K;
    cin >> N >> K;
    ll ans = K;
    rep(i,N-1) ans *= K-1;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(ll i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (ll i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};

int main(){
    ll n;
    cin >> n;
    ll ans = 0;
    rep(i, n) {
        ans += (i+1)*(n-i);
    }
    rep(i, n-1) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        if (u>v) swap(u, v);
        ans -= (u+1)*(n-v);
    }
    
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3604
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def prime_factorize(n: int) -> list:
    return_list = []
    while n % 2 == 0:
        return_list.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            return_list.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        return_list.append(n)
    return return_list

def main():
    n = i_input()

    if n == 1:
        print(0)
        exit()

    tmp = prime_factorize(n)

    if len(tmp) == 1:
        print(1)
        exit()

    count = 0

    counter_tmp = Counter(tmp)

    a_list = []

    for k, v in counter_tmp.items():
        while v >= 1:
            a_list.append(k**v)
            v -= 1

    a_list.sort()

    for a in a_list:
        if n % a != 0:
            continue
        n /= a

        count += 1

    print(count)

if __name__ == '__main__':
    main()


Measured memory_bytes: 68600
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(){
    int n;
    scanf("%d",&n);
    if(n % 2 == 0){
        printf("%d",n/2);
    }else{
        printf("%d",n/2 + 1);
    }
    return 0;
}


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

#include<iostream>

using namespace std;

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

#define rep1(i,n) for(ll i=1;i<=n;i++)

typedef long long ll;



ll a,b,c,d;

ll N;


int main()

{

	cin>>a>>b>>c>>d;

	cin>>N;

	N*=4LL;

	ll ans=0LL;

	if(d<c*2&&d<b*4&&d<a*8){if(N/8LL >0LL) ans+=(N/8LL)*d;

	N%=8LL;}

	if(c<b*2&&c<a*4){ if( (N/4LL) >0LL) ans+=(N/4LL)*c;

	N%=4LL;}

	if(b<a*2){ if(N/2LL>0LL) ans+=(N/2LL)*b;

	N%=2LL;}

	if(N>0LL) ans+= N*a;

	N%=1LL;

	cout<<ans<<endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int pos[5010];
long long f[2][5010];
int n;
int a,b;
int main()
{
	scanf("%d %d %d",&n,&a,&b);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		pos[x]=i;
	}
	for(int i=1;i<=n;i++)
		if(i<pos[1])f[1][i]=b;
		else if(i>pos[1])f[1][i]=a;
		else f[1][i]=0;
	for(int i=2;i<=n;i++)
	{
		int now=i&1;
		int lst=now^1;
		for(int j=1;j<=n;j++)
			if(j<pos[i])
				f[now][j]=f[lst][j]+b;
			else if(j==pos[i])
			{
				f[now][j]=1e18;
				for(int k=1;k<=j;k++)
					f[now][j]=min(f[now][j],f[lst][k]);
			}
			else f[now][j]=f[lst][j]+a;
	}
	long long ans=1e18;
	for(int i=1;i<=n;i++)
		ans=min(ans,f[n&1][i]);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 384
// https://atcoder.jp/contests/abc176/tasks/abc176_c
#include <iostream>
#include <algorithm>
#include <set>
#include <stack>
#include <string>
using namespace std;
typedef long long ll;
const int MAXN=2e5;

ll a[MAXN];

void solve() {
    int N; ll total = 0;
    cin >> N;
    for (int x = 0; x < N; x++) 
        cin >> a[x];
    for (int x = 0; x < N-1; x++) 
        if (a[x] > a[x+1]) {
            total += a[x] - a[x+1];
            a[x+1] = a[x];
        }
    cout << total;
}

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

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

#define   ll    long long int

int ok(ll n, ll k)
{
    if (n < k) return 0;
    while (n >= k) {
        if (n % k == 0) {
            n /= k;
        }
        else {
            ll a = n / k;
            n = n - a * k;
        }
    }
    if (n == 1) return 1;
    return 0;
}


int main( )
{
    ll c = 0;
    ll n, rt;
    cin >> n;
    if (n == 2) {
        cout << "1\n";
        return 0;
    }
    rt = sqrt(n);
    for (int i = 2; i <= rt; i++) {
        if (ok(n, i) == 1) {
            //cout << i << '\n';
            c++;
        }
        if (n / i != i && ok(n, n / i) == 1) {
            //cout << 3141 / i << '\n';
            c++;
        }
    }
    cout << c + 2 << "\n";
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <iomanip>
#include <stdio.h>
#include <queue>
#include <string.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define LL long long
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
int n;
int a[110];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        if(a[i]%2==0){
            if(a[i]%3!=0&&a[i]%5!=0)return puts("DENIED"),0;
        }
    }
    return puts("APPROVED"),0;
}


Measured memory_bytes: 256
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

N = int(input())
A = [int(input()) for _ in range(N)]
C = Counter(A[::2])
D = Counter(sorted(A)[::2])
ans = 0

for k, v in D.items():
    ans += max(0, v - C[k])
print(ans)

Measured memory_bytes: 56028
#店1:月1 月2 火1 火曜2...
#店2:月1 ... 金2
#みたいな入力
from itertools import accumulate
n = int(input())
lis = []
for i in range(n):
    A=[int(i) for i in input().split()]
    lis.append(A)
ans = [0]*10
lis2 = []
for i in range(n):
    p = [int(i) for i in input().split()]
    lis2.append(p)

#時間帯bit(i)で営業する場合を見るのでbit全探索
ans = -10000000000
for i in range(1,1<<10):
    kaburi = [0]*n#状態iで店を開く時に被ってる店舗を1~Nごとに記録する　kaburi[i]:店iと何個被ってるか
    tmp = 0
    for j in range(11):
        if(i & 1<<j):
            for k in range(n):
                if lis[k][j]:
                    kaburi[k]+=1
    for j in range(n):
        tmp += lis2[j][kaburi[j]]

    ans = max(tmp, ans)
print(ans)


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

using namespace std;

const int MAX_N = 200010;
const long long P = 1000000007;
int N;
long long A[MAX_N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];
	
	long long sum = 0, sos = 0;
	for (int i = 0; i < N; i++) {
		sum = (sum + A[i]) % P;
		sos = (sos + ((A[i] * A[i]) % P)) % P;
	}
	
	long long ans = (((P + 1LL) / 2LL) * ((((sum * sum) % P) - sos + P) % P)) % P;
	cout << ans << "\n";
	
	return 0;
}


Measured memory_bytes: 5176
/* B Merge Sort */

#include<stdio.h>
/*#include<limits.h>*/
int n;  /* n <= 500000 */
void MergeSort(int A[], int l, int r);
void Merge(int A[], int l, int m, int r);
int counter=0;

int main(){

  int S[500001];  /* 0 <= an element in S <= 10^9 */
  int i;

  /*printf("int Max %d\n", INT_MAX);*/
  scanf("%d",&n);

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

  MergeSort(S, 0, n);
  for(i=0;i<n-1;i++){
    printf("%d ", S[i]);
  }
  printf("%d\n", S[i]);

  printf("%d\n",counter);
  return 0;
}

void Merge(int A[], int l, int m, int r){
  int n1, n2, i, j, k;
  int L[500001], R[500001];
  n1=m-l;
  n2=r-m;
  for(i=0; i<=n1-1; i++){
    L[i]=A[l+i];
  }
  for(j=0;j<=n2-1;j++){
    R[j]=A[m+j];
  }
  L[n1]=1000000001;
  R[n2]=1000000001;
  i=0;
  j=0;
  for(k=l;k<=r-1;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i=i+1;
      counter++;
    }else{
      A[k]=R[j];
      j=j+1;
      counter++;
    }
  }
}

void MergeSort(int A[], int l, int r){
  int m;
  if(l+1<r){
    m=(l+r)/2;
    MergeSort(A, l, m);
    MergeSort(A, m, r);
    Merge(A, l, m, r);
  }
}

Measured memory_bytes: 4324
def is_include?(i, arr)
    if arr.length == 1 then
        if arr[0] == i then
            return true
        else
            return false
        end
    else
        x = arr.length / 2
        if i < arr[x] then
            is_include?(i, arr[0..x-1])
        else
            is_include?(i, arr[x..arr.length-1])
        end
    end
end

gets
s = gets.split.map(&:to_i)
gets
t = gets.split.map(&:to_i)
cnt = 0

x = s.length / 2
a = s[0..x-1]
b = s[x..s.length-1]

for i in t
    cnt += 1 if is_include?(i, s)
end

puts cnt


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

#define range(i, l, r) for (int i = (int)l; i < (int)(r); ++(i))
#define rrange(i, l, r) for (int i = ((int)(r) - 1); i >= (int)l; --(i))

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define rwhole(f,x,...) ([&](decltype((x)) whole) { return (f)(rbegin(whole), rend(whole), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using int32 = int;
using int64 = long long;

const int mod     = 1e9 + 7;
const int32 inf   = 1001001001;
const int64 infll = 1001001001001001001ll;

const int dx[] = {0, -1, 1, 0, -1, 1, -1, 1}, dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const string YES = "YES", NO = "NO", Yes = "Yes", No = "No", yes = "yes", no = "no";

struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(16); cerr << fixed << setprecision(16); } } iosetup;

template <typename T = int64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } 
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.fs << " " << p.sc; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.fs >> p.sc; return is; }

template <typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

void solver() {
  int N = input();
  
  map< string, int64 > mp;
  range(i, 0, N) {
    string s;
    cin >> s;

    whole(sort, s);
    mp[s]++;
  }

  int64 ans = 0;
  for (auto s : mp) {
    ans += (s.second - 1) * s.second / 2;
  }

  cout << ans << endl;
}

signed main(int argc, char *argv[]) {
  solver();
}


Measured memory_bytes: 11264
from collections import deque


B = deque()
n = int(input())
A = list(map(int, input().split()))

for i, a in enumerate(A):
    if i % 2 == 0:
        B.append(a)
    else:
        B.appendleft(a)

if n % 2 == 1:
    B.reverse()
print(*B)


Measured memory_bytes: 32436
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
int main()
{
    int n,i,j,k,result=0,a,b;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            for(k=1;k<=n;k++)
            {
                a=gcd(i,j);
                result+=gcd(a,k);
            }
        }
    }
    cout<<result<<endl;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(0); 
    cin.tie(0);   
	ll n,a[29][29],ans[30][30],r[100],c[100],m,k,fin=0;
	string s;
	cin>>n>>m>>k;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		for(int j=0;j<m;j++)
		{
			if(s[j]=='#')
				a[i][j]=1;
			else
				a[i][j]=0;
			ans[i][j]=a[i][j];
		}
	}
	ll nn=pow(2,n),mm=pow(2,m);
	for(int i=0;i<nn;i++)
	{
		ll h=0,temp=i;
		for(int l=0;l<n;l++)
			r[l]=0;
		while(temp)
		{
			r[h]=temp%2;
			temp/=2;
			h++;

		}
		for(int j=0;j<mm;j++)
		{
			h=0;
			temp=j;
			for(int l=0;l<m;l++)
				c[l]=0;
			while(temp)
			{
				c[h]=temp%2;
				temp/=2;
				h++;
			}
			for(int l=0;l<n;l++)
			{
				if(r[l]==1)
				{
					for(int p=0;p<m;p++)
						ans[l][p]=0;
				}
			}
			for(int l=0;l<m;l++)
			{
				if(c[l]==1)
				{
					for(int p=0;p<n;p++)
						ans[p][l]=0;
				}
			}
			ll count=0;
			for(int l=0;l<n;l++)
			{
				for(int p=0;p<m;p++)
				{
					if(ans[l][p]==1)
						count++;
				}
			}
			// for(int l=0;l<n;l++)
			// {
			// 	for(int p=0;p<m;p++)
			// 		cout<<ans[l][p]<<" ";
			// 	cout<<endl;
			// }
			// cout<<endl;
			for(int l=0;l<n;l++)
			{
				for(int p=0;p<m;p++)
					ans[l][p]=a[l][p];
			}
			if(count==k)
				fin++;
		}
	}
	cout<<fin<<endl;
	return 0;
}

Measured memory_bytes: 4100
#include<stdio.h>

int main(){
	int first;
	int second;
	int answer;

	for( first = 0; first < 10; first++ ) {
		for( second = 0; second < 10; second++ ) {
			answer = first * second; 
			if( first != 0 && second != 0) {
				printf("%dx%d=%d\n", first, second, answer);
			}
		}
	}

	return 0;
}

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

int main()
{
    string a, b;
    cin >> a >> b;
    for(int i = 0; i<min(a.size(), b.size()); i++)
        cout << a[i] << b[i];
    if(a.size()>b.size())cout<<a[a.size()-1];
    else if(a.size()<b.size())cout << b[a.size()-1];
}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

const ll MAX = 200010;
const ll MOD = 998244353;

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

void com_init() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll com(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

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

    com_init();
    ll res = 0;
    for (int i = 0; i <= k; ++i) {
        res += (m * com(n-1, i) % MOD) * modpow(m-1, n-1-i, MOD) % MOD;
        res %= MOD;
    }

    res += MOD;
    res %= MOD;
    cout << res << endl;
}

Measured memory_bytes: 8288
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int MAX = 1000000;
const int INF = 1e9;
const double pi=acos(-1);


int main(){
  string s;
  int q;
  cin >> s >> q;
  int sum=0;
  int forw=1;
  deque<string>deq;
  deq.push_front(s);
  rep(i,q){
    int x;
    cin >> x;
    if(x==1){
      if(forw==1)forw=2;
      else forw=1;
    }
    else{
      int f;
      string c;
      cin >> f >> c;
      if((f+forw)%2==0)deq.push_front(c);
      else deq.push_back(c);
    }
  }
  if(forw==1){
    while(!deq.empty()){
      string t=deq.front();
      deq.pop_front();
      cout <<t;
    }
  }
  else{
    while(!deq.empty()){
      string t=deq.back();
      deq.pop_back();
      if(s==t)reverse(t.begin(),t.end());
      cout <<t;
    }
  }
  return 0;
}


Measured memory_bytes: 11648
n, m = map(int, input().split())
scList = [list(map(int, input().split())) for _ in range(m)]
num = ["-" for _ in range(n)]
flag = True
for i in range(m):
    s = scList[i][0] - 1
    c = scList[i][1]
    if num[s] != "-" and num[s] != str(c):
        flag = False
        break
    elif n != 1 and (s == 0 and c == 0):
        flag = False
        break
    num[s] = str(c)
if not flag:
    print("-1")
else:
    ans = "".join(num)
    ans = ans.replace("-", "0")
    if ans[0] == "0" and n != 1:
        ans = "1" + ans[1:]
    print(ans)


Measured memory_bytes: 3064
import sys
from collections import deque
input = sys.stdin.readline
n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
ans=[-1]*n
q,k=map(int,input().split())
ans[k-1]=0
d=deque([k-1])
while d:
  now=d.pop()
  for x in l[now]:
    a,b=x
    if ans[a]<0:
      ans[a]=ans[now]+b
      d.appendleft(a)
for i in range(q):
  a,b=map(int,input().split())
  print(ans[a-1]+ans[b-1])

Measured memory_bytes: 83376
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

struct Node{
  int key;
  Node *next;
  Node *prev;
};

Node *nil;

void init(){
  nil = (Node *)malloc(sizeof(Node));
  nil->next = nil;
  nil->prev = nil;
}

void insert(int key){
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;
  x->next = nil->next;
  x->prev = nil;
  nil->next->prev = x;
  nil->next = x;
}

Node* listSearch(int key){
  Node *cur = nil->next;
  while ( cur != nil && cur->key != key){
    cur = cur->next;
  }
  return cur;
}

void deleteNode(Node *t){
  if ( t == nil ) return;
  t->next->prev = t->prev;
  t->prev->next = t->next;
  free(t);
}

void deleteKey(int key){
  deleteNode(listSearch(key));
}

void deleteFirst(){
  deleteNode(nil->next);
}

void deleteLast(){
  deleteNode(nil->prev);
}

void print(){
  Node *cur = nil->next;
  int i = 0;
  while (cur != nil){
    if ( i ) printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
    i++;
  }
  printf("\n");
}

int main(){
  int n, key;
  char com[20];

  scanf("%d", &n);
  init();
  for ( int i = 0; i < n; i++){
    scanf("%s", com);
    if ( com[0] == 'i'){
      scanf("%d", &key);
      insert(key);
    } else if ( strlen(com) == 6) {
      scanf("%d", &key);
      deleteKey(key);
    } else if (com[6] == 'F') {
      deleteFirst();
    } else deleteLast();
  }

  print();

  return 0;
}


Measured memory_bytes: 33944