akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;
@SuppressWarnings("unchecked")
class Main {
	static int[] visited;
	static LinkedList<Integer>[] graph;

	public static void solve(int[] distance){
		int[] marks = new int[distance.length];
		Queue<Integer> q = new LinkedList<>();
		q.add(1);
		int[] visited = new int[distance.length];
		visited[1] = 1;
		while(!q.isEmpty()){
			int poll = q.poll();
			//System.out.print(poll + "-> ");
			for(int child : graph[poll]){
				if(distance[child] == 0){
					distance[child] = distance[poll]+1;
					visited[poll] = 1;
					  marks[child] = poll;
   
					q.add(child);
				}
			}
		}		

		//System.out.print(Arrays.toString(distance));
	 System.out.println("Yes");
    for(int i = 2; i < visited.length; i++){
      System.out.println(marks[i]);
    }

	}


	public static void main(String[] args) throws Exception {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     	 String[] in = br.readLine().trim().split(" ");
		int n = Integer.parseInt(in[0]);
		n = n+1;
		int e = Integer.parseInt(in[1]);
		graph = new LinkedList[n];
		for(int i = 0; i < n; i++)
			graph[i] = new LinkedList<Integer>();



		for(int i = 0;i<e;i++){
			in = br.readLine().trim().split(" ");
			int a = Integer.parseInt(in[0]);
			int b = Integer.parseInt(in[1]);
			graph[a].add(b);
			graph[b].add(a);


}


		int[] visited = new int[n];
          solve(visited);


   

	}
}

Measured memory_bytes: 77120
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>

using namespace std;

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

long int gcd(long int x, long int y){
    if (y == 0){
        return x;
    }
    
    return gcd(y, x % y);
}

long int lcm(long int x, long int y){
    
    return (x / gcd(x, y)) * y; 
}

