akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int main(){
  int i,j,a,b,c1=0,c2=0;
  int hai1[10000],hai2[1000];

  scanf("%d",&a);
  for(i=0;i < a ; i++){
    scanf("%d",&hai1[i]);
  }
  scanf("%d",&b);
  for(i=0;i < b ; i++){
    scanf("%d",&hai2[i]);
  }
 
  
  for(i=0 ;i < b ; i++){
    for(j=0 ; j  < a ; j++){
      if(hai1[j] == hai2[i]){
        c2++;
        c1++;
        if(c2>=2){
          c1--;
        }
      }
    }
    c2=0;
  }
  printf("%d",c1);
  printf("\n");

  return 0;
}



Measured memory_bytes: 2104
#include "bits/stdc++.h"

#define rep(i, a) for (int i = 0; i < (a); ++i)
#define FORV(a, A) for (auto &a : A)

using namespace std;

using ll = long long;

void Main() {
  int n;
  cin >> n;
  for (int i = 1; i < 10; ++i) {
    if (n % i == 0 && n / i < 10) {
      cout << "Yes" << endl;
      return;
    }
  }
  cout << "No" << endl;
}

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


Measured memory_bytes: 256
"use strict";

const main = arg => {
    let rows = arg.trim().split("\n");
  	let N = rows[0].split(" ")[0]*1;
    let Q = rows[0].split(" ")[1];
    let S = rows[1].split("");
  
  	// 累積和を使うために分解していく
  	let ACNums = new Array(N).fill(0);
	for(let i = 1; i < N; i++){
    	if(S[i] == "C" && S[i - 1] == "A"){
        	ACNums[i] = ACNums[i - 1] + 1
        } else {
	        ACNums[i] = ACNums[i - 1]
        }
    }
  
  	// 書き出しの処理
  	let targetNums = rows.slice(2 , 2 + Q);
  	targetNums.forEach(
      (targetNum) => {
      	let s = targetNum.split(" ")[0] - 1;
        let g = targetNum.split(" ")[1] - 1;
        console.log(ACNums[g] - ACNums[s]);
      }
    )
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 36712
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for(int i=0; i<(int)(a); i++)
typedef long long ll;
const ll mod = 1000000007;

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

  int t = (n-2)*(n-1)/2;
  if (t < k) {
    cout << -1 << endl;
    return 0;
  }

  printf("%d\n", n-1+(t-k));
  for (int i=2; i<=n; i++) {
    printf("%d %d\n", 1, i);
  }
  for (int i=2; i<n; i++) {
    for (int j=i+1; j<=n; j++) {
      if (t <= k) return 0;
      printf("%d %d\n", i, j);
      t--;
    }
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>

using namespace std;

int bit[108000];

int cnt(int x){
  x++;
  int res = 0;
  while(x){
    res += bit[x];
    x -= x & -x;
  }
  return res;
}

void add(int x, int val){
  x++;
  while(x < 108000){
    bit[x] += val;
    x += x & -x;
  }
}

int n, a[108000], b[108000];
int res;
int main(){
  cin >> n;
  for(int i = 0;i < n;i++){
    cin >> a[i];
    b[i] = a[i];
  }
  sort(b, b + n);
  for(int i = 0;i < n;i++){
    a[i] = lower_bound(b, b + n, a[i]) - b;
    if((a[i] - i ) % 2 != 0)res++;
  }
  cout << res/2 << endl;
  return 0;
}


Measured memory_bytes: 1656
import java.util.Scanner;

class Main {
  public static final String NODE = "node ";
  public static final String KEY = ": key = ";
  public static final String COMMA = ", ";
  public static final String PARENT = "parent key = ";
  public static final String LEFT = "left key = ";
  public static final String RIGHT = "right key = ";

  public static void main(String... args) {
    Scanner sc = new Scanner(System.in);
    int size = sc.nextInt() + 1;
    int[] tree = new int[size];
    for (int i = 1; i < size; i++) {
      tree[i] = sc.nextInt();
    }
    int capacity = 100;
    StringBuilder sb = new StringBuilder(capacity);
    for (int i = 1; i < size; i++) {
      sb.append(NODE).append(i).append(KEY).append(tree[i]).append(COMMA);

      if (i != 1) {
        sb.append(PARENT).append(tree[i / 2]).append(COMMA);
      }

      if (i * 2 < size) {
        sb.append(LEFT).append(tree[i * 2]).append(COMMA);
        if (i * 2 + 1 < size) {
          sb.append(RIGHT).append(tree[i * 2 + 1]).append(COMMA);
        }
      }

      System.out.println(sb);
      sb = new StringBuilder(capacity);
    }
  }
}



Measured memory_bytes: 27552
N, M = map(int, input().split())
H_ = list(map(int,input().split()))
H = [0]
H.extend(H_)
D = dict()
for i in range(M):
    t_ = list(map(int,input().split()))
    if t_[0] not in D.keys():
        D[t_[0]] = [t_[1]]
    else:
        D[t_[0]].append(t_[1])
    if t_[1] not in D.keys():
        D[t_[1]] = [t_[0]]
    else:
        D[t_[1]].append(t_[0])
ret = list()
for v in D.keys():
    L = D[v]
    for i in range(len(L)):
        if H[v] <= H[L[i]]:
            break
        if i == len(L) - 1:
            ret.append(v)
num = N - len(D.keys()) + len(ret)
print(num)

Measured memory_bytes: 32864
#include<iostream>
#include<string>
#include <algorithm>
#include <vector>
#include<map>
using namespace std;

int main(){
  
  int N, cnt=0;
  int p_no, q_no;
  string p_in,q_in,p="",q="",j="";
  cin>>N;
  
  for(int i=0;i<N;i++){
    cin>>p_in;
    p += p_in;
  }
  
  for(int i=0;i<N;i++){
    cin>>q_in;
    q += q_in;
  }
  
  vector<int> v(N);
  for(int i=0;i<N;i++){
   v[i]=i+1; 
  }
  
  do {
    cnt++;
    for(auto x : v) {
      j += to_string(x);
    }
    //cout<<j<<endl;
    if(j == p){
      p_no = cnt;
    }
    
    if(j == q){
      q_no = cnt;
    }
    
    j = "";
  } while( next_permutation(v.begin(), v.end()) );     // 次の順列を生成
  
  cout<<abs(p_no-q_no)<<endl;
   
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int dist[2][100000],id,s;
vector<int>g[100000];
bool dfs(int idx,int par=-1)
{
	if(~par)dist[id][idx]=dist[id][par]+1;
	for(auto &to:g[idx])
	{
		if(to!=par)dfs(to,idx);
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	id=0;
	dfs(0);
	id=1;
	dfs(n-1);
	for(int i=0;i<n;i++)
	{
		if(dist[0][i]<=dist[1][i])s++;
	}
	if(s>=(n+2)/2)cout<<"Fennec\n";else cout<<"Snuke\n";
	return 0;
}


Measured memory_bytes: 11136
#include <iostream>

using namespace std;

#define int_64 long long

const int N = 2e5 + 10;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);    
  int n;
  cin >> n;
  cout << (((n + 999) / 1000) * 1000 - n);
  return 0;
}

Measured memory_bytes: 3648
import sys
N=int(input())
if N==1:
    print('Yes')
    sys.exit()
A=[]
B=list(range(2,10))
B=B[::-1]
for i in B:
    while N%i==0:
        A.append(i)
        N//=i
if N==1 and 1<=len(A) and len(A)<=2:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> x(N), y(N);
  for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
  
  vector<int> v(N);
  for (int i = 0; i < N; ++i) v[i] = i;
  double ans = 0;
  do {
    for (int i = 1; i < N; ++i) {
      ans += sqrt((x[v[i]] - x[v[i - 1]]) * (x[v[i]] - x[v[i - 1]]) + (y[v[i]] - y[v[i - 1]]) * (y[v[i]] - y[v[i - 1]]));
    }
  } while (next_permutation(v.begin(), v.end()));
  int F = 1;
  for (int i = 0; i < N; ++i) F *= (i + 1);
  ans /= F;
  
  cout << fixed << setprecision(10);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
  
int main(){
  
  char A;
  cin >> A;
  
  if(A == 'a' || A == 'i' || A == 'u' || A == 'e' || A == 'o' ){
    
  cout << "vowel" << endl;
  
  }
  
  else{
    
  cout << "consonant" << endl;
    
  }
  
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;
const int MAXN = 305;

int A[MAXN + 5][MAXN + 5];

int N, M;

bool Check(int ans)
{
	int f[MAXN + 5], sum[MAXN + 5];
	bool t[MAXN + 5];
	for(int i = 1; i <= N; i++) f[i] = 1;
	for(int i = 1; i <= M; i++) t[i] = true;
	bool check = false;
	while(!check){
		memset(sum, 0, sizeof(sum));
		for(int i = 1; i <= N; i++){
			int tot = f[i], c = A[i][tot];
			sum[c]++;
		}
		bool ok = true;
		for(int i = 1; i <= M; i++){
			if(sum[i] > ans) ok = false;
		}
		if(ok){
			check = true;
			break;
		}
		else{
			for(int i = 1; i <= N; i++){
				int tot = f[i], c = A[i][tot];
				if(sum[c] > ans) t[c] = false;
			}
			for(int i = 1; i <= N; i++){
				int tot = f[i], c = A[i][tot];
				if(sum[c] > ans){
					while(f[i] <= M && !t[A[i][f[i]]]) f[i]++;
				}
				if(f[i] > M) ok = true;
			}
			if(ok) break;
		}
	}
	return check;
}

int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
	scanf("%d %d", &N, &M);
	for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) scanf("%d", &A[i][j]);
	int L = 1, R = 305, tot = 0;
	while(L <= R){
		int mid = (L + R) >> 1;
		if(Check(mid)) tot = mid, R = mid - 1;
		else L = mid + 1;
	}
	printf("%d\n", tot);
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h> 
#define ll long long 
#define pb push_back 
#define vec vector<int> 
#define fo(i,n) for (ll i = 0; i < n; i++)
#define so(v) sort(v.begin(), v.end())
#define fi first
#define se second 
using namespace std;  
int main()
{
 ll n,d;
cin>>n>>d;
int count=0;
ll x,y;
fo(i,n)
{
    cin>>x>>y;
    if((x*x+y*y)<=d*d)
       
    {
        count++;
    }
}
cout<<count;

}

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

public class Main{
    public static void main(String[] args){
	Scanner scan = new Scanner(System.in);

	/* 入力 */
	int n = scan.nextInt();
	int m = scan.nextInt();
	int[] l = new int[m];
	int[] r = new int[m];
	for(int i = 0; i < m; i++){
	    l[i] = scan.nextInt();
	    r[i] = scan.nextInt();
	}

	/* lの最大値 rの最小値 */
	Arrays.sort(l);
	Arrays.sort(r);
       	if(r[0]-l[m-1]+1 < 0){
	    System.out.println(0);
	}else if(r[0]-l[m-1]+1 < n){
	    System.out.println(r[0]-l[m-1]+1);
	}else{
	    System.out.println(n);
	}
    }
}


Measured memory_bytes: 80524
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k,u,d;
    cin>>n;
    vector<vector<int> > Adj(n,vector<int>(n,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            Adj[i][j]=0;
        }
    }
    for(int i=0;i<n;i++){
        cin>>k>>u;
        for(int j=0;j<u;j++){
            cin>>d;
            Adj[k-1][d-1]=1;
        }
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(j==n-1){
                cout<<Adj[i][j]<<"\n";
            }else{
                cout<<Adj[i][j]<<" ";
            }
        }
    }
    
    return 0;
}


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

