akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
  int N;
  cin >> N;
  vector<vector<int>> A(2, vector<int>(N));
  
  rep(i, 2){
    rep(j, N){
      cin >> A.at(i).at(j);
    }
  }
  
  int x = 0;
  int y = 0;
  int cnt = A.at(0).at(0);
  int max = 0;
  
  rep(i, N){
    while(x != 1 || y != N-1){
      if(x == 0 && y == i){
        x++;
        cnt += A.at(x).at(y);
      }
      else{
        y++;
        cnt += A.at(x).at(y);
      }
    }
    if(cnt > max){
      max = cnt;
    }
    x = 0;
    y = 0;
    cnt = A.at(0).at(0);
  }
  
  cout << max << endl;
  
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

template <typename T>
bool chmax(T &a, const T& b) {
    if (a < b) {
      a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmin(T &a, const T& b) {
    if (a > b) {
      a = b;
      return true;
    }
    return false;
}
const int MXN=100000;
int dp[MXN];
vl G[MXN];

void bfs(int V){
    if(G[V].size()==0){
        dp[V]=0;
        return;
    }
    int S=G[V].size();
    vl A(S);
    rep(i,S){
        bfs(G[V][i]);
        A[i]=dp[G[V][i]];
    }
    sort(A.begin(),A.end());
    reverse(A.begin(),A.end());
    ll res=0;
    rep(i,S){
        chmax(res,A[i]+i+1);
    }
    dp[V]=res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rep(i,MXN){
        dp[i]=-1;
    }
    int N;
    cin >> N;
    rep(i,N-1){
        int A;
        cin >> A;
        A--;
        G[A].pb(i+1);
    }
    bfs(0);
    cout << dp[0] << endl;
}

Measured memory_bytes: 21928
import java.util.*;

public class Main{
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int a=sc.nextInt();
    int b=sc.nextInt();
    int c=sc.nextInt();
    int d=sc.nextInt();
    int ac=Math.abs(a-c);
    // System.out.println(ac);
    int bc=Math.abs(c-b);
    int ab=Math.abs(a-b);
    // System.out.println(bc+" "+ab);

    if (ac<=d||(bc<=d&&ab<=d)) {
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 21844
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
	using namespace std;

	int main() {
		int A, B;
		cin >> A >> B;

		cout << A * B << endl;
	}
		




Measured memory_bytes: 3644
import java.io.*;
import java.util.*;

import static java.lang.Integer.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter prnt = new PrintWriter(System.out);
        StringTokenizer st;
        st = new StringTokenizer(read.readLine());
        int D = parseInt(st.nextToken()), T = parseInt(st.nextToken()),S = parseInt(st.nextToken());
        if (D <= T * S) {
            prnt.println("Yes");
        } else {
            prnt.println("No");
        }
        prnt.close();
    }
}

Measured memory_bytes: 32688
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N;
    cin >> N;

    vll A(N);
    REP(i, N) cin >> A[i];

    ll ans = 0;
    REP(i, N) REP(j, N) {
        ans = max(ans, abs(A[i] - A[j]));
    }

    print(ans);
    
}


Measured memory_bytes: 3620
def main():
  N, K = map(int, input().split())
  sunuke_l = [0] * N
  for _ in range(K):
    x = int(input())
    y = list(map(int, input().split()))
    for i in y:
      sunuke_l[i-1] += 1
  print(sunuke_l.count(0))
main()

Measured memory_bytes: 67708
#include <stdio.h>

int main(void) {

  int N;
  do {
    scanf("%d", &N);
  } while (N < 2 || N > 100);

  int W[N];
  int S_max = 0;
  for (int i = 0; i < N; i++) {
    do {
      scanf("%d", &W[i]);
    } while (W[i] < 1 || W[i] > 100);
    S_max += W[i];
  }

  int S1[N - 1], S2[N - 1], S_difference[N - 1];
  for (int i = 0; i < N - 1; i++) {
    if (i == 0) {
      S1[i] = W[i];
      S2[i] = S_max - S1[i];
      S_difference[i] = S1[i] - S2[i];
      if (S_difference[i] < 0) {
	S_difference[i] = S_difference[i] * (-1);
      }
    } else {
      S1[i] = W[i] + S1[i - 1];
      S2[i] = S_max - S1[i];
      S_difference[i] = S1[i] - S2[i];
      if (S_difference[i] < 0) {
	S_difference[i] = S_difference[i] * (-1);
      }
    }
  }

  int min = S_difference[0];
  for (int i = 1; i < N - 1; i++) {
    if (min > S_difference[i]) {
      min = S_difference[i];
    }
  }

  printf("%d\n", min);

  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define all int i=0; i<n; i++
#define INF 9999999999999999
using namespace std;
typedef long long int ll; 
#define int ll    

int32_t main(){
	int a,n;
	cin>>a>>n;
	int arr[n];
	for(all)cin>>arr[i];

	
	for(all)a-=arr[i];
	
	if(a<=0)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	long long s = 0, i;
	string x;
	cin >> x;
	for (i = 0; i < x.size(); i++)
	{
		s += (x[i] - '0');
		s %= 9;
	}
	if (s % 9 == 0)
		cout << "Yes";
	else
		cout << "No";
}

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

int main() {
    int N;
    cin >> N;
    string s = to_string(N);
    int num = s.size();
    int sum = 0;
    for (int i = 1; i <= num - 1; i += 2) {
        sum += pow(10, i - 1) * 9;
    }
    if (num == 1) {
        sum += N;
    } else if (num % 2 == 1) {
        sum += N % int(pow(10, num)) - int(pow(10, num-1)) + 1;
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
  int a, b, c, cnt=0;
  cin >> a >> b >> c;
  if(a%2 == b%2 && b%2!=c%2){
    a++;
    b++;
    cnt++;
  }
  else if(b%2==c%2 && c%2!=a%2){
    b++;
    c++;
    cnt++;
  }
  else if(c%2==a%2 && a%2!=b%2){
    c++;
    a++;
    cnt++;
  }
  int mx = max(a, max(b ,c));
  cnt += (3*mx - (a+b+c))/2;
  cout << cnt << endl;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> a(M);
  vector<int> b(M);
  for(int i = 0; i < M; i++) cin >> a.at(i) >> b.at(i);
  vector<int> ans(N, 0);
  for(int i = 0; i < M; i++) {
    ans.at(a.at(i) - 1)++;
    ans.at(b.at(i) - 1)++;
  }
  for(int i = 0; i < N; i++)
    cout << ans.at(i) << endl;
}

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

using namespace std;

int solve(int n, vector<vector<int> > arr) {
  vector<vector<int> > dp(3);
  for(int i = 0; i < 3; i++) {
    dp[i].resize(n + 1);
    for(int j = 0; j < n + 1; j++) {
      dp[i][j] = 0;
    }
  }
  for(int i = 1; i <= 2; i++) {
    for(int j = 1; j <= n; j++) {
      int c1 = dp[i - 1][j];
      int c2 = dp[i][j - 1];
      int c3 = arr[i - 1][j - 1];
      dp[i][j] = (c1 < c2 ? c2 : c1) + c3;
    }
  }
  return dp[2][n];
}

int main() {
  int n;
  cin >> n;
  vector<vector<int> > arr(2);
  for(int i = 0; i < 2; i++) {
    arr[i].resize(n);
    for(int j = 0; j < n; j++) {
      cin >> arr[i][j];
    }
  }
  cout << solve(n, arr) << endl;
}


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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = (int)(n); i >= 0; i--)
#define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--)
#define all(x) (x).begin(),(x).end()
#define inf 2e9
#define MOD 1000000007

using namespace std;
typedef long long int lli;
typedef long long ll;


int main(){
  string s; cin >> s;
 
  if(s == "Sunny") s = "Cloudy";
  else if(s == "Cloudy") s = "Rainy";
  else s = "Sunny";
 
  cout << s << endl;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
 
a.sort()
count = 0
for i in range(n-1, 0, -1):
    l = 0
    r = i-1
    while(l<r):
        if a[l] + a[r] > a[i]:
            count += r-l
            r -= 1
 
        else:
            l += 1
 
print(count)

Measured memory_bytes: 9332
from collections import deque
N = list(input())
S = [int(i) for i in N]
cnt = 0
que = deque(([-1,S[0]]))

for i in range(1,len(S)):
    jdg = que.pop()

    if (S[i] + jdg) == 1:
        cnt += 2
    else:
        que.append(jdg)
        que.append(S[i])
        
print(cnt)

Measured memory_bytes: 49520
#include <stdio.h>

int main()
{
	int n; 
	long int N[201][3], sum[201] = { 0 }, cnt[201][3];
	int i, j, k;

	scanf("%d", &n);
	for (i = 0;i < n;i++) {
		scanf("%d%d%d", &N[i][0], &N[i][1], &N[i][2]);
		cnt[i][0] = 0;cnt[i][2] = 0;cnt[i][1]=0;
	}
	for(k=0;k<3;k++){
		for (i = 0;i < n;i++) {
			for (j = 0;j < n;j++) {
				if (N[i][k] == N[j][k])cnt[i][k] += 1;
			}
				if (cnt[i][k]>1)sum[i] += 0;
				else sum[i] += N[i][k];
		}
	}
	for (i = 0;i < n;i++) {
		printf("%d\n", sum[i]);
	}
	return 0;
}

Measured memory_bytes: 608
N,M = map(int,input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

AB.sort(key=lambda x: x[0])

ans = 0
while(M>0):
    for a,b in AB:
        if b>=M:
            ans += a*M
            M -= M
            break
        else:
            ans += a*b
            M -= b
print(ans)


Measured memory_bytes: 22756
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> P;
typedef vector<P> vec;
 
double eps=1e-8;
double PI=acos(-1);
 
bool eq(double a,double b){return (b-a<eps&&a-b<eps);}
double dot(P a,P b){return real(b*conj(a));}
double cross(P a,P b){return imag(b*conj(a));}
P project(P a,P b,P c){b-=a;c-=a;return a+b*real(c/b);}
P reflect(P a,P b,P c){b-=a;c-=a;return a+conj(c/b)*b;}
int ccw(P a,P b,P c){
  b-=a,c-=a,a=c*conj(b);
  if(a.imag()>eps)return 1;//ccw
  if(a.imag()<-eps)return -1;//cw
  if(a.real()<-eps)return 2;//ob
  if(abs(b)+eps<abs(c))return -2;//of
  return 0;//os
}
 
//segment ab , point c
double dist(P a,P b,P c){
  if(dot(b-a,c-a)<0)return abs(c-a);
  if(dot(a-b,c-b)<0)return abs(c-b);
  return abs(cross(b-a,c-a))/abs(b-a);
}
 
bool isintersect(P a,P b,P c,P d){
  return ((ccw(a,b,c)*ccw(a,b,d)<=0)&&(ccw(c,d,a)*ccw(c,d,b)<=0));
}
 
//segment ab , segment cd
P intersect(P a,P b,P c,P d){
  a-=d;b-=d;c-=d;
  return d+a+(b-a)*imag(a/c)/imag(a/c-b/c);
}
 
double dist(P a,P b,P c,P d){
  if(isintersect(a,b,c,d))return 0;
  double ab=min(dist(a,b,c),dist(a,b,d));
  double cd=min(dist(c,d,a),dist(c,d,b));
  return min(ab,cd);
}
 
double calcArea(vec &t){
  double res=0;
  int n=t.size();
  for(int i=0;i<n;i++)res+=cross(t[i],t[(i+1==n?0:i+1)]);
  return abs(res/2.0);
}
 
double Arg(P a,P b,P c){
  b-=a,c-=a;
  return arg(c*conj(b));
}
 
int inPolygon(vec &t,P p){
  int n=t.size();
  double sum=0;
  for(int i=0;i<n;i++){
    P a=t[i],b=t[(i+1==n?0:i+1)];
    if( ccw(a,b,p) == 0 )return 1;
    sum+= Arg(p,a,b);
  }
  if( abs(sum) < eps )return 0;
  else  return 2;
}
 
int main(){
  int n;
  cin>>n;
  vec t;
  double x,y;
  for(int i=0;i<n;i++){
    cin>>x>>y;
    t.push_back(P(x,y));
  }
  int q;
  cin>>q;
  while(q--){
    cin>>x>>y;
    cout<<inPolygon(t,P(x,y))<<endl;
  }
 
  return 0;
}

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

#define MAX_V 105
#define INF 1e9

typedef pair<int, int> P; // first??????????????¢, second??????????????????

// ????????¨????§??????? (?????????, ??????, ?????????, ??????)
struct edge {
    int to, cap, cost, rev;
};

int V;                          // ????????°
vector<edge> G[MAX_V];     // ??°???????????£??\???????????¨???
int h[MAX_V];                   // ??????????????£???
int dist[MAX_V];                // ???????????¢
int prevv[MAX_V], preve[MAX_V]; // ??´??????????????¨???

// from??????to??????????????????cap,?????????cost???????????°?????????????????????
void add_edge(int from, int to, int cap, int cost) {
    G[from].push_back((edge){to, cap, cost, G[to].size()});
    G[to].push_back((edge){from, 0, -cost, G[from].size() - 1});
}

// s??????t????????????f???????°??????¨???????±???????
// ??????????????´??????-1?????????
int min_cost_flow(int s, int t, int f) {
    int res = 0;
    fill(h, h + V, 0); // h????????????
    while (f > 0) {
        // ??????????????????????????¨??????h?????´??°??????
        priority_queue<P, vector<P>, greater<P> > que;
        fill(dist, dist + V, INF);
        dist[s] = 0;
        que.push(P(0, s));
        while (!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if (dist[v] < p.first)
                continue;
            for (int i = 0; i < G[v].size(); i++) {
                edge &e = G[v][i];
                if (e.cap > 0 &&
                    dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push(P(dist[e.to], e.to));
                }
            }
        }
        if (dist[t] == INF) {
            // ????????\???????????????
            return -1;
        }
        for (int v = 0; v < V; v++)
            h[v] += dist[v];

        // s-t????????????????????£??????????????????
        int d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * h[t];
        for (int v = t; v != s; v = prevv[v]) {
            edge &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}

int main(){
    int e, f;
    cin >> V >> e >> f;
    for(int i=0;i<e;++i){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        add_edge(u, v, c, d);
    }

    cout << min_cost_flow(0, V-1, f) << endl;

    return 0;
}


Measured memory_bytes: 3204
import math
import itertools

n=int(input())
b = list(map(int,input().split()))[:n]

a=[0] * n 

for i in range(n):

    if(i==0):
        a[i] =b[i]
    elif(i==n-1):
        a[i] = b[i-1]
    else:
        a[i] = min(b[i],b[i-1])

print(sum(a))


Measured memory_bytes: 3060
import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

ba = [None]*N
bc = [None]*N

for i in range(N):
    ba[i] = bisect.bisect_left(A, B[i])
for i in range(N):
    bc[i] = bisect.bisect_right(C, B[i])

ans = 0
for i in range(N):
    ans += ba[i]*(N-bc[i])
print(ans)


Measured memory_bytes: 23488
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = 0; i < (n); i++)
 
int main(){
    int N;
    cin >> N;
    vector<long long> a(3*N);

    for(int i=0;i<3*N;i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end(),greater<int>());
    long long sum = 0;
    for(int i=1;i<=2*N;i+=2){
        sum += a[i];
    }
    cout << sum;

    return 0;
}

Measured memory_bytes: 2560
n = int(input())
bdict = {}
rdict = {}
for i in range(0, n):
    line = input()
    if not (line in bdict):
        bdict[line] = 0
    bdict[line] += 1
m = int(input())
for i in range(0, m):
    line = input()
    if not (line in rdict):
        rdict[line] = 0
    rdict[line] += 1
ans = 0
temp = 0
for i in bdict.items():
    temp = i[1]
    if i[0] in rdict:
        temp -= rdict[i[0]]
    if temp > ans:
        ans = temp
print(ans)

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

using namespace std;

int main() {
  int N;
  int d[110];
  int count = 0;

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

  sort(d, d+N);

  for(int i=0;i<N-1;++i){
    if(d[i+1]-d[i] <= 0) count = count + 1;
  }

  cout << N-count << endl;
  
}


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

using namespace std;

using ll = long long;
using ii = pair<int,int>;

#define ff first
#define ss second

const int maxn = 1e5+10;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int a,x;
	cin >> x >> a;
	cout << (x<a ? 0 : 10) << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n,m;
    cin >> n >> m;
    int a[100][100],b[100];
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            a[i][j]=0;
        }
    }
    for(int i=0; i<m; i++){
        b[i]=0;
    }
    int Z;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> Z;
            a[i][j]=Z;
        }
    }
    int Y;
    for(int i=0; i<m; i++){
        cin >> Y;
        b[i]=Y;
    }
    int X=0;
    for(int i=0; i<n; i++){
        X=0;
        for(int j=0; j<m; j++){
            X+=a[i][j]*b[j];
        }
        cout << X << endl;
    }
}