int main(){
    long int n;
    cin >> n;
    long int t[n];
    rep(i, n) cin >> t[i];
    long int ans = t[0];
    rep(i, n - 1){
        ans = lcm(ans, t[i+1]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

int main(){
    ll k;
    cin >> k;
    ll n = 50;
    vector<ll> a(n);
    vector<ll> cnt(n);
    ll p =  k / n;
    for(int i=0;i<(k%n);i++){
        cnt[i] = p + 1;
    }
    for(int i=k%n;i<n;i++){
        cnt[i] = p;
    }
    rep(i,n){
        a[i] = (cnt[i]+1)*n-k+cnt[i]-1LL;
    }
    cout << n << endl;
    rep(i,n) cout << a[i] << " " ;
    cout << endl;
    return 0;
}

Measured memory_bytes: 3600
N = int(input())
X = [0] * N
ans = 0
for i in range(N-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    if x > y: x, y = y, x
    ans += (y - x) * (N - y + x + 1)
    X[x] += 1
    X[y] += 1
for i, x in enumerate(X):
    ans += (i + 1) * (N - i) * (2 - x)
print(ans // 2)

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

int ds[100009];

int uf(int n)
{
	if (ds[n] == n) return n;
	return ds[n] = uf(ds[n]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++)
		ds[i] = i;
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		ds[uf(a)] = uf(b);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (ds[i] == i)
			ans++;
	cout << ans << '\n';
	return 0;
}	

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int Y = sc.nextInt();

		int leg = 0;
		String ans = "No";

		for (int t=0; t<X+1; t++) {
			leg = 2*t + 4*(X-t);
			if (leg==Y) {
				ans="Yes";
				break;
			}
		}

		if (ans=="Yes") {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}


	}

}

Measured memory_bytes: 27064
#include <cstdio>
#include <vector>
#include <cstring>
#define N 100005
using namespace std;
int n, m, a, b, q, v[N], d[N], c[N], ans[N], memo[N];
vector<int> g[N];

void f(int p, int q, int r) {
	if(q<0 || q<=memo[p]) return;
	memo[p] = q;
	if(!ans[p]) ans[p] = r;
	for(int i=0; i<g[p].size(); i++) {
		f(g[p][i], q-1, r);
	}
}

int main() {
	int i;
	scanf("%d%d", &n, &m);
	while(m--) {
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	scanf("%d", &q);
	for(i=0; i<q; i++) scanf("%d%d%d", v+i, d+i, c+i);
	memset(memo, -1, sizeof(memo));
	for(i=q-1; i>=0; i--) {
		f(v[i], d[i], c[i]);
	}
	for(i=1; i<=n; i++) printf("%d\n", ans[i]);
	return 0;
}

Measured memory_bytes: 8440
from itertools import permutations
n,n_color = map(int,input().split())
change_cost = [list(map(int, input().split())) for i in range(n_color)]
color_grid = [list(map(int, input().split())) for i in range(n)]

mod0_colors = [0] * n_color
mod1_colors = [0] * n_color
mod2_colors = [0] * n_color
for y in range(n):
    for x in range(n):
        color = color_grid[y][x]-1
        if (y+x+2) % 3 == 0:
            mod0_colors[color]+= 1
        elif (y+x+2) % 3 == 1:
            mod1_colors[color]+= 1
        else:
            mod2_colors[color]+= 1

mod2color_cost = [[0]*n_color for _ in range(3)]
for mod,mod_colors in enumerate([mod0_colors,mod1_colors,mod2_colors]):
    for color_to in range(n_color):
        total_cost = 0
        for color_from in range(n_color):
            cost_per_node = change_cost[color_from][color_to]
            n_node = mod_colors[color_from]
            total_cost += n_node*cost_per_node
        mod2color_cost[mod][color_to] = total_cost

ans = float('inf')
for pettern in permutations([i for i in range(n_color)],3):
    total_cost = 0
    for from_ in range(3):
        to = pettern[from_]
        total_cost += mod2color_cost[from_][to]
    ans = min(ans, total_cost)
print(ans)

Measured memory_bytes: 11652
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
using namespace std;
int main(){

    // Seiranchan!
     int a,b,c;
     cin >> a >> b >>c;

     REP(i,c){
         if(i%2==0){
         if(a%2!=0){
             a -=1;;

             a /=2;
             b +=a;
         }else{
             a =a/2;
             b=a+b;
         }
         }
         if(i%2==1){
             if(b%2!=0){
                 b=b-1;
                 b = b/2;
                 a = a+b;
             }else{
                b = b/2;
                a=b+a;
             }
         }
     }

     cout << a << " " << b<<endl;
}



Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int keep;
		int n4=0;
		int n2=0;
		for(int i=0;i<n;i++){
			keep=sc.nextInt();
			if(keep%4==0){
				n4++;
			}
			else if(keep%2==0){
				n2++;
			}
		}
		if(n/2<=n4||n2>=n-2*n4){
			System.out.println("Yes");
		}
		else{
			System.out.println("No");
		}
	}
}

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

int b[8][8] = {{0}};  // b = block

    bool isA(int i, int j){
        if(i + 1 < 8 && j + 1 < 8){
            if(b[i][j] == 1 && b[i][j + 1] == 1 && b[i + 1][j] == 1 && b[i + 1][j + 1] == 1) 
                return true;
        }
        return false;
    }

    bool isB(int i, int j){
        if(i + 3 < 8 && j < 8){
            if(b[i][j] == 1 && b[i + 1][j] == 1 && b[i + 2][j] == 1 && b[i + 3][j] == 1)
                return true;
        }
        return false;
    }

    bool isC(int i, int j){
        if(i< 8 && j + 3 < 8){
            if(b[i][j] == 1 && b[i][j + 1] == 1 && b[i][j + 2] == 1 && b[i][j + 3] == 1)
                return true;
        }
        return false; 
    }

    bool isD(int i, int j){
        if(i + 2 < 8 && j - 1 >= 0){
            if(b[i][j] == 1 && b[i + 1][j] == 1 && b[i + 1][j - 1] == 1 && b[i + 2][j - 1] == 1)
                return true;
        }
        return false;
    }

    bool isE(int i, int j){
        if(i + 1 < 8 && j + 2 < 8){
            if(b[i][j] == 1 && b[i][j + 1] == 1 && b[i + 1][j + 1] == 1 && b[i + 1][j + 2] == 1)
                return true;
        }
        return false;
    }

    bool isF(int i, int j){
        if(i + 2 < 8 && j + 1 < 8){
            if(b[i][j] == 1 && b[i + 1][j] == 1 && b[i + 1][j + 1] == 1 && b[i + 2][j + 1] == 1)
                return true;
        }
        return false;
    }

    bool isG(int i, int j){
        if(i + 1 < 8 &&  j - 1 >= 0 && j + 1 < 8){
            if(b[i][j] == 1 && b[i][j + 1] == 1 && b[i + 1][j] == 1 && b[i + 1][j - 1] == 1)
                return true;
        }
        return false;
    }

int main(void){
    int i, j;

    string str;
    while(true) {
        for(i=0; i < 8; i++) {
            if(!(cin >> str)) {
                return 0;
            }
            for(j=0; j < 8; j++) {
                b[i][j] = str[j] == '1' ? 1 : 0;
                //cout << b[i][j]; 
            }
            //cout << endl;
        }
        for(i = 0; i < 8; i++){
            for(j = 0; j < 8; j++){
                //output
                if(b[i][j] == 1){
                    if(isA(i, j)) cout << "A" << endl;
                    if(isB(i, j)) cout << "B" << endl;
                    if(isC(i, j)) cout << "C" << endl;
                    if(isD(i, j)) cout << "D" << endl;
                    if(isE(i, j)) cout << "E" << endl;
                    if(isF(i, j)) cout << "F" << endl;
                    if(isG(i, j)) cout << "G" << endl;
                }  
            }
        }
    }

/**
    char b[8];
    std str;
    for(i = 0; i < 8; i++){
        cin >> b[i];
        str = std::to_string(b[i]);
    }
    for(i = 0; i < 8; i++){
        cout << str << endl;
    }*/
    

}


Measured memory_bytes: 3060
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <tuple>
using namespace std;
int main(void){
  int N,M,C;
  cin>>N>>M>>C;
  int B[M];
  for(int i=0;i<M;i++){
      cin>>B[i];
  }
  int A[N][M];
  for(int i=0;i<N;i++){
      for(int j=0;j<M;j++){
          cin>>A[i][j];
      }
  }
  int ans=0;
  for(int i=0;i<N;i++){
      int sum=0;
      for(int j=0;j<M;j++){
         sum+=B[j]*A[i][j];
      }
      sum+=C;
      if(sum>0){ans++;}
  }
  cout<<ans;
  return 0;
}


Measured memory_bytes: 256
S=input()
N=len(S)
K,I,H,B,R=S.find('K'),S.find('I'),S.find('H'),S.find('B'),S.find('R')
f = (K==0 or K==1) and K==I-1==H-2 and (H+1==B or S[H+1]=='A') and (B+1==R or S[B+1]=='A') and (R==N-2 and S[R+1]=='A' or R==N-1)
T='AKIHABARA'
i=0;j=0;g=True
while 1:
    if S[i]==T[j]:i+=1;j+=1
    elif T[j]=='A':j+=1
    else:g=False;break
    if i==len(S):break
    elif j==9:g=False;break
print('YES'if f and g else 'NO')

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

int main()
{
	ll n, a, b, sum = 0;
	cin >> n >> a >> b;
	sum += n / (a + b) * a;
	if (n % (a + b) <= a)	sum += n % (a + b);
	else	sum += a;
	cout << sum;
	return 0;
 } 

Measured memory_bytes: 256
from bisect import bisect_left,bisect_right
a,b,q=map(int,input().split())
INF=float("inf")
s=[-INF]+[int(input())for i in range(a)]+[INF]
t=[-INF]+[int(input())for i in range(b)]+[INF]
for _ in range(q):
  x=int(input())
  b,c=bisect_right(s,x),bisect_right(t,x)
  a=INF
  for i in [s[b-1],s[b]]:
    for j in [t[c-1],t[c]]:
      a=min(a,abs(x-i)+abs(i-j),abs(x-j)+abs(j-i))
  print(a)

Measured memory_bytes: 14096
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define ld long double
#define uns unsigned
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpii vector<pii>
#define gr vector<vpii>
#define str string
#define mask vector<bool>
#define vs vector<str>
#define pq priority_queue
#define ordered_set_of(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
#define fi first
#define se second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define nub(x) x.resize(unique(all(x)) - x.begin())
#define TWO class T1, class T2
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define GAME_OVER return 0
using namespace std;
using namespace __gnu_pbds;
char _$ = ' ';
struct sep {sep(char c) {_$ = c;}};
ostream& operator<<(ostream& o, sep s) {return o;}
template<TWO> ostream& operator<<(ostream& o, pair<T1, T2> x) {return o << x.fi << ' ' << x.se;}
template<TWO> istream& operator>>(istream& i, pair<T1, T2>& x) {return i >> x.fi >> x.se;}
template<class T> ostream& operator<<(ostream& o, vector<T> x) {for (auto it : x) o << it << _$; return o;}
template<class T> istream& operator>>(istream& i, vector<T>& x) {for (auto& it : x) i >> it; return i;}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    str s;
    cin >> s;
    if (s[0] == '7' || s[1] == '7' || s[2] == '7')
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    GAME_OVER;
}

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

int main(){
  int n;
  long long int k,count=0;
  cin >> n >> k;
  vector<int> a(n),b(n);
  vector<long long int> c(100001,0);
  for(int i=0;i<n;i++)cin >> a.at(i) >> b.at(i);
  for(int i=0;i<n;i++)c.at(a.at(i))+=b.at(i);
  for(int i=1;i<100001;i++){
    count += c.at(i);
    if(count >= k){
      cout << i << endl;
      break;
    }
  }
}


Measured memory_bytes: 1792
import java.util.*;

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

        long x = sc.nextLong();
        long n = 100;

        long count = 0;
        while(n < x){
            n += n / 100;
            count++;
        }
        System.out.println(count);

    }
}


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