#define pb push_back
#define fst first
#define snd second
#define ALL(s) s.begin(),s.end()
#define fill(a,c) memset(&a, c, sizeof(a))
#define fore(i,x,y) for(ll i=x;i<y;i++)
#define SZ(x) ((int)(x).size())
#define PI 3.1415926535897932384626433832795
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef long long ll;
using namespace std;

int main() {FIN;
    int n,k; cin>>n>>k;
    int m = (n-1)*(n-2)/2;
    if(k > m){
        cout<<"-1\n"; return 0;
    }
    cout<<n-1+m-k<<"\n";
    fore(i,2,n+1) cout<<1<<" "<<i<<"\n";
    int cnt = 0;
    fore(i,2,n+1){
        fore(j,i+1,n+1){
            if(cnt == m-k) break;
            cout<<i<<" "<<j<<"\n";
            cnt++;
        }
        if(cnt == m-k) break;
    }
    return 0;
}



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

using namespace std;
long long maxSum(long long arr[], long long n, long long k)
{
    if (n < k)
    {
       cout << "Invalid";
       return -1;
    }
    long long res = 0;
    for (long long i=0; i<k; i++)
       res += arr[i];
    long long curr_sum = res;
    for (long long i=k; i<n; i++)
    {
       curr_sum += arr[i] - arr[i-k];
       res = max(res, curr_sum);
    }

    return res;
}