Measured memory_bytes: 3100
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(int argc,char** argv){
  int n;
  cin >> n;
  if(n==1){
    cout << "Hello World" << endl;
  }else if(n == 2){
    int a,b;
    cin >> a >> b;
    cout << a + b << endl;
  }

  return 0;
}


Measured memory_bytes: 256
import sys

input = sys.stdin.readline
s = input()
lft, rgt = 0, 0
cnt = 0
tmp = ""
for cur in s:
    if tmp == ">" and cur == "<":
        lar = max(lft, rgt)+1
        sma = min(lft, rgt)
        cnt += sum(range(lar)) + sum(range(sma))
        lft, rgt = 1, 0
    elif cur == ">":
        rgt += 1
    elif cur == "<":
        lft += 1
    tmp = cur

lar = max(lft, rgt)+1
sma = min(lft, rgt)
cnt += sum(range(lar)) + sum(range(sma))
print(cnt)


Measured memory_bytes: 47212
#include <iostream>
#include <string>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;

#define PI 3.14159265358979323846264338327950L

ll res;

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

    string S;
    cin >> S;
    ll N = S.size();
    res = 0;
    vector<ll> Black(N, 0);
    ll black_count = 0;
    for (int i = 0; i < N; i++)
    {
        if (S[i] == 'B')
        {
            black_count++;
        }
        Black[i] = black_count;
    }
    for (int i = 0; i < N; i++)
    {
        if (S[i] == 'W')
        {
            res += Black[i];
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 5112
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 100; 
const double pi = acos(-1.0);

inline ll read()
{
    ll kk=0,f=1;
    char cc=getchar();
    while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}
    while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}
    return kk*f;
}