int main()
{
  int x, y;
  cin >> x >> y;
  if((x == 1 || x == 3 || x == 5 || x == 7 || x == 8 || x == 10 || x == 12) && (y == 1 || y == 3 || y == 5 || y == 7 || y == 8 || y == 10 || y == 12))
  {
    cout << "Yes" << endl;
  }
  else if((x == 4 || x == 6 || x == 9 || x == 11) && (y == 4 || y == 6 || y == 9 || y == 11))
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ti,mi,se,sammin,thrti,afh,afm,afs;
    while(cin>>ti>>mi>>se&&ti!=-1&&mi!=-1&&se!=-1){
        sammin=120*60-(ti*3600+mi*60+se);
        afh=sammin/3600;afm=sammin%3600/60;afs=sammin%3600%60;
        thrti=sammin*3;
        printf("%0.2d:%0.2d:%0.2d\n",afh,afm,afs);
        afh=thrti/3600;afm=thrti%3600/60;afs=thrti%3600%60;
        printf("%0.2d:%0.2d:%0.2d\n",afh,afm,afs);
    }
}

Measured memory_bytes: 1160
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	s := getNextString(scanner)
	fmt.Fprintln(writer, solve(s))

	writer.Flush()
}

func solve(s string) string {
	var index [26]int

	for i := 0; i < 26; i++ {
		index[i] = -3
	}
	n := len(s)
	for i := 0; i < n; i++ {
		if i-index[s[i]-'a'] <= 2 {
			return fmt.Sprintf("%d %d", index[s[i]-'a']+1, i+1)
		}
		index[s[i]-'a'] = i
	}
	return "-1 -1"
}


Measured memory_bytes: 896
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
typedef vector<int> vi;
typedef vector<ll> vl;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define IN cin >> 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (m-1); i >= (int)(n); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
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; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////


int main(){

    int n;
    cin >> n;
    int ans = 0;
    rep(i,0,n){
        char c;
        cin >> c;
        if(c == 'R')ans++;
        else ans--;
    }
    if(ans > 0)Yes;
    else No;
    
	return  0;
}

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

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

    int dif = 0;
    for(int i = 0; i < n-1; i++){
        if (s[i] != s[i+1])dif++;
    }

    int aftdif;
    if (dif >= k*2)aftdif = dif - k*2;
    else aftdif = 0;
    int ans = n - 1 - aftdif;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3292
from itertools import accumulate
N, M = map(int, input().split())
A = list(map(int, input().split()))

B = [0] + A
C = {}
B = list(accumulate(B))
for i in range(1, len(B)):
    if B[i]%M not in C:
        C[B[i]%M] = 1
    else:
        C[B[i]%M] += 1
ans = 0
for i in C.values():
    ans += i*(i-1)//2
if 0 in C:
    ans += C[0]
print(ans)

Measured memory_bytes: 17748
#include<stdio.h>
#define MAX 2000000

int H,A[MAX+1];