int main()
{
    long long n,i,k;
    cin>>n>>k;
    double sum=0;
    long long a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sum=sum+k+maxSum(a,n,k);
    sum=sum/2;
    cout << fixed << setprecision(12) <<sum<<endl;
    return 0;
}


Measured memory_bytes: 1792
import sys
from collections import defaultdict
def wi(): return list(map(int, sys.stdin.readline().split()))
def i(): return int(sys.stdin.readline())
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def mip(n): return [wip() for _ in range(n)]

def main():
    n, q = wi()
    ab = mip(n - 1)
    px = mip(q)
    for i in range(q):
        px[i][1] += 1


    cost = [0] * n
    for i in range(q):
        cost[px[i][0]] += px[i][1]

    son = [[] for _ in range(n)]
    for i in range(n - 1):
        son[ab[i][0]].append(ab[i][1])
        son[ab[i][1]].append(ab[i][0])

    flagli = [0] * n
    flagli[0] = 1
    queue = []
    queue.append(0)
    while queue != []:
        po = queue.pop()
        for kk in son[po]:
            if flagli[kk] == 0:
                flagli[kk] = 1
                queue.append(kk)
                cost[kk] += cost[po]

    for i in range(n):
        print(cost[i],"" , end="")

if __name__ == '__main__':
    main()

Measured memory_bytes: 112012
#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int SIZE = 500000 + 100;
int BIT[26][SIZE + 1];

int sum(int i, int a) {
    int ans = 0;
    while (a) {
        ans += BIT[i][a];
        int least = a & -a;
        a -= least;
    }
    return ans;
}
int sum(int i, int a, int b) {
    if (a > b)
        return 0;
    return sum(i, b) - sum(i, a - 1);
}
void add(int i, int a, int x) {
    while (a <= SIZE) {
        BIT[i][a] += x;
        int least = a & -a;
        a += least;
    }
}

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

    for (int i = 0; i < N; ++i) {
        for (int c = 'a'; c <= 'z'; ++c) {
            if (S[i] == c) {
                add(S[i] - 'a', i + 1, 1);
            }
        }
    }

    int Q;
    cin >> Q;
    for (int k = 0; k < Q; ++k) {
        int type;
        cin >> type;
        if (type == 1) {
            int i;
            char c;
            cin >> i >> c;
            --i;
            add(S[i] - 'a', i + 1, -1);
            add(c - 'a', i + 1, 1);
            S[i] = c;
        }
        else {
            int l, r;
            cin >> l >> r;

            int ans = 0;
            for (int i = 0; i < 26; ++i) {
                if (sum(i, l, r) > 0) {
                    ++ans;
                }
            }
            cout << ans << endl;
        }
    }
}


Measured memory_bytes: 51716
import sys
input=sys.stdin.readline

s=input().rstrip('\n')
n=int(input())

s_f=[]
s_b=[]
muki=True

for i in range(n):
    line=input().rstrip('\n')
    #print(line)
    if line == "1":
        muki=not muki
        continue

    q,f,c=map(str, line.split())
    q,f=int(q),int(f)
    if (f == 1 and muki) or (f == 2 and not muki):
        s_f.append(c)
    else:
        s_b.append(c)

ans = "".join(s_f[::-1]) + s + "".join(s_b)

if muki:
    print(ans)
else:
    print(ans[::-1])




Measured memory_bytes: 6252
n,m=map(int,input().split())
l=[]
ansac=0
answa=0
a=[0]*(n)
d=dict()
for i in range(m):
  p,s=input().split()
  l.append([int(p),s])
for i in range(m):
  if l[i][1]=='AC':
    if l[i][0] not in d:
      ansac+=1
      answa+=a[l[i][0]-1]
      d[l[i][0]]=0
  else:
    a[l[i][0]-1]+=1
print(ansac,answa)

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MK make_pair
#define REP(i, a, b) for (int i=a; i < b; i++)


bool sort_by(pi c, pi d){
	return c.S < d.S;
}

int main() {
	int h, w;
	cin >> h >> w;
	char grid[h][w];
	vector<bool> rows(h, false);
	vector<bool> cols(w, false);
	char c;
	
	REP(i, 0, h){
		REP(j, 0, w){
			cin >> c;
			rows[i] = (c=='#'?true:rows[i]);
			cols[j] = (c=='#'?true:cols[j]);
			grid[i][j] = c;
		}
	}
	
	REP(i, 0, h){
		if(!rows[i]) continue;
		REP(j, 0, w){
			if(cols[j]) cout << grid[i][j];
		}
		cout << endl;
	}
			
	
				

}


Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
#include<iomanip>
#include<math.h>
#include<vector>
#include<cctype>
#include<string>
#include<set>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
std::string line;
typedef long long ll;

int keta_calc(int n){
   int keta = 1;  //最低1桁としておく
   int tmp = n;
   while(tmp/10>0){
      tmp = tmp/10;
      keta++;
   }
   return keta;
};