ll floor(ll a,ll b);
int main(void)
{
	ll a,b,n;
	a=read();b=read();n=read();
	
	ll x=min(n,b-1);
	ll ans = floor(a*x/b) - a*floor(x/b); 
	printf("%lld",ans);
	return 0;
}

ll floor(ll a,ll b)
{
	ll c=a/b;
	return a/b;
}

Measured memory_bytes: 3732
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    ttl_bins = [0]*60
    for i in range(N):
        target = targets[i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            ttl_bins[keta] += int(target_str[keta])

    ans = 0
    for i in range(60):
        ttl = ttl_bins[i] * (N - ttl_bins[i])
        ans += pow(2, 59-i, MOD) * ttl
        ans %= MOD

    print(ans)


main()


Measured memory_bytes: 119304
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int a = Integer.parseInt(line[0]);
        int b = Integer.parseInt(line[1]);
        int x = Integer.parseInt(line[2]);
        
        if ((x >= a) && (a + b >= x)) System.out.println("YES");
        else System.out.println("NO");
    }
}


Measured memory_bytes: 21076
#include <stdio.h>

int
main(void)
{
  int h, w, i, j;
  while (1) {
    scanf("%d %d", &h, &w);
    if (h == 0 && w == 0) {
      break;
    }
    for (i = 0; i < h; i++) {
      for (j = 0; j < w; j++) {
        if (i != 0 && i != h - 1 && j != 0 && j != w - 1) {
          printf("%c", '.');
        } else {
          printf("%c", '#');
        }
      }
      printf("\n");
    }
    printf("\n");
  }
}