int parent(int i) { return i/2; }
int left(int i) { return i*2; }
int right(int i) { return i*2+1; }
void maxHeapify(int);
void buildMaxHeap();

int main()
{
  int i;
  
  scanf("%d",&H);
  for(i=1;i<=H;i++){
    scanf("%d",&A[i]);
  }

  buildMaxHeap();
  
   for(i=1;i<=H;i++){
    printf(" %d",A[i]);
  }
   printf("\n");
   
  return 0;
}

void maxHeapify(int i)
{
  int largest;
  int l = left(i);
  int r = right(i);
  int x;
  //自分、左の子、右の子の中から値が最大ノードを選ぶ
  if( l <= H && A[l] > A[i] ) largest = l;
  else largest = i;
  if( r <= H && A[r] > A[largest] ) largest = r;

  if(largest != i){ //iの子の方が値が大きい場合
    //printf("yes\n");
    x = A[i];
    A[i] = A[largest];
    A[largest] = x;
    maxHeapify(largest); //再帰的に呼び出し
  }
}

void buildMaxHeap()
{
  int i;
  for(i=H/2;i>=1;i--){
    maxHeapify(i);
  }
}



Measured memory_bytes: 3808
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#include <utility>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<pair<int,int> > A;
  int a;
  for(int i = 0; i < N; ++i){
    cin >> a;
    A.push_back(make_pair(a,i));
  }
  sort(A.begin(),A.end());
  set<int> s;
  s.insert(-1);
  s.insert(N);
  long long int ans = 0LL;
  for(int i = 0; i < N; ++i){
    int id = A[i].second;
    s.insert(id);
    set<int>::iterator u = s.find(id), l = u;
    ++u;
    --l;
    ans += (long long int)(*u - id)*(id - (*l))*A[i].first;
    s.insert(id);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11248
from collections import Counter


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


n = int(input())
pf = prime_factorize(n)
c = Counter(pf)

ans = 0
for v in c.values():
    i = 1
    while v > 0:
        v -= i
        i += 1
        if v >= 0:
            ans += 1

print(ans)

Measured memory_bytes: 65728
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

inline long long read()
{
    char c;long long out=0,f=1;
    for (c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    if (c=='-'){f=-1;c=getchar();}
    for (;c>='0'&&c<='9';c=getchar()){out=(out<<3)+(out<<1)+c-'0';}
    return out*f;
}
void write(long long x)
{
	if (x<0){putchar('-');write(-x);return;}
    if (x>9){write(x/10);}
	putchar(x%10+'0');
}

void work(int a);

long long n,x,ans,f[60],g[60];

int main()
{
	int i;
	
	cin>>n>>x;
	
	f[0]=g[0]=1;
	
	for (i=1;i<=n;++i)
	{
		f[i]=f[i-1]*2+3;
		g[i]=g[i-1]*2+1;
	}
	
	work(n);
	
	cout<<ans;
	
	return 0;
}

void work(int a)
{
	if (x==0)
	{
		return;
	}
	if (a==0)
	{
		--x;
		++ans;
	}
	else if (x>=f[a])
	{
		x-=f[a];
		ans+=g[a];
	}
	else if (x<=f[a-1]+1)
	{
		--x;
		work(a-1);
	}
	else
	{
		x-=f[a-1]+2;
		ans+=g[a-1]+1;
		work(a-1);
	}
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int m;
    scanf("%d",&m);
    int ans = m;
    bool f = false;
    for(int i = 0 ; i < n; i++){
        int in,out;
        scanf("%d%d",&in,&out);
        if(m+in-out < 0){
            f = true;
        }
        ans = max(ans,m+in-out);
            int x = m+in-out;
            m = x;
    }

    (f) ? puts("0") : printf("%d\n",ans);

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> P;
typedef pair<P,P> L; //Line, Segment

const double EPS = 1e-8;
const double INF = 1e100;

namespace std {
  bool operator < (const P& a, const P& b){
    return fabs(real(a)-real(b)) < EPS ? imag(a) < imag(b) : real(a) < real(b);
  }
}

double dot(P a, P b){ return real(conj(a)*b); }
double cross(P a, P b){ return imag(conj(a)*b); }
int ccw(P a, P b, P c){
  b -= a;
  c -= a;
  if(cross(b,c) > EPS) return 1;
  if(cross(b,c) < -EPS) return -1;
  if(dot(b,c) < -EPS) return 2;
  if(norm(b) < norm(c)) return -2;
  return 0;
}
bool isIntersect(L s1, L s2){
  
  //ccw ??????????????????????????¨, ????????????????????´?????????????????¨??????????????????????????????
  if(max(real(s1.first), real(s1.second)) + EPS < min(real(s2.first), real(s2.second)) ||
     max(imag(s1.first), imag(s1.second)) + EPS < min(imag(s2.first), imag(s2.second)) ||
     max(real(s2.first), real(s2.second)) + EPS < min(real(s1.first), real(s1.second)) ||
     max(imag(s2.first), imag(s2.second)) + EPS < min(imag(s1.first), imag(s1.second))) return false;

  return ( ccw(s1.first,s1.second,s2.first) * ccw(s1.first,s1.second,s2.second) <= 0 &&
           ccw(s2.first,s2.second,s1.first) * ccw(s2.first,s2.second,s1.second) <= 0 );
}


int Na,Nb;
P A[1111],B[1111];

struct edge{
  int to;
  double c;
  bool operator<(const edge& e) const {
    return c > e.c;
  }
};

vector<edge> G[2][1111];
double H[1111];
double dijk(int fl){
  fill(H,H+1001,INF);
  priority_queue<edge> q;
  q.push( (edge){0,0.0} );
 while( !q.empty() ){
   edge p = q.top(); q.pop();
   int id = p.to;
    double c = p.c;
    if( H[id] < c ) continue;
    for(int i=0;i<(int)G[fl][id].size();i++){
      edge e = G[fl][id][i];
      if( H[e.to]  > e.c + c ){
	H[e.to] = e.c + c;
	q.push( (edge){e.to,H[e.to]} );
      }
    }
  }
 return H[1];
}

int main(){
  cin >> Na >> Nb;
  for(int i=0;i<Na;i++)
    cin >> A[i].real() >> A[i].imag();
  for(int i=0;i<Nb;i++)
    cin >> B[i].real() >> B[i].imag();


  L s = L(B[0],B[1]);
  for(int i=0;i<Na;i++){
    for(int j=i+1;j<Na;j++){
      L line = L(A[i],A[j]);
      if( !isIntersect( s, line ) ){
	G[0][i].push_back((edge){j,abs(A[i]-A[j])});
	G[0][j].push_back((edge){i,abs(A[i]-A[j])});
      }
    }
  }

  s = L(A[0],A[1]);
  for(int i=0;i<Nb;i++){
    for(int j=i+1;j<Nb;j++){
      L line = L(B[i],B[j]);
      if( !isIntersect( s, line ) ){
	G[1][i].push_back((edge){j,abs(B[i]-B[j])});
	G[1][j].push_back((edge){i,abs(B[i]-B[j])});
      }
    }
  }
  
  double res = min( abs(B[0]-B[1]) + dijk(0),
		    abs(A[0]-A[1]) + dijk(1) );
  if( res > INF/10 ) cout << -1 << endl;
  else printf("%.14lf\n",res);
  
}

Measured memory_bytes: 35240
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	string s;
	cin>>s;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='1')s[i]='9';
		else
		if(s[i]=='9')s[i]='1';
	}
	cout<<s;
	return 0;
} 

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc=new Scanner(System.in);
    	int n=sc.nextInt();
    	int t = 1;
    	int can = 0;
    	for(int i=0;i<n;i++) {
    		int m = sc.nextInt();
    		if(m==t) {
    			can++;
    			t++;
    		}
    	}
    	int sum = can==0?-1:n-can;
    	System.out.println(sum);
	}
}