int main(){

   int n;
   cin >> n;
int cnt = 0;
   for(int i=1;i<=n;i++){
      if(keta_calc(i)%2 != 0) cnt++;
   }

   cout << cnt << endl;

   return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
int n,a,i,ii,y,s[2048];
scanf("%d",&n);
for(i=1;i<=n;i++){
    scanf("%d",&a);
    s[i] = a;
}
for(i=0;i<=9;i++){
    y=0;
    for(ii=1;ii<=n;ii++){ 
        if(s[ii]==i){
            y=1;
            break;
        }
    }
    if(y==0){
        printf("%d\n",i);
        return 0;
    }
}
for(i=10;i<=99;i++){
    y=0;
    for(ii=1;ii<=n-1;ii++){ 
        if(s[ii]==i/10 &&s[ii+1]==i%10){
            y=1;
            break;
        }
    }
    if(y==0){
        printf("%d\n",i);
        return 0;
    }
}
for(i=100;i<=999;i++){
    y=0;
    for(ii=1;ii<=n-2;ii++){ 
        if(s[ii]==i/100 &&s[ii+1]==(i/10)%10 &&s[ii+2]==i%10){
            y=1;
            break;
        }
    }
    if(y==0){
        printf("%d\n",i);
        return 0;
    }
}
return 0;
}

Measured memory_bytes: 1036
import java.util.List;
import java.util.Scanner;

public class Main {

	static Scanner scanner;

	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    int a=gi();
	    int b=gi();
	    int t=gi();
	    
	    int s=b*Math.floorDiv(t, a);


	   
	    System.out.print(s);

//        if (a>b) {
//        	c+=a;
//        	a--;
//        	System.out.print(c+Math.max(a, b));
//        }else {
//        	c+=b;
//        	b--;
//        	System.out.print(c+Math.max(a, b));
//        }


	}
	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

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

int main() {
  long long int N,M;
  cin>>N>>M;
  long long int ans;
  if (N==1 && M==1) {
    ans=1;
  } else if (N==1 && M!=1) {
    ans=M-2;
  } else if (N!=1 && M==1) {
    ans=N-2;
  } else {
    ans=(N-2)*(M-2);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
def get_next(sw_prev2,sw_prev1,ox_prev1):
    
    rev_ox = {"o":"x", "x":"o"}
    rev_sw = {"S":"W", "W":"S"}
    
    sw = sw_prev2
    if sw_prev1 == "W": ox_prev1 = rev_ox[ox_prev1]
    if ox_prev1 == "x": sw = rev_sw[sw]
    
    return sw

n = int(input())
ox = input()

ans = [None] * (n+2)
for sw0,sw1 in [("S","S"),("S","W"),("W","S"),("W","W")]:
     
    ans[0] = sw0
    ans[1] = sw1
    
    for i,oxi in enumerate(ox[1:]+ox[0],1):
        ans[i+1] = get_next(ans[i-1],ans[i],oxi)
    
    if ans[0] == ans[-2] and ans[1] == ans[-1]:
        break
else:
    ans = [-1]

print("".join(map(str,ans[:n])))

Measured memory_bytes: 5620
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
int ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop//
//gcdlcm, isPrime, eratos, modinv, bitSearch, bitList, dfs, bfs, dijkstra, UnionFind, COM, digitDP//
ll i, j, k, l, m, n; ll N, M, K, H, W, L;
ll MOD = 1000000007; ll INF = 9999999999999; ll ans = 0;
vl flag, color; vll path; vl D; ll C;
//***********//
void bfs(ll now) {
	queue<ll> Q;
	Q.push(now);
	D[now] = 0;
	flag[now] = 1;
	ll u;
	while (!Q.empty()) {
		u = Q.front();
		Q.pop();
		for (ll v = 0; v < path[u].size(); v++) {
			ll next = path[u][v];
			if (flag[next] == 0) {
				D[next] = D[u] + 1;
				if (D[next] % 2 == 0) flag[next] = 1;
				else flag[next] = 2;
				Q.push(next);
			}
		}
	}
}
int main() {
	cin >> N >> M;
	flag.resize(N);
	path.resize(N);
	D.resize(N);
	vpll P(M);
	for (i = 0; i < M; i++) {
		ll a, b;
		cin >> a >> b;
		a--; b--;
		P[i] = make_pair(a, b);
		path[a].push_back(b);

		path[b].push_back(a);
	}
	bfs(0);
	ll isBG = 1;
	for (i = 0; i < M; i++) {
		//cout << P[i].first << P[i].second << endl;
		if (flag[P[i].first] == flag[P[i].second]) {
			isBG = 0;
			break;
		}
	}
	if (isBG) {
		ll B = 0, W = 0;
		for (i = 0; i < N; i++) {
			if (flag[i] == 1) B++;
			else W++;
		}
		//cout << "a";
		cout << B * W - M;
	}
	else {
		cout << N * (N - 1) / 2 - M;
	}
}

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

using namespace std;

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

const long long INF = (long long)1e18;
const long long MOD = (long long)1e9 + 7; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}

#define MAX


signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N, K;
	
	cin>>N>>K;
	
	// cout<<(N-2)*(N-1)/2<<endl;
	if(K <= (N-2)*(N-1)/2){
		
		cout<<N-1 + (N-2)*(N-1)/2-K<<endl;
		
		for(int i = 2; i <= N; i++){
			cout<<1<<" "<<i<<endl;
		}
		K = (N-2)*(N-1)/2-K;
		for(int i = 2; i <= N; i++){
			for(int j = i+1; j <= N; j++){
				if(!K) break;
				K--;
				cout<<i<<" "<<j<<endl;
			}
			if(!K) break;
		}
	} else cout<<-1<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#encoding:utf-8 No.0011 2014.11.10
w = (1..gets.chomp.to_i).to_a
gets.chomp.to_i.times do
  i,j = gets.chomp.split(/,/).map{|n| n.to_i}
  w[i-1],w[j-1] = w[j-1],w[i-1]
end

puts w

Measured memory_bytes: 6100
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
  ll n,a,ans=0;
  map<ll,ll> mp,mp2;
  cin>>n;
  rep(i,n){
     cin>>a;
     mp[-(a+i+1)]++; 
     mp2[a-(i+1)]++;
  }
  for(auto itr : mp)
    ans+=mp2[itr.first]*itr.second;
  cout<<ans;
  return 0;
}

Measured memory_bytes: 37864
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC046A
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, c;

            var word = Console.ReadLine().Split(' ');

            a = int.Parse(word[0]);
            b = int.Parse(word[1]);
            c = int.Parse(word[2]);

            if (a == b && b == c)
                Console.WriteLine("1");

            else if (a == b || b == c || a == c)

                Console.WriteLine("2");

            else
                Console.WriteLine("3");

            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}