Measured memory_bytes: 1696
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int h,w;
int res=inf;

void dfs(int x,int y,int d,vvi a){
	if(d==10) return;
	for(int i=0;i<4;i++){
		int p=x,q=y;
		while(p>=0&&p<h&&q>=0&&q<w&&!a[p][q]){
			p+=dx[i],q+=dy[i];
		}
		if(p<0||p>=h||q<0||q>=w) continue;
		if(a[p][q]==3){
			res=min(res,d+1);
			continue;
		}
		vvi b=a;
		b[p][q]=0;
		p-=dx[i],q-=dy[i];
		if(p==x&&q==y) continue;
		dfs(p,q,d+1,b);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(1){
		cin>>w>>h;
		if(h==0) break;
		vvi a(h,vi(w));
		int x,y;
		for(int i=0;i<h;i++) for(int j=0;j<w;j++){
			cin>>a[i][j];
			if(a[i][j]==2){
				a[i][j]=0;
				x=i,y=j;
			}
		}
		res=inf;
		dfs(x,y,0,a);
		cout<<(res==inf?-1:res)<<endl;
	}
}


Measured memory_bytes: 3224
#include <iostream>
#include <algorithm>
#include <string>

int main(void)
{
  std::string str;
  std::cin >> str;
  
  std::string rev;
  for (int i = str.size() - 1; i >= 0; i--) {
    rev.push_back(str[i]);
  }
  
  std::cout << rev << std::endl;
  
  return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
#include <iterator>
using namespace std;
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(v) begin(v), end(v)
#define rreps(i, a, n) for (ll i = (a); i <= (ll)(n); ++i)
#define rrep(i, n) rreps(i, 0, n)
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define each(i, n) for (auto&& i : n)
#define fill(x, y) memset(x,y,sizeof(x))
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template <typename T> inline void print(const T& x) {cout << x << '\n';}

signed main()
{ 
  int n,p;
  vi ans;
  while(cin>>n>>p,n||p)
  {
    vi man(n);
    each(v,man) v=0;
    for(int i=0;;i++)
    {
      if(i==n) i=0;
      if(p==0)
      {
        bool c=true;
        rep(j,n)
        {
          if(j==i) continue;
          if(man[j]>0) c=false;
        }
        if(c)
        {
          ans.push_back(i);
          break;
        }
        p+=man[i];
        man[i]=0;
      }
      else
      {
        man[i]++;
        p--;
      }
    }
  }
  each(v,ans) print(v);

  return 0;
}



Measured memory_bytes: 3124
#include <stdio.h>
#include <string.h>

typedef struct {
	char name;
	int win;
	int lose;
} TEAM;

TEAM team[16];

int cmp(TEAM *A, TEAM *B)
{
	if (A->win == B->win){
		return (A->lose - B->lose);
	}
	
	return (B->win - A->win);	
}

int main(void)
{
	int i, n;
	int j;
	int r;
	
	while (scanf("%d", &n), n){
		memset(team, 0, sizeof(team));
		
		for (i = 0; i < n; i++){
			scanf(" %c", &team[i].name);
			
			for (j = 0; j < n - 1; j++){
				scanf("%d", &r);
				
				if (r == 0){
					team[i].win++;
				}
				else if (r == 1){
					team[i].lose++;
				}
			}
		}
		
		qsort(team, n, sizeof(TEAM), cmp);
		
		for (i = 0; i < n; i++){
			printf("%c\n", team[i].name);
		}
	}
	
	return (0);
}

Measured memory_bytes: 608
package main

import (
	"fmt"
	"io"
	"os"
)

func main() {
	solve(os.Stdin, os.Stdout)
}

func solve(in io.Reader, out io.Writer) {
	var a, p int
	fmt.Fscanf(in, "%d%d", &a, &p)
	ans := (a*3 + p) / 2
	fmt.Fprintln(out, ans)
}

Measured memory_bytes: 512
fn dfs(adjl: &Vec<Vec<usize>>, v: usize, mut memo: &mut Vec<usize>) -> usize {
    if memo[v] != std::usize::MAX {
        memo[v]
    } else {
        let mut res = 0;
        for n in &adjl[v] {
            res = max(res, dfs(&adjl, *n, &mut memo) + 1);
        }
        memo[v] = res;
        res
    }
}

fn main() {
    let (n, m): (usize, usize) = (read::<usize>(), read::<usize>());
    let mut indeg = vec![0; n];
    let mut adjl = vec![vec![]; n];
    let mut leaves = vec![];
    for _ in 0..m {
        let (x, y): (usize, usize) = (read::<usize>() - 1, read::<usize>() - 1);
        adjl[x].push(y);
        indeg[y] += 1;
    }
    for i in 0..n {
        if indeg[i] == 0 {
            leaves.push(i);
        }
    }
    let mut ans = 0;
    let mut memo = vec![std::usize::MAX; n];
    for l in leaves {
        ans = max(dfs(&adjl, l, &mut memo), ans);
    }
    println!("{}", ans);
}

// =========
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet};
#[allow(unused_imports)]
use std::process::exit;

#[allow(dead_code)]
const MOD: isize = 1000000007;

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

// =========


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



void rec(int d, long long val, vector<long long> &all) {

all.push_back(val);

if(d == 10) return;

for(int j = -1; j <= 1; j++){
int add = (val % 10) + j;
if(add >= 0 && add <= 9) rec(d+1, val*10+add, all);

}


}



int main() {
int K;
cin >> K;
vector<long long> all;
for(int v = 1; v < 10; v++) rec(1, v, all);

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

cout << all[K-1] << endl;

}

Measured memory_bytes: 2420
for n in iter(input, '0'):
    st = ''
    prv_lv = 0
    ops = ['']
    for _ in range(int(n)):
        line = input()
        lv = line.count('.')
        op = line[lv:]
        while prv_lv > lv:
            ops.pop()
            st += ')'
            prv_lv -= 1
        if op in '*+':
            st += ops[-1]
            st += '(' + str(int(op == '*'))
            ops.append(op)
        else:
            st += ops[-1] + op
        prv_lv = lv
    while len(ops) > 1:
        ops.pop()
        st += ')'
    print(eval(st))


Measured memory_bytes: 5612
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
int n,a[1000005],b,d[1000005],cnt[1000005],g,p=1;
void sieve(){
   for(int i=2;i<=1000;i++){
      if(d[i]==i){
         for(int j=i*i;j<=1000000;j+=i) d[j]=i;
      }
   }
}
int main(){
   for(int i=1;i<=1000000;i++) d[i]=i;
   sieve();
   cin>>n;
   for(int i=1;i<=n;i++){
      cin>>a[i];
      b=a[i];
      set<int> s;
      while(b>1){
         s.insert(d[b]);
         b/=d[b];
      }
      for(auto j:s) cnt[j]++;
   }
   g=__gcd(a[1],a[2]);
   for(int i=3;i<=n;i++) g=__gcd(g,a[i]);
   for(int i=1;i<=1000000;i++){
      if(cnt[i]>=2) p=0;
   }
   if(p) cout<<"pairwise coprime";
   else if(g==1) cout<<"setwise coprime";
   else cout<<"not coprime";
   return 0;
}

Measured memory_bytes: 15296
#include <iostream>
#include <vector>
#include <numeric>

using lint = long long;

void fail() {
    std::cout << "NO" << std::endl;
    std::exit(0);
}

int main() {
    lint N;
    std::cin >> N;

    std::vector<lint> A(N);
    for (auto& a : A) std::cin >> a;
    lint sum = std::accumulate(A.begin(), A.end(), 0LL);

    if (sum % (N * (N + 1) / 2) > 0) fail();

    // 合計操作回数
    lint M = sum / (N * (N + 1) / 2);

    for (lint i = 0; i < N; ++i) {
        lint d = A[(i + 1) % N] - A[i];

        // 箱iの選ばれる回数は(M-d)/Nとなる
        // この値は非負整数でなくてはならない
        if (M < d || (M - d) % N > 0) fail();
    }

    std::cout << "YES" << std::endl;
    return 0;
}


Measured memory_bytes: 1024
fn fact(n: usize) -> usize {
    let mut ret = 1_usize;
    for i in 2..n + 1 {
        ret *= i;
        ret %= 1_000_000_007;
    }
    ret
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    let (n, m) = {
        let v: Vec<usize> = buf.split_whitespace().map(|x| x.parse().unwrap()).collect();
        (v[0], v[1])
    };

    let ans = if n == m {
        2 * fact(n) * fact(m) % 1_000_000_007
    } else if n == m + 1 || n + 1 == m {
        fact(n) * fact(m) % 1_000_000_007
    } else {
        0
    };
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
  long long s;
  cin >> s;

  long long a,b,c,d,e,f;
  a = 0;
  b = 0;
  d = 0;
  e = 0;

  long long mid = sqrt(s);
  long long news;
  if(mid * mid == s){
  news = s;
  c = mid;
  f = mid;
  }
  else{
  news = (mid + 1) * (mid + 1);
  c = mid + 1;
  f = mid + 1;
  }

  long long de = news - s;
  for(long long i=sqrt(de);i>0;i--){
    bool check = false;
    if(de % i == 0){
      d = i;
      e = de / i;
      check = true;
      break;
    }
    if(check)
    break;
  }

  cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << endl;
  return 0;
}


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

#define N 100000

using namespace std;

int main(void){
long int debt = 0;

  int n;
  cin >> n;
  int money = N;
  
  for(int i = 0;i < n;i++){
  	
  	if(((money *= 1.05) % 1000) != 0){
  		money += 1000 - (money % 1000);
  	}
  	
  }
  cout << money << endl;


  return 0;
}

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main() {
  int H, W; cin >> H >> W;
  char c[H][W];
  for(int i = 0; i < H; i++)
    for(int j = 0; j < W; j++)
      cin >> c[i][j];
  char g[H + 2][W + 2];
  for(int i = 0; i < H + 2; i++)
    for(int j = 0; j < W + 2; j++)
      if(i == 0 || i == H + 1 
         || j == 0 || j == W + 1)
        g[i][j] = '#';
      else g[i][j] = c[i - 1][j - 1];
  for(int i = 0; i < H + 2; i++, cout << endl)
    for(int j = 0; j < W + 2; j++)
      cout << g[i][j];
}

Measured memory_bytes: 256
def main():
  S_=input()
  T=input()
  ans=''
  if len(S_)<len(T):
    print('UNRESTORABLE')
    return
  for i in range(len(S_)-len(T)+1):
    flag=True
    for j in range(len(T)):
      if S_[i+j]!='?' and S_[i+j]!=T[j]:
        flag=False
        break
    if flag:
      S=['a']*len(S_)
      for k in range(i):
        if S_[k]!='?':
          S[k]=S_[k]
      for k in range(i,i+len(T)):
        S[k]=T[k-i]
      for k in range(i+len(T),len(S_)):
        if S_[k]!='?':
          S[k]=S_[k]
      if ans=='':
        ans=''.join(S)
      elif ans>''.join(S):
        ans=''.join(S)
  if ans=='':
    print('UNRESTORABLE')
  else:
    print(ans)
  return

main()


Measured memory_bytes: 38512
#include <iostream>
#include <stdio.h>
#include <stack>
#include <stdlib.h>
using namespace std;
int main(){
    int x,a,b,ans;
    stack<int> S;
    char s[1000];
    while(scanf("%s" ,s)!=EOF){
        if(s[0]=='+'){
            a=S.top();
            S.pop();
            b=S.top();
            S.pop();
            ans=a+b;
            S.push(ans);
        }
        else if(s[0]=='-'){
            a=S.top();
            S.pop();
            b=S.top();
            S.pop();
            ans=b-a;
            S.push(ans);
        }
        else if(s[0]=='*'){
            a=S.top();
            S.pop();
            b=S.top();
            S.pop();
            ans=a*b;
            S.push(ans);
        }
        else{
            x=atoi(s);
            S.push(x);
        }
    }
    cout<<S.top()<<endl;
    return 0;
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
    cin>>n>>m;
    if (1ll*m*n<=n+m) return cout<<min(n,m)<<endl,0;
    cout<<1ll*n*m/2+abs(n*m%2)<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<numeric>
using namespace std;
int main()
{
    long long int a,b,mul;
    cin>>a>>b;
    mul= a*b;
    int gcd;
    gcd=__gcd(a,b);
    long long int lcm;
    lcm = mul/gcd;
    cout<<lcm<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;



int main() {
  Vl v(3);
  rep(i, 0, 3) cin >> v[i];
  sort(ALL(v));
  ll a = v[2], b = v[1], c = v[0];
  ll cnt = 2*a - b - c;
  if(cnt%2 == 0) cout << cnt/2 << endl;
  else cout << (cnt+3)/2 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//---------------------------------------------------------------------------------------------------------
#ifdef DEBUG
#define debug( args... ) { vector<string> _v = split( #args, ','); err( _v.begin(), args); cerr << '\n'; }
vector<string> split( const string& s, char c) {
    vector<string> v;
    stringstream ss( s);
    string x;
    while ( getline( ss, x, c))
        v.emplace_back( x);
    return move( v);
}
void err( vector<string>::iterator it) { }
template<typename T, typename... Args>
void err( vector<string>::iterator it, T a, Args... args) {
    cerr << it -> substr( ( *it)[0] == ' ', it -> length()) << " = " << a << '\t';
    err( ++it, args...);
}
#else
#define debug(...)
#endif
//----------------------------------------------------------------------------------------------------------

#define pb push_back
#define pfr push_front
#define eb emplace_back
#define ef emplace_front
#define fi first
#define se second
#define mp make_pair
#define fr(i,j,k) for(i = j; i < (k); i++)
#define bck(i,j,k) for(i = j; i > (k); i--)
#define all(x) x.begin(), x.end()
#define el '\n'

typedef long long int ll;
typedef long double DO;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vi;
//---------------------------  TEMPLATE ENDS, MAKE CHANGES FROM HERE ----------------------------------------

const int mod = 1e9+7;
const ll inf = 2e18;
const DO eps = 1e-9;
const int NN = 1e6 + 2;

const int maxn = NN;
ll fact[maxn], inv[maxn], invFact[maxn];

ll ncr(int n, int r){
    if(n < 0 || r < 0 || n < r) return 0;

    ll v = (invFact[r] * invFact[n-r] ) %mod;
    return (v*fact[n])%mod;
}

void pre(){
    int i;
    fact[0] = fact[1] = 1;
    for(i=2; i<maxn; i++)
        fact[i] = (fact[i-1]*i)%mod;

    inv[0] = 0;
    inv[1] = 1;
    for (i = 2; i < maxn; i++) {
        inv[i] = mod - ((ll) (mod / i) * inv[mod % i] % mod);
    }

    invFact[0] = 1;
    for (i = 1; i < maxn; i++) {
        invFact[i] = ( inv[i] * invFact[i - 1] % mod);
    }
}


void getDivs(int x, multiset <int> &ms){

    for(int i = 2; i*i <= x; i++) {
        if(x%i == 0) {
            int j = 0;
            while(x % i == 0) {
                x /= i;
                j++;
            }
            ms.insert(j);
        }
    }
    if(x > 1) ms.insert(1);
}
void solve(){
    int i = 0, j = 0, k = 0, n = 0, m = 0;
    cin >> n >> m;
    ll ans = 1;
    debug(n, m);
    multiset<int> ms;
    getDivs(m, ms);
    for(int a : ms) {
        ans = (ans * ncr(a + n - 1, a))%mod;
    }
    cout << ans;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1, tc;
    pre();
    fr(tc, 1, T+1){
        solve();
    }
    return 0;
}
/* The judge is never wrong! Your code is buggy 😈
   Look for:
 * * an easier and alternate approach
 * * if concept is corret and still WA, try with a different implementation
 * * special cases (n=1?)
 * * overflow (ll vs int?)
 * * array bounds
 * * if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
 */



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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


ll A,B,C,D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>D;
	cout<<max({A*C,A*D,B*C,B*D})<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 3652
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long

const int MAX=88;
const int mod=1e9+7;

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

int A,B;
int re1[MAX+5],re2[MAX+5];
int len;
int k1,k2;

int Work(int x,int y,int tot)
{
	if(x>A||y>B)
		return tot-1;
	if(x!=y)
	{
		re1[++len]=x,re2[len]=y;
		k1=x,k2=y;
	}
	return Work(x+y,x,tot+1);
}

int f[MAX+5];
int sum;

void Find1(int x,int val1,int val2)
{
	int sum1=0,sum2;
	if(!val2)
		sum2=0x3f3f3f3f3f3f3f3f;
	else
		sum2=(B-k2)/re2[x]/val2;
	sum1=((A-k1)/re2[x])/val1;
	for(int i=1;i<=min(sum1,sum2);i++)
	{
		int t1=k1+i*val1*re2[x];
		int t2=k2+i*val2*re2[x];
		sum=(sum+(A-t1)/t2+1)%mod;
		if(B>=t1)
			sum=(sum+1)%mod;
	}
}

signed main()
{
	f[1]=1;
	f[2]=1;
	for(int i=3;i<=MAX;i++)
		f[i]=f[i-1]+f[i-2];
	int T=read();
	while(T--)
	{
		A=read(); B=read();
		len=0;
		if(A<B)
			swap(A,B);
		if(A==1&&B==1)
		{
			cout<<"1"<<" "<<"1"<<endl;
			continue;
		}
		if(A==2&&B==1)
		{
			cout<<"1"<<" "<<"2"<<endl;
			continue;
		}
		if(B==1)
		{
			cout<<"1"<<" "<<A%mod<<endl;
			continue;
		}
		int ans1=Work(1,0,0)-1;
		printf("%lld ",ans1);
		if(A==2&&B==2)
		{
			cout<<"4"<<endl;
			continue;
		}
		if(k1<=B)
			sum=2;
		else
			sum=1;
		sum=(sum+(A-k1)/k2)%mod;
		for(int i=2;i<len;i++)
		{
			int val1=f[len-i+1];
			int val2=f[len-i];
			Find1(i,val1,val2);
		}
		printf("%lld\n",sum);
	}
	return 0;
}







Measured memory_bytes: 3968
n = int(input())
s = list(input())

alp = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
ans = ''

for c in s:
    if alp.index(c) + n > 25:
        ans += alp[alp.index(c)+n-26]
    else:
        ans += alp[alp.index(c) + n]

print(ans)

Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
#include<string.h>

#define N 0;
#define S 1;
#define E 2;
#define W 3;

typedef struct dice{
	int e[7]; /*Dice Eyes 1～6*/
}dice_t;


void DiceRoll(char order, dice_t* pDice){
	
	switch (order){
		case 'N':
			pDice->e[0] = pDice->e[1];
			pDice->e[1] = pDice->e[2];
			pDice->e[2] = pDice->e[6];
			pDice->e[6] = pDice->e[5];
			pDice->e[5] = pDice->e[0];
			break;
		case 'S':
			pDice->e[0] = pDice->e[1];
			pDice->e[1] = pDice->e[5];
			pDice->e[5] = pDice->e[6];
			pDice->e[6] = pDice->e[2];
			pDice->e[2] = pDice->e[0];
			break;
		case 'E':
			pDice->e[0] = pDice->e[1];
			pDice->e[1] = pDice->e[4];
			pDice->e[4] = pDice->e[6];
			pDice->e[6] = pDice->e[3];
			pDice->e[3] = pDice->e[0];
			break;
		case 'W':
			pDice->e[0] = pDice->e[1];
			pDice->e[1] = pDice->e[3];
			pDice->e[3] = pDice->e[6];
			pDice->e[6] = pDice->e[4];
			pDice->e[4] = pDice->e[0];
			break;
		default:
			break;
	}
	return ;
}


int main(){
	int i;
	dice_t dice;
	dice_t* pDice = &dice;
	char order[100]={0};
	int order_num;
	
	for(i=1; i<7; i++){
		scanf("%d", &dice.e[i]);
	}
	scanf("%s", order);
	
	order_num = (int)strlen(order);
	
	for(i=0; i<order_num; i++){
		DiceRoll( order[i], pDice );
	}
	printf("%d\n", dice.e[1]);
	
	
	return 0;
}




Measured memory_bytes: 2136
N, Y = map(int, input().split())


def judge(n, target):
    for x in range(n+1):
        for y in range(n+1-x):
            # 読みにくい解き方
            # https://atcoder.jp/contests/abc085/submissions/9494737 が読みやすい
            tmp = Y - 10000 * x - 5000 * y
            z = n - x - y
            if tmp / 1000 == z:
                return '{} {} {}'.format(x, y, z)
    return '-1 -1 -1'


print(judge(N, Y))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;
typedef pair<ll, ll> pint;

const int MOD = 1000000007;
void yesno(bool b) {
    if (b) {
        cout << "Yes" << endl;
    }     else {
        cout << "No" << endl;
    }
}

int main() {
    ll X;
    cin >> X;
    ll tmp = 101;
    ll t1;
    ll ind = 1;
    while(tmp < X) {;
        t1 = tmp/100;
        tmp += t1;
        ind++;
    }

    cout <<  ind << endl;

}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int main(){
    long long n,m;
    long long ans;
    cin >> n >> m;
    
    vector<pair<long long, long long>> p_vec;
    for(int i = 0; i < n; i++){
        pair<long long, long long> p;
        cin >> p.first >> p.second;
        p_vec.push_back(p);
    }
    sort(p_vec.begin(), p_vec.end());

    for(int i = 0; i < n; i++){
        long long honsu;
        if(m < p_vec[i].second)honsu = m;
        else honsu = p_vec[i].second;
        ans += p_vec[i].first * honsu;
        m -= honsu;
        if(m == 0)break;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2420
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

ll dp[2222][2222];

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

	ll n;cin >> n;
	vector<P> a(n);
	REP(i, n) {
		cin >> a[i].FI;
		a[i].SE = i;
	}

	sort(ALL(a), greater<P>());
	ll ans = 0;

	REP(i, n+1){
		REP(j, n+1){
			if(i + j >= n){
				ans = max(ans, dp[i][j]);
				continue;
			}
			ll left = i;
			ll right = n - 1 - j;
			ll id = a[i+j].SE;
			ll c = a[i+j].FI;
			dp[i+1][j] = max(dp[i+1][j], dp[i][j] + c * abs(id - left));
			dp[i][j+1] = max(dp[i][j+1], dp[i][j] + c * abs(id - right));
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 26960
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
ll llmax = LLONG_MAX;
string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alp = "abcdefghijklmnopqrstuvwxyz";
vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
void neg() {cout << -1 << endl;}

int main() {
  ll h, n;
  cin >> h >> n;
  vll a(n), b(n);
  for (ll i = 0; i < n; i++) cin >> a[i] >> b[i];
  vll dp(10001, llmax);
  dp[0] = 0;
  for (ll i = 1; i <= h; i++) {
    for (ll j = 0; j < n; j++) {
      dp[i] = min(dp[i], dp[max(0LL, i - a[j])] + b[j]);
    }
  }
  cout << dp[h] << endl;
}

Measured memory_bytes: 384