Measured memory_bytes: 65596
#include <stdio.h>

int main()
{
	int N;
	scanf("%d",&N);
	if(N == 1){
		printf("Hello World");
	}
	if(N == 2){
		int A,B;
		scanf("%d %d",&A,&B);
		printf("%d",A+B);
	}
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>

#define MAXN 20000
int N;
int P[MAXN+5],A[MAXN+5],B[MAXN+5];

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d",&P[i]);
    for(int i=1;i<=N;i++){
        A[i]=(i-1)*N+1;
        B[i]=(N-i)*N+1;
    }
    for(int i=1;i<=N;i++)
        A[P[i]]+=i-1;
    printf("%d",A[1]);
    for(int i=2;i<=N;i++)
        printf(" %d",A[i]);
    puts("");
    printf("%d",B[1]);
    for(int i=2;i<=N;i++)
        printf(" %d",B[i]);
    puts("");
}


Measured memory_bytes: 768
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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


	int N;
	cin >> N;

	rep1(i, 9) {
		if (N % i == 0 && N / i < 10) {
			co("Yes");
			return 0;
		}
	}
	co("No");

	Would you please return 0;
}

Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        solve(System.in, System.out);
    }

    static void solve(InputStream is, PrintStream os) {
        // Your code here!
        Scanner scan = new Scanner(is);
        int N = scan.nextInt();
        int sub[] = new int[N];
        for (int i = 0; i < N-1; i++) {
            sub[scan.nextInt()-1]++;
        }

        for (int i = 0; i < N; i++)
            os.println(sub[i]);

    }
}

Measured memory_bytes: 57228
#include<bits/stdc++.h>
using namespace std;
struct UF {
  vector<int> p;
  UF(int n) : p(n) {iota(p.begin(), p.end(), 0);}
  int r(int x) {
    if (p[x] == x) return x;
    return p[x] = r(p[x]);
  }
  void m(int x, int y) {
    x = r(x); y = r(y);
    p[x] = y;
  }
};

int main() {
  int n, k, l; cin >> n >> k >> l;
  UF a(n), b(n);
  while (k--) {
    int f, t; cin >> f >> t; f--; t--;
    a.m(f, t);
  }
  while (l--) {
    int f, t; cin >> f >> t; f--; t--;
    b.m(f, t);
  }
  map<pair<int, int>, int> m;
  for (int i = 0; i < n; i++) {
    m[{a.r(i), b.r(i)}]++;
  }
  for (int i = 0; i < n; i++) {
    cout << m[{a.r(i), b.r(i)}] << endl;
  }
}

Measured memory_bytes: 13568
#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;