int const INF = 1001001001;


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

vvi c(3,vi(3));
rep(i,3) rep(j,3) cin >> c[i][j];

if(c[1][0]-c[0][0] == c[1][1]-c[0][1] && c[1][1]-c[0][1] == c[1][2]-c[0][2]){
    if(c[2][0]-c[0][0] == c[2][1]-c[0][1] && c[2][1]-c[0][1] == c[2][2]-c[0][2]){
        cout << "Yes" << endl;
        return 0;
    }
}

cout << "No" << endl;


return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define VREP(s, ite) for (auto ite = s.begin(); ite != s.end(); ++ite)
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
//#define endl "\n"
#define ciosup  \
    cin.tie(0); \
    ios::sync_with_stdio(false);
#define eb emplace_back
#define vint vector<int>
constexpr ll INF = 1e9 + 7;
constexpr ll MOD = 1e9 + 7;

template <typename T>
void vecin(vector<T> &v, int n = 0)
{
    if (n == 0)
        n = v.size();
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
}
template <typename T>
void vecout(vector<T> &v, int n = 0)
{
    if (n == 0)
        n = v.size();
    for (int i = 0; i < n - 1; ++i)
    {
        cout << v[i] << " ";
    }
    cout << v[n - 1] << endl;
}

int main()
{
    int n;
    cin >> n;
    vector<pint> a(n);
    REP(i,n){
        cin >> a[i].FI;
        a[i].SE = i + 1;
    }
    sort(ALL(a));
    REP(i,n-1){
        cout << a[i].SE << " ";
    }
    cout << a[n - 1].SE << endl;
}

Measured memory_bytes: 1664
#include <stdio.h>



int main()
{
	
	int A,B,C,K;
	
	scanf("%d %d %d %d", &A, &B, &C, &K);
	
	if (A > B && A > C){
		for (int i = 1; i <= K; i++){
			A = 2*A;
		}
	}
	else if(B > A && B > C){
		for (int j = 1; j <= K; j++){
			B = 2*B;
		}
	}
	else if(C > A && C > B){
		for(int h = 1; h <= K; h++){
			C = 2*C;
		}
	}
	else{
		for (int u = 1; u <= K; u++){
			A = 2*A;
		}
	}
	
	
	printf("%d", (A + B + C));
	

	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>

using namespace std;

int main()
{
	int n, w[100001];
	long long int l, t, x[100001], y[100001];
	scanf("%d %lld %lld", &n, &l, &t);
	l=l*2;
	t=t*2;
	vector<int> i1, i2;
	int e1=0, e2=0;
	for(int i=0; i<n; i++){
		scanf("%lld %d", &x[i], &w[i]);
		x[i]=x[i]*2;
		if(w[i]==1){
			y[i]=(x[i]+t)%l;
			i1.push_back(i);
			e1=1;
		}else{
          if(x[i]+l-t>=0){
			y[i]=(x[i]+l-t)%l;
          }else{
            y[i]=(l-(-(x[i]+l-t))%l)%l;
          }
			i2.push_back(i);
			e2=1;
		}
	}
	if(e1==0 || e2==0){
		for(int i=0; i<n; i++){
			printf("%lld\n", y[i]/2);
		}
	}else if(w[0]==1){
		long long int n2=i2.size();
		long long int t0[200002];
		for(int i=1; i<=n2; i++){
			t0[i]=(x[i2[i-1]]-x[0])/2;
		}
		for(int i=n2+1; i<=2*n2; i++){
			t0[i]=(x[i2[i-n2-1]]-x[0]+l)/2;
		}
		long long int tq=t/l, tr=t%l;
		long long int k;
		for(int i=1; i<2*n2; i++){
			if(t0[i]<=tr && tr<t0[i+1]) k=i;
		}
		if(tr<t0[1]) k=0;
		if(tr>=t0[2*n2]) k=2*n2;
		k=(tq*2*n2+k)%n;
		long long int ans[100000];
		long long int y0=y[0];
		ans[k]=y0/2;
		sort(y, y+n);
		int k1;
		for(int i=0; i<n; i++){
			if(y[i]==y0)  k1=i;
		}
		if(k1==n-1 && y[0]==y0) k1=0;
		for(int i=0; i<n; i++){
			int p=i+k, q=i+k1;
			if(p>=n) p=p-n;
			if(q>=n) q=q-n;
			ans[p]=y[q]/2;
		}
		for(int i=0; i<n; i++){
			printf("%lld\n", ans[i]);
		}
	}else{
		long long int n1=i1.size();
		long long int t0[200002];
		for(int i=1; i<=n1; i++){
			t0[i]=(l-x[i1[n1-i]]+x[0])/2;
		}
		for(int i=n1+1; i<=2*n1; i++){
			t0[i]=(l-x[i1[2*n1-i]]+x[0]+l)/2;
		}
		long long int tq=t/l, tr=t%l;
		long long int k;
		for(int i=1; i<2*n1; i++){
			if(t0[i]<=tr && tr<t0[i+1]) k=n-i;
		}
		if(tr<t0[1]) k=0;
		if(tr>=t0[2*n1]) k=n-2*n1;
		k=(n+k+2*(n-n1)*tq)%n;
		long long int ans[100000];
		long long int y0=y[0];
		ans[k]=y0/2;
		sort(y, y+n);
		int k1;
		for(int i=0; i<n; i++){
			if(y[i]==y0){
				k1=i;
				break;
			}
		}
		if(k1==0 && y[n-1]==y0) k1=n-1;
		for(int i=0; i<n; i++){
			int p=i+k, q=i+k1;
			if(p>=n) p=p-n;
			if(q>=n) q=q-n;
			ans[p]=y[q]/2;
		}
		for(int i=0; i<n; i++){
			printf("%lld\n", ans[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 5196
#include"bits/stdc++.h"
#define REP(i,n)  for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n) for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n) for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)for(ll i=(n);i>0;--i)
#define ALL(obj)  (obj).begin(),(obj).end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
template<typename T>using pqg=priority_queue<T,vector<T>,greater<T>>;
constexpr auto inf=static_cast<ll>(1e18);
template<typename T=ll>inline T in(){T ret;cin>>ret;return ret;}
template<typename T=ll>inline vector<vector<T>>vec2(size_t h,size_t w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}
inline void setp(int n){cout<<fixed<<setprecision(n);}
inline void delnl(){cin.ignore(numeric_limits<streamsize>::max(),'\n');}

int main()
{
    ll n=in();
    double ar=0;
    REP(i,n)ar+=1/in<double>();
    setp(20);
    cout<<1/ar<<endl;
}

Measured memory_bytes: 256
s = raw_input()
bls = [False for _ in range(4)]
for c in s:
    if c == 'N':
        bls[0] = True
    elif c == 'E':
        bls[1] = True
    elif c == 'W':
        bls[2] = True
    elif c == 'S':
        bls[3] = True
if bls[0] == bls[3] and bls[1] == bls[2]:
    print 'Yes'
else:
    print 'No'


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



int main()
{
	int X, A, B;
	cin >> X >> A >> B;
	if (A >= B)
	{
		cout << "delicious";
	}
	else if (B-A <= X)
	{
		cout << "safe";
	}
	else
	{
		cout << "dangerous";
	}
	return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9;

int mp[100];

int nex (char x) {
    int y = x - 'a';
    for (int i = y; i < 26; i++)
        if (mp[i] == 0)
            return i;
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++)
        mp[s[i] - 'a'] ++;

    if (n < 26) {
        cout << s;
        for (int i = 0; i < 26; i++)
            if (mp[i] == 0)
                return cout << char (i + 'a') << endl, 0;
    }
    for (int i = n - 1; i >= 0; i--) {
        if (nex (s[i]) != -1) {
            for (int j = 0; j < i; j++)
                cout << s[j];
            cout << char (nex (s[i]) + 'a') << endl;
            return 0;
        }
        mp[s[i] - 'a'] --;
    }
    cout << -1 << endl;
}

Measured memory_bytes: 888
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
 long long int n,a[5];
 long long int ans=0;
 scanf("%lld",&n); 
for(int i=0;i<5;i++)
 {
 scanf("%lld",&a[i]);
 }
 long long int z=n;
 for(int i=0;i<5;i++)
 {
  if(z%a[i]==0){ans=ans+z/a[i];}
  else {ans=ans+z/a[i]+1;}
  if(i<=3){z=n-(ans-i-1)*a[i+1];}
  if(z<=0){z=1;}
  }
 printf("%lld\n",ans);
}


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

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

    int N;
    cin >> N;
    vector<int> B(N - 1);
    for (int i = 0; i < N - 1; i++) {
        cin >> B[i];
    }
    long long ans = 0;
    ans += B[0];
    for (int i = 1; i < B.size(); i++) {
        ans += min(B[i - 1], B[i]);
    }
    ans += B[B.size() - 1];
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll inf=(1ll<<61);
const int MX=3e5+9;
ll a,b;
int main(){
    cin>>a>>b;
    a*=b;
    if(a%2)puts("Odd");
    else puts("Even");
}

Measured memory_bytes: 768
#include<stdio.h>
#define N 100
int main(){
  int i,j,A[N],minj,a,n,count=0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&A[i]);
    }
    
    for(i=0;i<n;i++){
        minj = i;	
	for(j=i;j<n;j++){
	  if(A[j]<A[minj])   minj=j;
	}
	  a=A[i];
	  A[i]=A[minj];
	  A[minj]=a;
	  if(A[i]!=A[minj]) count++;
	
    }
    
     for(j=0;j<n-1;j++){
        printf("%d ",A[j]);
    }
    printf("%d\n",A[n-1]);
    printf("%d\n",count);
    return 0;
    
}



Measured memory_bytes: 2056
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn main() {
    let nk: Vec<u64> = read_vec();
    let n = nk[0];
    let k = nk[1];

    if k == 0 {
        println!("{}", n * n);
    } else {
        let mut ans: u64 = 0;
        for b in (k + 1)..(n + 1) {
            let qn = n / b;
            let rn = n % b;
            if rn == 0 || rn < k {
                ans += qn * (b - k);
            } else {
                ans += qn * (b - k) + rn - k + 1;
            }
        }
        println!("{}", ans);
    }
}


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

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

	for (int i = 0; i < k; i++) {
		if (max(a, max(b, c)) == a) a *= 2;
		else if (max(a, max(b, c)) == b) b *= 2;
		else c *= 2;
	}
	
	cout << a + b + c << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int maxSum = 0;
		for (int i = 0; i < n; i++) {
			maxSum += sc.nextInt() - 1;
		}

		System.out.println(maxSum);

		sc.close();
	}
}


Measured memory_bytes: 25816
#include <stdio.h>
#define MAX 250
int main(){
  int i, n, H[MAX+1];
  scanf("%d",&n);
  for ( i = 1 ; i <=n ; i++) {
    scanf("%d",&H[i]);
  }
  for( i=1 ; i<=n ; i++ ){
    printf("node %d: key = %d, ", i, H[i]);
    if(parent(i)>0){
      printf("parent key = %d, ",H[parent(i)]);
    }
    if(left(i)<=n){
      printf("left key = %d, ",H[left(i)]);
    }
    if(right(i)<=n){
      printf("right key = %d, ",H[right(i)]);
    }
      printf("\n");
  }
  
  return 0;
}
 
int parent(int i){
  return i/2;
}
 
int left(int i){
  return 2*i;
}
  
int right(int i){
  return 2*i + 1;
}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll> > P3;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-10;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

ll dp[1005][1005];

int main() {
    int w, h;
    string s[1005];
    cin >> h >> w;
    REP(i,h) cin >> s[i];
    dp[0][0] = 1;
    REP(i,h){
        REP(j,w){
            dp[i][j] %= MOD;
            if(i+1<h && s[i+1][j]!='#') dp[i+1][j] += dp[i][j];
            if(j+1<w && s[i][j+1]!='#') dp[i][j+1] += dp[i][j];
        }
    }
    cout << dp[h-1][w-1]%MOD << endl;
    return 0;
}


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

#define ST_ARR_LEN(array) (sizeof(array)/sizeof(*array))
#define MOD 1000000007

using namespace std;

using ll = long long;
const ll MAX = LLONG_MAX;
const ll MIN = LLONG_MIN;

typedef stack<ll> llStack;
typedef queue<ll> llQueue;
typedef vector<ll> llVector;
typedef list<ll> llList;

typedef struct S{
  int a;
  int b;
} Object;

int main(){
  ll A, B, C, K;
  cin >> A >> B >> C >> K;
  
  ll ans;
  if(A > K){
    ans = K;
  }else if(K <= A+B){
    ans = A;
  }else{
    ans = A-(K-A-B);
  }
  
  
  cout << ans << endl;
}


Measured memory_bytes: 3640
#include<stdio.h>
int main(void)
{
	int a,b,c,d,e;
	scanf("%d",&a);
	b = a/3600;
	c =a%3600;
	d =c/60;
	e =c%60;
	printf("%d:%d:%d\n",b,d,e);
	return 0;
}

Measured memory_bytes: 592
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void p(vector<int> A){rep(i,A.size()){cout << A[i] << " ";}cout << "\n";}

int f(char s){
    int cnt = 0;
    string d = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    rep(i,d.size()){
        cnt++;
        if(d[i] == s)return cnt;
    }
    //return;
}

int main(){
    int n;
    string s;
    cin >> n >> s;
    string alp = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string ans = "";
    rep(i,s.size()){
        ans += alp[f(s[i])+n-1];
    }
    cout << ans;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define db long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
 
#define PB push_back
#define MK make_pair
#define LB lower_bound
#define UB upper_bound
#define EB emplace_back
#define fi first
#define se second
 
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define UPD(x,y) (((x)+=(y))>=mo?x-=mo:233)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
 
#define LS3 k*2,l,mid
#define RS3 k*2+1,mid+1,r
#define LS5 k*2,l,mid,x,y
#define RS5 k*2+1,mid+1,r,x,y
#define GET pushdown(k);int mid=(l+r)/2
 
#define INF ((1ll<<60)-233)
#define sqr(x) ((x)*(x))
#define debug puts("wzpkking")
#define N M
using namespace std;
const int N=500005;
int deg[N],p[N],q[N],n,k;
int ans[N],mx[N*4];
priority_queue<pii,vector<pii >,greater<pii > > que;
vector<int> e[N];
void change(int k,int l,int r,int p,int v){
	mx[k]=max(mx[k],v);
	if (l==r) return;
	int mid=(l+r)/2;
	if (p<=mid) change(k*2,l,mid,p,v);
	else change(k*2+1,mid+1,r,p,v);
}
int ask(int k,int l,int r,int x,int y){
	if (x>y) return 0;
	if (l==x&&r==y) return mx[k];
	int mid=(l+r)/2;
	if (y<=mid) return ask(k*2,l,mid,x,y);
	if (x>mid) return ask(k*2+1,mid+1,r,x,y);
	return max(ask(k*2,l,mid,x,mid),
			   ask(k*2+1,mid+1,r,mid+1,y));
}
int main(){
	scanf("%d%d",&n,&k);
	For(i,1,n) scanf("%d",&p[i]),q[p[i]]=i;
	For(i,1,n){
		int v=ask(1,1,n,q[i]+1,min(n,q[i]+k-1));
		if (v) e[v].PB(i),deg[i]++;
		change(1,1,n,q[i],i);
	}
	For(i,1,n) if (!deg[i])
		que.push(pii(q[i],i));
	while (!que.empty()){
		int x=que.top().se; que.pop();
		for (int i:e[x]) if (!--deg[i])
			que.push(pii(q[i],i));
		ans[++*ans]=x;
	}
	For(i,1,*ans) p[q[ans[i]]]=i;
	For(i,1,n) printf("%d\n",p[i]);
}

Measured memory_bytes: 44416
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 110;
const int maxw = 100100;
ll dp[maxn][maxw], n, w;
ll weight[maxn], value[maxn];

int main() {
    cin>>n>>w;
    for(int i=1;i<=n;i++) {
        cin>>weight[i]>>value[i];
    }
    ll result = 0LL;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=w;j++) {
            dp[i][j] = dp[i-1][j];
            if(j - weight[i] >= 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-weight[i]] + value[i]);
            }
            result = max(result, dp[i][j]);
        }
    }
    cout<<result<<"\n";
    return 0;
}