int main(void){
  int N=0;
  double a=0;
  //scanf("%d", &N);
  //printf("%d", N);
  cin >> N;
  
  if(N%2==0) a=0.5;
 else{
   a=(N+1)/2;
   a=a/N;
 }
  
  //int i=1;
  //for(i=1;i<=N;i++){
    //if(i % 2 == 1) oddCount++;
  //}
  
  //float answer=0;
  //answer = oddCount / N;
  printf("%f", a);
  
  return 0;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll power[200005]={0};
int main(){
  ll n,m;
  cin>>n>>m;
  ll ans=0,kans=0;
  vector<ll> num;
  for(int i=0;i<n;i++){
    ll a;
    cin>>a;
    num.push_back(a);
  }
  for(int i=0;i<n-1;i++){
    ll a=num[i],b=num[i+1];
    if(a>b) b+=m;
    power[a+2]++;
    power[b+1]--;
    ans+=b-a;
  }
  for(int i=1;i<=2*m;i++) power[i]+=power[i-1];
  for(int i=0;i<n-1;i++){
    ll a=num[i],b=num[i+1];
    if(a>b) b+=m;
    power[b+1]-=b-a-1;
  }
  for(int i=1;i<=2*m;i++) power[i]+=power[i-1];
  for(int i=1;i<=m;i++) kans=max(kans,power[i]+power[i+m]);
  cout<<ans-kans<<endl;
}


Measured memory_bytes: 2676
#include <stdio.h>

int main(void)
{
	int a,b,c;
	scanf("%d%d",&a,&b);
	if (b % a != 0) {
		c = b / a + 1;
	}
	else {
		c = b / a;
	}
	printf("%d\n",c);
	return 0;
}


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

int main(){
  int N ; 
  cin >> N ; 
  string S ;
  cin >> S ; 
  
  
  int T = S.size() ; 
  int A = 0 ; 
  
  for(int i = 0 ; i < T ; i++){
    if(S.at(i) == 'R' ){
      A++ ; 
    }
    
  }
  int P = 0 ; 
  for(int i = 0 ; i < A ; i++){
    if(S.at(i) == 'W'){
      P++ ; 
    }
  }



  cout << P << endl ; 
  
}

Measured memory_bytes: 3752
#include <stdio.h>

struct Dice{
    int num[7];
};

void throwdice(char direction,struct Dice *A){
    int temp;
    switch(direction){
        case 'N' :
            temp = A->num[1];
            A->num[1] = A->num[2];
            A->num[2] = A->num[6];
            A->num[6] = A->num[5];
            A->num[5] = temp;
            break;
        
        case 'E' :
            temp = A->num[1];
            A->num[1] = A->num[4];
            A->num[4] = A->num[6];
            A->num[6] = A->num[3];
            A->num[3] = temp;
            break;
        
        case 'W' :
            temp = A->num[1];
            A->num[1] = A->num[3];
            A->num[3] = A->num[6];
            A->num[6] = A->num[4];
            A->num[4] = temp;
            break;
            
        case 'S' :
            temp = A->num[1];
            A->num[1] = A->num[5];
            A->num[5] = A->num[6];
            A->num[6] = A->num[2];
            A->num[2] = temp;
            break;
    }
}


int main(void){
    struct Dice A;
    int i;
    char direction;
    
    for(i=1; i<=6; i++){
        scanf("%d",&A.num[i]);
    }
    
    scanf("%c",&direction);
    while(1){
        scanf("%c",&direction);
        if(direction == '\n') break;
        throwdice(direction,&A);
    }
    
    printf("%d\n",A.num[1]);
    
    return 0;
}

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

int main(){
  int n,ans;
  ans=0;
  cin >> n;
  vector<string> s(3);
  
  for(int i=0;i<3;i++){
	cin >> s[i];
  }
  for(int i=0;i<n;i++){
    if(s[0][i]==s[1][i] && s[0][i]==s[2][i]);
    else if(s[0][i]==s[1][i] || s[0][i]==s[2][i] || s[1][i]==s[2][i])ans++;
    else ans+=2;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
import sys

X, N = map(int, input().split())
P = list(map(int, input().split()))

if N == 0:
    print(X)
    sys.exit(0)

diff_prev = 10**10
for i in range(-1, 102):
    if i in P:
        continue

    diff_now = abs(X - i)
    if diff_prev <= diff_now:
        break
    else:
        diff_prev = diff_now
        i_prev = i

print(i_prev)


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

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

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

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

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

int main(){
    lint x,k,d; cin>>x>>k>>d;
    x = abs(x);

    if(x/d >= k){
        cout << x-k*d << endl; return 0;
    }

    lint ans;
    if(k % 2 == 0){
        ans = min(x%(2*d), 2*d-(x%(2*d)));
    }
    else{
        ans = min((x+d)%(2*d), 2*d-((x+d)%(2*d)));
    }
    cout << ans << endl;
}


Measured memory_bytes: 3556
n = int(input())
w_list = list(map(int, input().split()))

min_sum = 1000000
left_sum = 0
right_sum = sum(w_list)
for i in range(n):
    left_sum += w_list[i]
    right_sum -= w_list[i]
    min_sum = min(min_sum, abs(left_sum-right_sum))
print(min_sum)

Measured memory_bytes: 39856
import java.util.Scanner;

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

        int N = sc.nextInt();
        String S = sc.next();
        String ans = null;

        if(N % 2 == 0){
            String a = S.substring(0, N / 2);
            String b = S.substring(N / 2);
            if(a.equals(b)){
                ans = "Yes";
            }else{
                ans = "No";
            }
        }else{
            ans = "No";
        }

        System.out.println(ans);
    }
}


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

public class Main {
  private static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

    public String next() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public String nextLine() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          return reader.readLine();
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }

      return tokenizer.nextToken("\n");
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

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

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

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    System.out.println((a * b) % 2 == 1 ? "Yes" : "No");
  }
}

Measured memory_bytes: 21460
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp> 
const double PI=acos(-1);
using namespace std;
using boost::multiprecision::cpp_int;
#define ll long long
#define ull unsigned long long
#define ul unsigned long
#define ci cpp_int
#define MOD 1000000007