Measured memory_bytes: 79360
numbers =input().rstrip().split(" ")
a =int(numbers[0])
b =int(numbers[1])
values =[0,0,0]
values[0]=a+b
values[1]=a-b
values[2]=a*b
#print(values)
ranking =sorted(values ,reverse=True)
#print(ranking)
print(ranking[0])

Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
8 3
ACACTACG
3 7
2 3
1 8
'''

test_data2 = '''\
8 7
ACACAACG
1 2
1 4
1 3
2 4
2 7
1 7
1 8
'''

test_data3 = '''\

'''
td_num=1

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,q=map(int,f.readline().split())
        s=str(f.readline())
        l=[0]*q
        r=[0]*q
        for i in range(q):            
            l[i],r[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input code ---------------------------------------
        
        n,q=map(int,input().split())
        s=str(input())
        l=[0]*q
        r=[0]*q
        for i in range(q):            
            l[i],r[i]=map(int,input().split())
        # End Input code ---------------------------------------

pre=0
ac=[0]*n
for i in range(1,n):
    if s[i-1:i+1]=='AC':
        ac[i]=pre+1
    else:
        ac[i]=pre
    pre=ac[i]
    
#print('n,q,s,l,r=',n,q,s,l,r)
#print('ac',ac)
for i in range(q):
    print(ac[r[i]-1]-ac[l[i]-1])


Measured memory_bytes: 54104
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define PI 3.14159265358979323846264
#define pii pair <int, int>
#define pipii pair <int, pair <int, int> > 
#define piipi pair <pair <int, int>, int>
#define pb push_back
#define mp make_pair
#define vi vector <int>
#define vl vector <long long>
#define vpii vector <pair <int, int> >
#define ll long long
#define fi first
#define se second
#define FOR(i, x, y) for (int i=x; i<=y; i++)
#define FORD(i, y, x) for (int i=y; i>=x; i--)
#define debug printf("OK\n")
int n, ans;
int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        int cnt = 0;
        int k = i;
        while (k) {
            k /= 10;
            cnt++;
        }
        if (cnt%2) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define ar array
#define pii pair<int, int>

const int N = 1e7 + 5;
int cnt[N];

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j += i) cnt[j]++;
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) ans += 1ll * i * cnt[i];
    cout << ans << '\n';
}

Measured memory_bytes: 42664
// Created by Davidia on 2018-12-17.
//

// copyright@ Dr. Davidia


#include <bits/stdc++.h>

using namespace std;


int main(){
    int n; cin >> n;
    vector<vector<int>> dp (n,vector<int>(3));
    cin >> dp.at(0).at(0) >> dp.at(0).at(1) >> dp.at(0).at(2);
    for (int i = 1; i < n; i++){
        int a,b,c; scanf(" %d %d %d", &a ,&b, &c);
        dp.at(i).at(0) = max(dp.at(i-1).at(1), dp.at(i-1).at(2)) + a;
        dp.at(i).at(1) = max(dp.at(i-1).at(0), dp.at(i-1).at(2)) + b;
        dp.at(i).at(2) = max(dp.at(i-1).at(0), dp.at(i-1).at(1)) + c;
    }
    cout << max(dp.at(n-1).at(0), max(dp.at(n-1).at(1), dp.at(n-1).at(2))) << '\n';

    return 0;
}

Measured memory_bytes: 5760
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int ans = 0;
        for (int i = 0; i < s.length()/2; i++) {
            if(s.charAt(i) != s.charAt(s.length()-i-1)) ans++;
        }
        System.out.println(ans);
        sc.close();

    }

}


Measured memory_bytes: 24020
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,string> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const int INF=1000000001;
const double PI=3.141592653589;
const ll LMAX=1000000000000001;


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

  vector<P> p(m);

  rep(i,m) cin>>p[i].fs>>p[i].sc;
  vector<int> w(n,0);
  set<int> se;

  int AC=0;
  int WA=0;

  rep(i,m){

    if(se.count(p[i].fs)) continue;
    else{
      if(p[i].sc=="AC"){
        // ac=1;
        se.insert(p[i].fs);
      }else if(p[i].sc=="WA"){
        w[p[i].fs-1]++;
        // cout<<"a"<<endl;
      }
    }
  }
  rep(i,n){
    if(se.count(i+1)){
      WA+=w[i];
    }
  }
  // if(ac){
  //   AC++;
  //   WA+=wa;
  // }
  cout<<se.size()<<" "<<WA<<endl;

  return 0;
}


Measured memory_bytes: 11520
#include<iostream>
#include<cstdio>

using namespace std;

char C[2][3] ;
char D[2][3] ;

int main(void){
	
	for(int i = 0 ; i < 2; i++){
		for(int j = 0; j < 3; j++){
			cin >> C[i][j] ;
		}
	}
	D[0][0] = C[1][2] ;
	D[0][1] = C[1][1] ;
	D[0][2] = C[1][0] ;
	D[1][0] = C[0][2] ;
	D[1][1] = C[0][1] ;
	D[1][2] = C[0][0] ;
	
/*	for(int i = 0; i < 2 ; i++){
		for(int j = 0; j < 3 ; j++){
			cout << C[i][j] ; 
		}
		cout << endl ;
	} */
	
	bool flag = true  ;
	
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 3; j++){
			if(D[i][j] != C[i][j]) flag = false ;
		}
	}
	
	if(flag) cout << "YES" << endl;
	else cout << "NO" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>

using namespace std;

int pou[12] = {0};


int dfs(int nau,int b,int c){
  if(nau == 11) return 1;
  if(pou[nau-1] > b){
    if( dfs(nau+1,pou[nau-1],c) == 1){
      return 1;
    }
  }

  if(pou[nau-1] > c){
    if( dfs(nau+1,b,pou[nau-1])==1){
      return 1;
    }
  }

  return 0;
}



int main(){

  int n=0;

  scanf("%d",&n);

  for(int i = 0;i < n;i++){

    for(int j = 0;j < 10;j++){
      scanf("%d",&pou[j]);
    }

    if(dfs(1,0,0) == 1){
      printf("YES\n");
    }else{
      puts("NO");
    }
  }
  return 0;
}


Measured memory_bytes: 1168
n = int(input())
a = sorted(list(map(int,input().split())))
def runlength(S):
    ans = []
    for s in S:
        if len(ans) == 0 or ans[-1][0] != s:
            ans.append([s,1])
        else:
            ans[-1][1] += 1
    return ans
a = runlength(a)
ans = 0
for i in range(len(a)):
  if a[i][0] < a[i][1]:
    ans += a[i][1]-a[i][0]
  elif a[i][0] > a[i][1]:
    ans += a[i][1]
print(ans)

Measured memory_bytes: 71688
N = int(input())
SP = [[0]*3 for i in range(N)]
for i in range(N):
    S,P = map(str,input().split())
    SP[i][0] = S
    SP[i][1] = int(P)*-1
    SP[i][2] = i+1
SP = sorted(SP)
for i in range(N):
	print(SP[i][2])

Measured memory_bytes: 3060
#include <cstdio>

int main()
{
	int N, A;

	while (true)
	{
		scanf("%d", &N);

		if (N == 0) { break; }

		for (int i = 0; i < 9; i++)
		{
			scanf("%d", &A);

			N -= A;
		}

		printf("%d\n", N);
	}

	return 0;
}

Measured memory_bytes: 2680
#include <algorithm>
#include <iostream>
#include <vector>

#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(a) (a).begin(), (a).end()

#define INF 1000000000

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

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

    vector<int> A(N);
    REP(i, N)
        cin >> A[i];

    vector<int> B(N), C(N);

    REP(i, N) {
        B[i] = - A[i] + i;
        C[i] = A[i] + i;
    }

    sort(ALL(B));
    sort(ALL(C));

    ll sum = 0;
    for (int i = 0; i < N; ++i) {
        auto p = equal_range(ALL(C), B[i]);

        sum += p.second - p.first;
    }
    for (int i = 0; i < N; ++i) {
        auto p = equal_range(ALL(B), C[i]);

        sum += p.second - p.first;
    }

    cout << sum / 2 << endl;

    return 0;
}


Measured memory_bytes: 5584