long findmin(long a,long b) {
	return a<b?a:b;
}
long findmax(long a,long b) {
	return a>b?a:b;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long n;
	cin>>n;
	long a[n][3],dp[n][3];
	for(long i=0;i<n;i++) {
		for(int j=0;j<3;j++) {
			cin>>a[i][j];
			if(i==0) {
				dp[i][j]=a[i][j];
			}
		}
	}
	for(long i=1;i<n;i++) {
		for(int j=0;j<3;j++) {
			if(j==0) {
				dp[i][j]=a[i][j]+findmax(dp[i-1][1], dp[i-1][2]);
			}
			else if(j==1) {
				dp[i][j]=a[i][j]+findmax(dp[i-1][0], dp[i-1][2]);
			}
			else {
				dp[i][j]=a[i][j]+findmax(dp[i-1][0], dp[i-1][1]);
			}
		}
	}
	long ans=0;
	for(int i=0;i<3;i++) {
		if(dp[n-1][i]>ans) {
			ans=dp[n-1][i];
		}
	}
	cout<<ans<<"\n";
	cout.flush();
	return 0;
}


Measured memory_bytes: 8276
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,min=100,max=0,ans=0,tmp=0;
  cin >> n;
  int x[n];
  for(int i=0;i<n;i++){
    cin >> x[i];
    if(min>x[i]) min = x[i];
    if(max<x[i]) max = x[i];
  }

  for(int i=min;i<=max;i++){
    if(i==min){
      for(int j=0;j<n;j++) ans += pow(x[j]-i,2);
    }
    else{
      tmp = 0;
      for(int j=0;j<n;j++) tmp += pow(x[j]-i,2);
      if(ans>tmp) ans = tmp;
    }
  }

  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define M 1000005
#define mod 1000000007
#define PB push_back
#define MP std::make_pair
#define FI first
#define SE second
typedef long long ll;
ll type, t, n, m, fib[105];
std::vector <std::pair <ll, ll> > Vec[105];
ll read() {
	char c = getchar(); ll ans = 0;
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') ans = ans * 10 + c - '0', c = getchar();
	return ans;
}
void Write(ll x) {
	if (x < 10) putchar(x + '0');
	else Write(x / 10), putchar(x % 10 + '0');
}
ll min(ll x, ll y) {return x < y ? x : y;}
ll max(ll x, ll y) {return x > y ? x : y;}
void DFS(ll x, std::pair <ll, ll> y) {
	if (x <= 88) {
		Vec[x].PB(y);
		if (y.FI + y.SE <= fib[x + 3]) DFS(x + 1, MP(y.SE, y.FI + y.SE));
		if (y.FI + y.SE * 2 <= fib[x + 3]) DFS(x + 1, MP(y.SE, y.FI + y.SE * 2));
	}
}
int main() {
	type = 1, t = read(), fib[0] = fib[1] = 1;
	for (ll i = 2; i <= 91; i++) fib[i] = fib[i - 1] + fib[i - 2];
	DFS(0, MP(1, 1));
	while (t--) {
		n = read(), m = read(); if (n > m) std::swap(n, m); ll ans = 0;
		if (type == 1) {
			if (n == 1 || (n == 2 && m == 2)) Write(1), putchar(' '), Write(n * m % mod), putchar('\n');
			else {
				ll up = 1;
				while (up <= 88 && Vec[up][0].FI <= n && Vec[up][0].SE <= m) up++; up--;
				for (auto i : Vec[up - 1])
					if (i.SE <= n) ans = (ans + (m - i.FI) / i.SE + (n - i.FI) / i.SE) % mod;
				Write(up), putchar(' '), Write(ans), putchar('\n');
			}
		}
		else {
			if (n == 1 || (n == 2 && m == 2)) Write((n + m - (n != 2 || m != 2)) % mod), putchar('\n');
			else {
				for (ll i = 1; i <= 86; i++)
					for (auto j : Vec[i]) {
						if (j.SE > n) continue;
						if (j.SE < Vec[i + 2][0].FI)
							ans = (ans + (m - j.FI) / j.SE + (n - j.FI) / j.SE) % mod;
						else 
							ans = (ans + (min(Vec[i + 2][0].SE - 1, n) - j.FI) / j.SE) % mod,
							ans = (ans + (min(Vec[i + 2][0].SE - 1, m) - j.FI) / j.SE) % mod;
					}
				Write((ans + n + m) % mod), putchar('\n');
			}
		}
	}
	return 0;
}


Measured memory_bytes: 4372
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N];

int main() {
  int n;
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);   
    b[i] = a[i];
  }
  sort(a + 1, a + 1 + n);
  int pos = n / 2;
  for(int i = 1; i <= n; ++i) {
    if(b[i] > a[pos]) printf("%d\n", a[pos]);
    else printf("%d\n", a[pos + 1]);
  }
  return 0;
}

Measured memory_bytes: 3712
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int H, W;
    cin >> H >> W;
    int h, w;
    cin >> h >> w;

    int ans = (H * w + W * h - w * h);
    cout << (H * W - ans) << endl;
}

Measured memory_bytes: 256
use std::io::{self, BufRead};
use std::cmp;

fn main() {
    let mut line = String::new();
    let _ = io::stdin().read_line(&mut line);

    let mut cnt = Vec::new();
    for _ in 0..9{
        cnt.push(0);
    }
    let reader = io::stdin();
    let numbers: Vec<i32> = 
        reader.lock()       
        .lines().next().unwrap().unwrap()
        .split(' ').map(|s| s.trim())   
        .filter(|s| !s.is_empty())     
        .map(|s| s.parse().unwrap())      
        .collect();

    for num in &numbers{
        cnt[cmp::min((num/400),8) as usize] += 1;
    }
    let mut res : i32 = 0;
    for i in 0..8 {
        res += if cnt[i] > 0 {1} else {0};
    }
    println!("{} {}",cmp::max(res,1), res+cnt[8]);
}


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

int main() {

    int w, h, x, y, r;
    scanf("%d %d %d %d %d", &w, &h, &x, &y, &r);

    if(0 <= x - r && x + r <= w && 0 <= y - r && y + r <= h) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}



Measured memory_bytes: 3136
import java.util.*;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean flag = true;
        Integer[] num = new Integer[n];
        for(int i=0; i<n; i++) {
        	num[i] = sc.nextInt();
        }
        for(int i=0; i<n; i++) {
        	if(num[i]%2==0) {
        		if(num[i]%3==0 || num[i]%5==0) {
        			flag=true;
        		}
        		else {
        			flag=false;
        			break;
        		}
        	}
        }
        if(flag) {
        	System.out.println("APPROVED");
        }
        else {
        	System.out.println("DENIED");
        }
        
	}
}

Measured memory_bytes: 23764
import collections 
s = input()

n = len(s)
m = [0]
mod = 0
ten = 1
for i in s[::-1]:
  mod += (int(i)*ten)%2019
  mod %= 2019
  m.append(mod)
  ten *= 10
  ten %= 2019

count = collections.Counter(m)
print(sum([c*(c-1)//2 for c in count.values()]))
  

Measured memory_bytes: 16924
#include <bits/stdc++.h>
using namespace std;
int main(){
string t,s;
cin>>s>>t;
char S[s.size()];
for(int i=0;i<s.size();i++){
    S[i]=s[i];
}
char T[t.size()];
for(int i=0;i<t.size();i++){
    T[i]=t[i];
}
sort(S,S+(s.size()));
for(int i=0;i<s.size();i++){
    s[i]=S[i];
}
sort(T,T+(t.size()));
reverse(T,T+(t.size()));
for(int i=0;i<t.size();i++){
    t[i]=T[i];
}
if(s<t)cout<<"Yes";
else cout<<"No";


return 0;
}


Measured memory_bytes: 256
// Problem : A - Repeat ACL
// Contest : AtCoder - ACL Beginner Contest
// URL : https://atcoder.jp/contests/abl/tasks/abl_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define ff         first
#define ss         second
#define endl       '\n'
#define pb         push_back
#define int        long long
#define vi         vector<int>
#define mii        map<int, int>
#define pii        pair<int, int>
#define all(x)     (x).begin(), (x).end()
#define fill(a,b)  memset(a, b, sizeof(a))
#define setbits(x) __builtin_popcountll(x)
#define rep(i,x,y) for(int i=(int)x; i<y; i++)
#define px(a)      for(auto x: a) cout<<x<<" "; cout<<'\n';
#define pxy(a,n)   rep(i,0,n) {px(a[i])};
/*_________________________________________________________*/

const long long MOD=1e9+7,N=1e5+5;
int solve()
{
	int n,ans=0;
	cin>>n;
	int a[n];
	rep(i,0,n) cin>>a[i];
	px(a);
	return ans;
}
int32_t main()
{	
	std::ios::sync_with_stdio(false); 
	cin.tie(NULL);
	cout.tie(NULL);
	int n; cin>>n;
	rep(i,0,n) cout<<"ACL"; cout<<endl;
}

Measured memory_bytes: 3584
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll INF=1e15;

int main(){
    ll h,w,n;
    cin >> h >> w >> n;
    map<pll,ll> m;
    rep(i,n){
        ll a,b;
        cin >> a >> b;
        for(ll k=0;k<=2;k++){
            for(ll l=0;l<=2;l++){
                if(1<=a-k && a-k<=h && 1<=b-l && b-l<=w){
                    m[make_pair(a-k,b-l)]++;
                }
            }
        }
    }
    ll sum=0;
    vector<ll> j(10);
    for(auto x:m){
        if(1<=x.fi.fi && x.fi.fi<=h-2 && 1<=x.fi.se && x.fi.se<=w-2){
            j[x.se]++;
        }
    }
    for(ll i=1;i<=9;i++){
        sum+=j[i];
    }
    j[0]=(h-2)*(w-2)-sum;
    rep(i,10){
        cout << j[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 58496
# -*- coding: utf-8 -*-

n, l = map(int, raw_input().split())

ans = 0
if l > 0:
    for i in range(n):
        if i != 0:
            ans += (i + l)
else:
    if n > abs(l):
        for i in range(n):
            if i + l != 0:
                ans += (i + l)
    else:
        for i in range(n-1):
            ans += (i + l)

print ans
        


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

int main(){
  vector<vector<char>> A (2,vector<char>(3,'a'));
  
  for(int i=0;i<2;i++){
    for(int j=0;j<3;j++){
      cin >> A.at(i).at(j);
    }
  }
  bool B = false;
  for(int j=0;j<3;j++){
    int i=0;
    if(A.at(i).at(j) != A.at(i+1).at(2-j)){
      B=true;
      break;
    }
  }
  if(B){
    cout << "NO" << endl;
  }
  else{
    cout << "YES" << endl;
  }
}

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

using namespace std;

int main(){
int N,K; cin >> N >> K;
  vector<long long> V(N);
  for(int i = 0; i < N; i++){ cin >> V[i];}
 
  long long ans = -1LL << 60;
  
  for(int a = 0; a <= min( N, K); a++){
    for(int b = 0; b <= min( N, K) - a; b++){
     vector<int> vec; long long res = 0;
      for(int i = 0; i < b; i++){
        vec.push_back(V[i]); res += V[i];}
      for(int j = N - a; j < N; j++){
        vec.push_back(V[j]); res += V[j];} 
     sort(vec.begin(),vec.end()); int cnt = 0;
      for(int i = 0; i < vec.size(); i++){
        if( vec[i] < 0 && cnt < ( K - ( a + b))){
          res += abs(vec[i]); cnt++;} //小さい順に K - ( a + b) こ分までは捨てられる
      }
      ans = max(ans, res);}}
      
  
  cout << ans << endl; return 0;}

Measured memory_bytes: 256