akhauriyash/Code-Regression huggingface dataset:
fn main() {
    proconio::input! {
        n: usize,
        x: String,
    }

    let bp = x.match_indices('1').count() as u64;
    let p = if bp == 1 { vec![2, 1] } else { vec![bp + 1, bp - 1] };

    let xr: Vec<char> = x.chars().rev().collect();

    let mut pows = vec![[1, 1]; n];
    let mut xv = if xr[0] == '1' { [1, 1] } else { [0, 0] };
    for i in 1..n {
        for j in 0..=1 {
            pows[i][j] = (pows[i - 1][j] * 2) % p[j];
            if xr[i] == '1' {
                xv[j] += pows[i][j];
                xv[j] %= p[j];
            }
        }
    }

    for i in (0..n).rev() {
        if bp == 1 && xr[i] == '1' {
            println!("0");
        } else {
            let xi = if xr[i] == '0' {
                (xv[0] + pows[i][0]) % p[0]
            } else {
                let p = if xv[1] >= pows[i][1] { 0 } else { p[1] };
                xv[1] + p - pows[i][1]
            };
            println!("{}", 1 + pop_pop_count(xi));
        }
    }
}

fn pop_pop_count(mut v: u64) -> u64 {
    let mut r = 0;
    while v > 0 {
        v %= v.count_ones() as u64;
        r += 1;
    }
    r
}


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

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int func(int n){
  int tmp = 0;
  while(n>0){
    tmp += n%10;
    n = n/10;
  }
  return tmp;
}
int main(){
  string n; cin >> n;
  int last = n.size();
  int sum = 0;
  for(int i=0; i<last; ++i){
    int num = n[i] - '0';
    sum += func(num);
  }

  if(sum%9==0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

#define ll long long int
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define repm(i, a, n) for (ll i = a; i >= n; i--)
#define INF 1e9
#define LINF 1e17
#define MOD (int)(1e9 + 7)
#define mod (int)(1e9 + 7)
#define pi 3.141592653589
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vii vector<vector<int>>
#define vllll vector<vector<ll>>
#define ALL(a) (a).begin(), (a).end()

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

void print(bool f)
{
    cout << (f ? "Yes" : "No") << endl;
}

void Print(bool f)
{
    cout << (f ? "YES" : "NO") << endl;
}

int main(void)
{
    ll n;
    cin >> n;

    if (n < 10)
        return cout << n << endl, 0;
    vll s;
    rep(i, 1, 10) s.push_back(i);
    ll cnt = 9;
    for (int i = 0;; i++)
    {
        for (int j = -1; j < 2; j++)
        {
            if (s[i] % 10 == 0 && j == -1)
                continue;
            if (s[i] % 10 == 9 && j == 1)
                continue;
            ll tmp = s[i] * 10 + (s[i] % 10 + j);
            cnt++;
            if (cnt == n)
                return cout << tmp << endl, 0;
            s.push_back(tmp);
        }
    }
}

Measured memory_bytes: 4312
#include <iostream>
#include <vector>
#include <chrono>
#include <random>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	long long a, b;
	std::cin >> a >> b;
	std::cout << std::max(a+b, std::max(a-b, a*b)) << '\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int (i)=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1000000007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }

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

vector<double> calc(int fr, int to){
    vector<double> dp(N, 1e16);
    dp[N-1] = 0.0;
    for(int i=N-2; i>=0; i--){
        int M = G[i].size();
        if(fr == i) M--;
        if(M==0) continue;
        dp[i] = 0.0;
        for(int j : G[i]){
            if(i!=fr || j!=to) dp[i] += 1+dp[j];
        }
        dp[i] /= M;
    }
    return dp;
}

int main(){
    cin >> N >> M;
    G.resize(N);
    REP(i, M){
        int s, t;
        cin >> s >> t;
        s--; t--;
        G[s].push_back(t);
    }
    vector<double> dp = calc(-1, -1);
    vector<int> cands(N);
    for(int i=0; i<N-1; i++){
        double mx = -1.0;
        int j = -1;
        for(int to : G[i]){
            if(dp[to] > mx){
                j = to;
                mx = dp[to];
            }
        }
        cands[i] = j;
    }
    double ans = 1e16;
    for(int i=0; i<N-1; i++){
        ans = min(ans, calc(i, cands[i])[0]);
    }
    ans = min(ans, calc(-1, -1)[0]);
    cout << fixed << setprecision(12) << ans << endl;
    return 0;
}

Measured memory_bytes: 1408
def resolve():
    N, M, Q = list(map(int, input().split()))
    LR = [list(map(int, input().split())) for _ in range(M)]
    PQ = [list(map(int, input().split())) for _ in range(Q)]
    acc = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for lr in LR:
        l, r = lr
        acc[l][r] += 1
    for i in range(1, N+1):
        for j in range(1, N+1):
            acc[i][j] += acc[i][j-1]
    for i in range(1, N+1):
        for j in range(1, N+1):
            acc[i][j] += acc[i-1][j]
    
    for pq in PQ:
        p, q = pq
        print(acc[q][q] - acc[p-1][q] - acc[q][p-1] + acc[p-1][p-1])


if '__main__' == __name__:
    resolve()

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

const int INF = 1e9;
const int MAX = 100010;
vector<int> edge[MAX];

void bfs(int start, vector<int> &dist) {
	for(int i = 0; i < MAX; ++i) {
		dist[i] = INF;
	}
	queue<pair<int, int>> que;
	que.emplace(start, 0);
	while(not que.empty()) {
		int from, cost;
		tie(from, cost) = que.front();
		que.pop();
		if(dist[from] <= cost) continue;
		dist[from] = cost;
		for(int to : edge[from]) {
			que.emplace(to, cost + 1);
		}
	}
}

int main() {
	int n; cin >> n;
	int u, v; cin >> u >> v;
	--u, --v;
	for(int i = 0; i < n - 1; ++i) {
		int a, b; cin >> a >> b;
		--a, --b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	vector<int> udist(MAX), vdist(MAX);
	bfs(u, udist);
	bfs(v, vdist);
	int ans = 0;
	for(int i = 0; i < n; ++i) {
		if(udist[i] < vdist[i]) {
			ans = max(ans, udist[i] + (vdist[i] - udist[i] - 1));
		}
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 6840
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
#define vec vector<pii>
#define pb push_back
#define iter vector<pii>::iterator
#define _sort(x,y) sort(x.begin(),x.end(),y)
#define N 262150
#define inf 1e9
#define eps 1e-8
using namespace std;
inline int read(){
	int x=0; bool f=1; char c=getchar();
	for(;!isdigit(c); c=getchar()) if(c=='-') f=0;
	for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
	if(f) return x;
	return 0-x;
}

inline int cmpx(pii x,pii y){return x.fi<y.fi;}
inline int cmpy(pii x,pii y){return x.se<y.se;}
int n,son[N][2],w[N][2],d[N];
ll mid,mn[N];
vec f[N];

void solve(vec &ls, vec &rs, vec &s) {
    if(ls.size()>rs.size()) swap(ls,rs);    //启发式合并
    if(!s.empty()) s.clear();
    
    _sort(ls,cmpy), _sort(rs,cmpx);
    mn[0]=rs[0].se;
	for(int i=1; i<rs.size(); i++) mn[i]=min(mn[i-1],rs[i].se);
    for(int p1=0, p2=rs.size()-1; p1<ls.size(); ++p1) {
        while(p2>=0 && ls[p1].se+rs[p2].fi>mid) --p2;
        if(~p2) s.pb(mp(ls[p1].fi,mn[p2]));
    }
    
    _sort(ls,cmpx),_sort(rs,cmpy);
    mn[0]=rs[0].fi;
	for(int i=1; i<rs.size(); i++) mn[i]=min(mn[i-1],rs[i].fi);
    for(int p1=0, p2=rs.size()-1; p1<ls.size(); ++p1) {
        while(p2>=0 && ls[p1].fi+rs[p2].se>mid) --p2;
        if(~p2) s.pb(mp(mn[p2],ls[p1].se));
    }
}

void dfs(int x){
    if(!son[x][0]) return f[x].pb(mp(0,0)),void();
    int l=son[x][0], r=son[x][1];
	dfs(l), dfs(r);
    vec &ls=f[l], &rs=f[r];
    for(iter i=ls.begin(); i!=ls.end(); ++i) i->fi+=w[x][0], i->se+=w[x][0];
    for(iter i=rs.begin(); i!=rs.end(); ++i) i->fi+=w[x][1], i->se+=w[x][1];
    solve(ls,rs,f[x]);
	ls.clear(), rs.clear();
}

int main(){
    n=read();
    int x,y;
    for(int i=2; i<=n; i++) x=read(), y=read(), son[x][d[x]]=i, w[x][d[x]++]=y;
    ll l=0, r=131070ll*131072/2, ans=r;
    while(l<=r) {
        mid=(l+r)>>1;
		dfs(1);
        if(f[1].empty()) l=mid+1;
        else ans=mid, r=mid-1;
		f[1].clear();
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 32628
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <unordered_map>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <memory>


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
long long MOD = 1e9 + 7;
constexpr ll INF = 1e17;

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

    int a, b;
    cin >> a >> b;

    if (a < 10 && b < 10) {
        cout << a * b << endl;
    }
    else {
        cout << -1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	m := make([]int, n+1)
	m[0] = 1
	m[1] = 1

	for i := 2; i <= n; i++ {
		m[i] = m[i-2] + m[i-1]
	}

	fmt.Println(m[n])
}



Measured memory_bytes: 1112
#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define endl '\n' 

void solve() {
    int n ;
    cin >> n ;
    int ans = 0 ;
    vector<int> v(2 * n) ;
    for (auto &x : v) cin >> x ;
    sort(v.begin(), v.end()) ;
    for (int i = 0 ;  i < 2 * n ; i += 2) {
        ans += v[i] ;
    }
    cout << ans << endl ;
}

int32_t main() 
{
    fast ;
    int testcases = 1 ;
    // cin >> testcases ;
    while(testcases--) {
        solve() ;
    }
    return 0  ;
}
/*  CODED BY:-
 ___________________________________
|                       ___         |
|  /\   /\  \ /  |  |  |___   |__|  |        
| /~~\ /~~\  |   |__|   ___|  |  |  |
|___________________________________|
 
*/

Measured memory_bytes: 3636
n,d=map(int,input().split())
import math
zahyou=[]
for i in range(n):
    aha=list(map(int,input().split()))
    zahyou.append(aha)
kazu=0
for i in range(n):
    kyori=math.sqrt(zahyou[i][0]**2+zahyou[i][1]**2)
    if kyori<=d:
        kazu+=1

print(kazu)

Measured memory_bytes: 45456
#include <stdio.h>
#include <stdlib.h>

int main()
{
int A1,A2,A3;
int result;
scanf("%d%d%d",&A1,&A2,&A3);
result=A1+A2+A3;
if(result>=22){
    printf("bust");

}
else {
    printf("win");
}


    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int N, X[500];
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> X[i];
  }
  double pos[500] = {}, ret = 0;
  for(int i = 0; i < N; i++) {
    pos[i] = X[i];
    for(int j = 0; j < i; j++) {
      double A = X[j] + X[i], B = X[j] - X[i];
      pos[i] = max(pos[i], pos[j] + sqrt(A * A - B * B));
    }
    ret = max(ret, pos[i] + X[i]);
  }
  cout << fixed << setprecision(10) << ret << endl;
}

Measured memory_bytes: 1248
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
def main():
  n=int(input())
  A=list(map(int,input().split()))
  B=list(map(int,input().split()))
  C=list(map(int,input().split()))
  A.sort()
  C.sort()
  lc=len(C)
  ans=0
  for b in B:
    ma = bisect_left(A, b)
    mc = lc-bisect_right(C, b)
    ans += ma*mc
  print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 28880
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size,n=1,init=nil) #nに配列の次元数、sizeに配列の大きさ、initに初期値を投げることでその配列を返す
  if n==1
    return Array.new(size){init}
  else
    return Array.new(n).map{Array.new(size){init}}
  end
end

def min(a,b)
  return a>b ? b : a
end
class LazySegTree
  attr_accessor:node,:n,:lazy,:lazyF
  def initialize(n)
    @n=1
    @n*=2 while @n<n
    @node=array(2*@n-1,1,2**31-1)
    @lazy=array(2*@n-1,1,0)
    @lazyF=array(2*@n-1,1,false)
  end

  def lazy_eval(i,l,r)
    if @lazyF[i]
      @node[i]=@lazy[i]
      if r-l>1
        @lazy[i*2+1]=@lazy[i]
        @lazy[i*2+2]=@lazy[i]
        @lazyF[i*2+1]=true
        @lazyF[i*2+2]=true
      end
      @lazyF[i]=false
    end
  end

  def update(s,t,x,i,l,r)
    lazy_eval(i,l,r)
    return if (r<=s or t<=l)
    if(s<=l and r<=t)
      @lazyF[i]=true
      @lazy[i]=x
      lazy_eval(i,l,r)
    else
      mid=(l+r)/2
      update(s,t,x,i*2+1,l,mid)
      update(s,t,x,i*2+2,mid,r)
      @node[i]=min(@node[i*2+1],@node[i*2+2])
    end
  end

  def find(s,t,i,l,r)
    return 2**31-1 if r<=s or t<=l
    lazy_eval(i,l,r)

    return @node[i] if s<=l and r<=t
    mid=(l+r)/2
    leaf_l=find(s,t,i*2+1,l,mid)
    leaf_r=find(s,t,i*2+2,mid,r)
    return min(leaf_l,leaf_r)
  end
end
n,q=get_i

lst=LazySegTree.new(n)
q.times do
  que=get_i
  if que[0].zero?
    lst.update(que[1],que[2]+1,que[3],0,0,lst.n) 
  else
    puts lst.find(que[1],que[2]+1,0,0,lst.n)
  end
end


Measured memory_bytes: 13148
#include<stdio.h>

int main()
{
  int a=0, b=0;
  scanf("%d %d", &a, &b);
  if (a < b) {
    printf("a < b\n");
  }else if (a > b) {
    printf("a > b\n");
  }else{
    printf("a == b\n");
  }

  return 0;
}

Measured memory_bytes: 580
module Main where

import Data.Functor

main :: IO ()
main =  do
 { [n,m] <- getInts
 ; mat <- loop1 n
 ; vec <- loop2 m
 ; putStr $ unlines $ map show [sum $ zipWith (*) l vec | l <- mat]
 }

loop1 :: Int -> IO [[Int]]
loop1 0 = return []
loop1 n = do
  { l <- getInts
  ; ls <- loop1 (n-1)
  ; return (l:ls)
  }

loop2 :: Int -> IO [Int]
loop2 0 = return []
loop2 n = do
  [v] <- getInts
  vs  <- loop2 (n-1)
  return (v:vs)

getInts :: IO [Int]
getInts = map read . words <$> getLine

Measured memory_bytes: 7528
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int a, b, c, d, f;
	double e;
	cin >> a >> b >> c >> d >> e >> f;
	vector<int> water;
	for(int i=0; 100*a*i<=f; i++){
		for(int j=0; 100*a*i+100*b*j<=f; j++)
			water.push_back(100*a*i+100*b*j);
	}
	vector<int> sugar;
	for(int i=0; c*i<=f; i++){
		for(int j=0; c*i+d*j<=f; j++)
			sugar.push_back(c*i+d*j);
	}
	e = e/(e+100)*100;
	double pmax=0;
	int g=100*a, s=0;
	for(int i=0; i<water.size(); i++){
		for(int j=0; j<sugar.size(); j++){
			if(water[i]!=0 && water[i]+sugar[j]<=f){
				double per = (double)sugar[j]/(water[i]+sugar[j])*100;
				if(per<=e && per>pmax){
					pmax = per;
					g = water[i]+sugar[j];
					s = sugar[j];
				}
			}
		}
	}
	cout << g << ' ' << s << endl;
	return 0;
}

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

typedef long long LL;

void setIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}

int main() {
    setIO();
    LL a, b, c, d;
    cin>>a>>b>>c>>d;
    LL r = a*c;
    r = max(r, a*d);
    r = max(r, c*b);
    r = max(r, b*d);
    cout<<r<<endl;
    return 0;
}

Measured memory_bytes: 3616
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = input()
    if N[-1] == "2" or N[-1] == "4" or N[-1] == "5" or N[-1] == "7" or N[-1] == "9":
        print("hon")
    elif N[-1] == "0" or N[-1] == "1" or N[-1] == "6" or N[-1] == "8":
        print("pon")
    else:
        print("bon")
    



if __name__ == "__main__":
    main()


Measured memory_bytes: 61700
using System;

class AGC_034_A
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]);
        int A = int.Parse(input[1]);
        int B = int.Parse(input[2]);
        int C = int.Parse(input[3]);
        int D = int.Parse(input[4]);

        string S = Console.ReadLine();

        int[] SArray = new int[N];
        int counter = 0;
        for (int i = 0; i < N; i++)
        {
            if (S[i] == '#') counter++;
            else counter = 0;

            SArray[i] = counter;
        }

        for (int i = A; i < C; i++)
        {
            if(SArray[i]>1)
            {
                Console.WriteLine("No");
                return;
            }
        }

        for (int i = B; i < D; i++)
        {
            if (SArray[i] > 1)
            {
                Console.WriteLine("No");
                return;
            }
        }

        if(D<C)
        {
            int spaceCount = 0;
            for (int i = B-2; i <= D; i++)
            {
                if (SArray[i] == 0) spaceCount++;
                else spaceCount = 0;

                if (spaceCount >= 3) break;
            }
            if (spaceCount<3)
            {
                Console.WriteLine("No");
                return;
            }
        }

        Console.WriteLine("Yes");
    }
}

Measured memory_bytes: 13144
import java.util.Scanner;

public class Main {

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

		k = sc.nextInt();

		dfs(0);

	}

	static int k;
	static final int DEPTH_MAX = 12;
	static int[] digits = new int[DEPTH_MAX];
	static int count = 1;


	static void dfs(int depth){
		if(depth == DEPTH_MAX){
			if(digits[DEPTH_MAX - 1] == -1){
				return;
			}
//			System.out.print(count+" ");
			if(count == k){
				printDigits();
			}

			count++;
			return;
		}

		int start = 0;
		if(depth == 0 || digits[depth - 1] == -1){
			start = -1;
		}
		for(int i = start; i <= 9; i++){
			if(i == 0 && (depth == 0 || digits[depth - 1] == -1)){
				continue;
			}
			if(i == -1 || (depth >= 1 && (digits[depth - 1] == -1 || Math.abs(digits[depth - 1] - i) <= 1))){
				digits[depth] = i;
				dfs(depth + 1);
 			}
		}
	}

	static void printDigits(){
		for(int i = 0; i < DEPTH_MAX; i++){
			if(digits[i] != -1){
				System.out.print(digits[i]);
			}
		}
		System.out.println();
	}

}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
 
using namespace std;
 
int H, W, N, y, x;
char field[25][25], order[120];
 
bool inField(int _y, int _x){
  return (0 <= _x && _x < W && 0 <= _y && _y < H);
}
 
void funcU(){
  field[y][x] = '^';
 
  int ny = y-1, nx = x;
  if(!inField(ny,nx)) return;
  if(field[ny][nx] != '.') return;
  field[y][x] = '.';
  y = ny; x = nx;
  field[y][x] = '^';
}
 
void funcD(){
  field[y][x] = 'v';
 
  int ny = y+1, nx = x;
  if(!inField(ny,nx)) return;
  if(field[ny][nx] != '.') return;
  field[y][x] = '.';
  y = ny; x = nx;
  field[y][x] = 'v';
}
 
void funcL(){
  field[y][x] = '<';
 
  int ny = y, nx = x-1;
  if(!inField(ny,nx)) return;
  if(field[ny][nx] != '.') return;
  field[y][x] = '.';
  y = ny; x = nx;
  field[y][x] = '<';
}
 
void funcR(){
  field[y][x] = '>';
 
  int ny = y, nx = x+1;
  if(!inField(ny,nx)) return;
  if(field[ny][nx] != '.') return;
  field[y][x] = '.';
  y = ny; x = nx;
  field[y][x] = '>';
}
 
void shoot(){
  int dir;
  int dx[4] = {0,0,-1,1};
  int dy[4] = {-1,1,0,0};
 
  switch(field[y][x]){
  case '^':
    dir = 0;
    break;
  case 'v':
    dir = 1;
    break;
  case '<':
    dir = 2;
    break;
  case '>':
    dir = 3;
    break;
  }
  int tx = x, ty = y;
  while(true){
    int nx = tx + dx[dir];
    int ny = ty + dy[dir];
 
    if(!inField(ny,nx)) return;
    if(field[ny][nx] == '.' || field[ny][nx] == '-'){
      tx = nx; ty = ny;
      continue;
    }else if(field[ny][nx] == '*'){
      field[ny][nx] = '.';
      return;
    }else{
      return;
    }
  }
}
 
void print(){
  for(int i = 0 ; i < H ; i++){
    for(int j = 0 ; j < W ; j++){
      if(j == W-1){
        cout << field[i][j] << endl;
      }else{
        cout << field[i][j];
      }
    }
  }
}
 
void solve(){
  for(int i = 0 ; i < N ; i++){
    switch(order[i]){
    case 'U':
      funcU();
      break;
    case 'D':
      funcD();
      break;
    case 'L':
      funcL();
      break;
    case 'R':
      funcR();
      break;
    default:
      shoot();
      break;
    }
  }
  print();
}
 
int main(){
  int Tc;
  bool flg = false;
 
  cin >> Tc;
  while(Tc--){
    string str;
    if(flg) cout << endl;
    cin >> H >> W;
    for(int i = 0 ; i < H ; i++){
      cin >> str;
      for(int j = 0 ; j < W ; j++){
        field[i][j] = str[j];
        if(str[j] == '^' || str[j] == 'v' ||
           str[j] == '<' || str[j] == '>'){
          y = i, x = j;
        }
      }
    }
    cin >> N;
    for(int i = 0 ; i < N ; i++){
      cin >> order[i];
    }
    solve();
    flg = true;
  }
 
  return 0;
}

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

///Author:Refat(BSMRSTU)///

#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define pil pair<int,ll>
const int N = 1e5 + 5;
const int M = 1e9 + 7;
double pi=2*acos(0.0);
int Set(int N,int pos) {
    return N=N | (1<<pos);
}
int reset(int N,int pos) {
    return N= N & ~(1<<pos);
}
bool check(int N,int pos) {
    return (bool)(N & (1<<pos));
}
int ar[2005];
int binarysearch(int v1,int v2,int l,int r) {
    int ans=0;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(v1+v2>ar[mid]) {
            l=mid+1;
            ans=mid;
        } else {
            r=mid-1;
        }
    }
    return ans;
}
int main() {
    /// freopen("input.txt","r",stdin);
    /// freopen("output.txt","w",stdout);
    int n,total=0;
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d",&ar[i]);
    }
    // total=(n*(n-1)*(n-2))/6;
    sort(ar+1,ar+n+1);
    /*for(int i=1; i<=n; i++) {
       cout<<ar[i]<<" ";
    }cout<<endl;*/
    for(int i=1; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            int pos=binarysearch(ar[i],ar[j],j+1,n);
            //cout<<pos<<" "<<i<<" "<<j<<endl;
            if(pos!=0)
                total+=(pos-(j+1)+1);
        }
    }
    printf("%d\n",total);
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;

int dp[2010][2010];
int N;
VP P;

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

	cin >> N;
	P.resize(N);
	REP(i, N) {
		cin >> P[i].first;
		P[i].second = i;
	}

	rSORT(P);
	REP(i, 2010)REP(j, 2010)dp[i][j] = -INF;
	dp[0][0] = 0;

	FOR(i, 0, N) {//i+1個選ぶとする
		
		int a = P[i].first, b = P[i].second;

		eREP(j, i) {//左側にj+1個もしくはj個


			chmax(dp[j + 1][i - j], dp[j][i - j] + abs(b - j)*a);
			chmax(dp[j][i - j + 1], dp[j][i - j] + abs(N - b - 1 - (i-j))*a);
		}
	}

	int ans = 0;
	eREP(i, N)chmax(ans, dp[i][N - i]);

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 35240
import java.util.*;
import static java.lang.System.*;

public class Main {

	Scanner sc = new Scanner(in);
	
	void run() {
		while (true) {
			int n = sc.nextInt();
			if (n == 0) break;
			int a = 0, b = 0;
			for (int i = 0; i < n; i++) {
				int ta = sc.nextInt(), tb = sc.nextInt();
				if (ta > tb)
					a += ta + tb;
				else if (ta < tb)
					b += ta + tb;
				else {
					a += ta;
					b += tb;
				}
			}
			out.printf("%d %d\n", a, b);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

}

Measured memory_bytes: 53144
N = int(input())
A = list(map(int, input().split()))
def solve(N,A):
    liss = []
    lis = []
    lis.append(A[0])
    a = A[0]
    for i in range(1,N):
        if len(lis)==1 or prev==0:
            if A[i]>a:
                prev = 1
            elif A[i]<a:
                prev = -1
            else:
                prev = 0
        elif (A[i]-a)*prev<0:
            liss.append(lis)
            lis = []
        lis.append(A[i])
        a = A[i]
    liss.append(lis)
    ans = len(liss)
    return ans
print(solve(N,A))

Measured memory_bytes: 14436
#include <iostream>
#include <sstream>
#include <iterator>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <list>
#include <cmath>

#define YESNO(x) x ? printf("YES") : printf("NO")
#define YesNo(x) x ? printf("Yes") : printf("No")
#define scani(x) scanf("%d", &x)
#define scanll(x) scanf("%lld", &x)
#define printi(x) printf("%d", x)
#define printll(x) printf("%lld", x)

using namespace std;

//ABC131C - Anti-Division

long long GCD(long long x, long long y) {
	return y ? GCD(y, x % y) : x;
}

long long LCM(long long x, long long y) {
	return x * y / GCD(x, y);
}

long long func(long long x, long long c, long long d) {
	return x - x / c - x / d + x / LCM(c, d);
}

int Main() {
	long long a, b, c, d;
	long long ans = 0;

	scanll(a);
	scanll(b);
	scanll(c);
	scanll(d);

	ans = func(b, c, d) - func(a - 1, c, d);

	printll(ans);

	return 0;
}

int main()
{
	Main();
	return 0;
}


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

int main(){

    int N;
    cin >> N;

    string temp = to_string(N);

    for(int i= 0;i < 3;i++){
        if(temp[i]=='7'){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" <<endl;

    return 0;
}

Measured memory_bytes: 3704
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,o,k,t;
int a[18];
int vis[58][58][58];
int ab[6][3]= {1,0,0,-1,0,0,0,0,1, 0,1,0, 0,0,-1, 0,-1,0};
queue<int> w;
int ans=0;
int main()
{
    int i,j;
    for(i=0;i<3;i++)
        scanf("%d",&a[i]);
    sort(a,a+3);
    int sum=a[0]+a[1];
    printf("%d\n",sum);
    return 0 ;
}

Measured memory_bytes: 256
n = int(input())
a = [0]
for i in list(map(int, input().split())):
    a.append(i)
a.append(0)

cost = 0
for i in range(len(a) - 1):
    cost += abs(a[i] - a[i + 1])

for i in range(1, n + 1):
    if a[i - 1] <= a[i] <= a[i + 1] or a[i - 1] >= a[i] >= a[i + 1]:
        print(cost)
    else:
        dec = abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i])
        inc = abs(a[i + 1] - a[i - 1])
        print(cost - dec + inc)


Measured memory_bytes: 14172
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(vec) vec.begin(),vec.end()
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;

int main() {
  ll K; cin >> K;
  ll sum=0;
  
  rep(i,1e8){
    sum = sum*10 +7;
    sum%=K;
    if(sum == 0){
      cout << i+1 << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 3632
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

/*BigInteger
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
namespace xxx = boost::multiprecision;
using Bint = xxx::cpp_int;
using Real = xxx::number<xxx::cpp_dec_float<1024>>;
*/

#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0LL, sizeof(x))
#define mm(x) memset((x), -1LL, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define Bit(n) (1LL << (n))
#define Bitset(a, b) (a) |= (1LL << (b))
#define Bitunset(a, b) (a) &= ~(1LL << (b))
#define Bitcheck(a, b) ((((a) >> (b)) & 1LL) == 1LL)
#define Bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
constexpr int INF = (int)1e18;
constexpr int MOD = (int)1e9 + 7;
constexpr double PI = (double)acos(-1);
constexpr double EPS = (double)1e-10;
constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
} Accelerate_Cin;

signed main() {
  string s;
  cin >> s;
  int N = s.size();

  map<char, int> mp;
  for (int i = 0; i < N; i++) {
    mp[s[i]]++;
  }

  int a = mp['a'], b = mp['b'], c = mp['c'];
  int mx = max({a, b, c}), mn = min({a, b, c});
  if (abs(mx - mn) <= 1) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>	
#define pb push_back
typedef long long ll;
const int inf = 2e9;
using namespace std;


int main(){
	char S[10];
	scanf("%s",S);
	set<char> c;
	for (int i = 0; i < strlen(S); ++i)
	{
		if(S[i]=='a'||S[i]=='b'||S[i]=='c'){
			c.insert(S[i]);
		} else return !printf("No\n");
	}

	if(c.size()==3)printf("Yes\n"); 	
	else printf("No\n");

	return 0;
}	

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

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 1010, M = 3;

int n, m;
LL w[N][M];
LL val[N];

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i ++ )
		for (int j = 0; j < M; j ++ )
		 	cin >> w[i][j];
		 	
	LL res = -1e18;
	for (int i = 0; i < 1 << M; i ++ )
	{
		for (int j = 0; j < n; j ++ )
		{
			LL t = 0;
			for (int k = 0; k < M; k ++ )
				if ((i >> k) & 1) t += w[j][k];
				else t -= w[j][k];

			val[j] = t;
		}
		sort(val, val + n);
		reverse(val, val + n);
		
		LL t = 0;
		for (int i = 0; i < m; i ++ ) t += val[i];
		res = max(res, t);
	}
	
	cout << res << endl;
	
	
	return 0;
}

Measured memory_bytes: 256
package main

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

type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func primeFactors(n int) map[int]int {
	pfs := make(map[int]int)
	for n%2 == 0 {
		pfs[2]++
		n = n / 2
	}
	for i := 3; i*i <= n; i = i + 2 {
		for n%i == 0 {
			pfs[i]++
			n = n / i
		}
	}
	if n > 2 {
		pfs[n]++
	}

	return pfs
}

func main() {
	sc := NewScanner()
	N := sc.nextInt()
	P := sc.nextIntSlice(N)
	lGcd := make([]int, N)
	rGcd := make([]int, N)
	first := P[0]
	for i := 0; i < N; i++ {
		first = gcd(P[i], first)
		lGcd[i] = first
	}

	last := P[N-1]
	for i := N - 1; i >= 0; i-- {
		last = gcd(P[i], last)
		rGcd[i] = last
	}
	max := 0
	for i := 0; i < N; i++ {
		g := 0
		if i == 0 {
			g = rGcd[i+1]
		} else if i == N-1 {
			g = lGcd[i-1]
		} else {
			g = gcd(lGcd[i-1], rGcd[i+1])
		}
		if max < g {
			max = g
		}
	}
	fmt.Println(max)
}


Measured memory_bytes: 4736
X,Y=map(int,input().split())

def getMoney(n):
    if (n==1):
        return 300000
    elif (n==2):
        return 200000
    elif (n==3):
        return 100000
    else:
        return 0

base=0

if (X==1 and Y==1):
    base+=400000

base+=getMoney(X)
base+=getMoney(Y)

print(base)

Measured memory_bytes: 3316
N=gets.to_i

MEMO=Array.new(10) { Array.new(10,0) }
(1..N).each do |n|
    ns=n.to_s
    MEMO[ns[0].to_i][ns[-1].to_i]+=1
end

ret = 0
(1..9).each do |i|
    (1..9).each do |j|
        ret += MEMO[i][j] * MEMO[j][i]
    end
end
puts ret


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

int main()
{
    int64_t n;
    cin >> n;
    int64_t a[n];
    for (auto &i : a)
    {
        cin >> i;
    }
    int64_t ans = 0;
    for (auto &i : a)
    {
        while (i && i % 2 == 0)
        {
            ans++;
            i /= 2;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;
const ll mod = 1000000007;
constexpr ll INF = 1000000000000000ll;

struct Mod {
  ll n;
  Mod () : n(0) {;}
  Mod (ll m) : n(m) {
    if (n >= mod) n %= mod;
    else if (n < 0) n = (n % mod + mod) % mod;
  }
  operator ll() { return n; }
};

bool operator==(Mod a, Mod b) { return a.n == b.n; }
Mod operator+=(Mod &a, Mod b) { a.n += b.n; if (a.n >= mod) a.n -= mod; return a; }
Mod operator-=(Mod &a, Mod b) { a.n -= b.n; if (a.n < 0) a.n += mod; return a; }
Mod operator*=(Mod &a, Mod b) { a.n = (a.n * b.n) % mod; return a; }
Mod operator+(Mod a, Mod b) { return a += b; }
Mod operator-(Mod a, Mod b) { return a -= b; }
Mod operator*(Mod a, Mod b) { return a *= b; }
Mod operator^(Mod a, ll n) {
  if (n == 0) return Mod(1);
  Mod res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}

Mod pow2(ll n) {
  return Mod(2) ^ n;
}

int main()
{
  ll n;
  cin>>n;
  vector<ll> h(n+2);
  REP(i,n) cin>>h[i+1];
  vector<Mod> dpa(n, 2), dpb(n, 0);
  set<ll> sh;
  REP(i,n) {
    sh.insert(h[i+1]);
    if (h[i] == h[i+1]) {
      dpb[i] = Mod(2)*dpb[i-1] + Mod(2);
    }
  }
  for_each(rbegin(sh), rend(sh), [&](ll hi) {
    set<int> pos;
    REP(i,n) {
      if (h[i+1] == hi) {
        pos.insert(i);
      }
    }
    for (int p : pos) {
      int l, r;
      for (l = p-1; l >= 0; --l) {
        if (h[l+1] < hi) break;
      }
      for (r = p+1; r < n; ++r) {
        if (h[r+1] < hi) break;
      }
      bool old = false, old2 = true;
      vector<ll> minh(1, INF);
      int cnt = 0;
      vector<Mod> vdpa, vdpb;
      FOR(i,l+1,r) {
        if (h[i+1] == hi) {
          if (!old2) {
            minh.push_back(INF);
          }
          old = false;
          old2 = true;
          ++cnt;
          continue;
        }
        if (h[i+1] <= minh.back()) {
          minh.back() = h[i+1];
          if (old) {
            vdpa.back() = dpa[i];
            vdpb.back() = dpb[i];
          } else {
            vdpa.emplace_back(dpa[i]);
            vdpb.emplace_back(dpb[i]);
          }
          old = true;
          old2 = false;
        }
      }
      if (vdpa.empty()) continue;
      Mod a = 1;
      REP(i, vdpa.size()) {
        a *= vdpa[i] * pow2(minh[i] - hi - 1);
      }
      Mod b = 1;
      REP(i, vdpa.size()) {
        b *= Mod(2)*(vdpa[i] * pow2(minh[i] - hi - 1)) + vdpb[i];
      }
      Mod mb = 1;
      REP(i, vdpa.size()) {
        mb *= Mod(2)*(vdpa[i] * pow2(minh[i] - hi - 1));
      }
      cerr << p << ' ' << a << ' ' << b << ' ' << mb << ' ' << cnt << endl;
      b -= mb;
      dpa[p] = a*Mod(2);
      dpb[p] = a * (pow2(cnt+vdpa.size()) - Mod(2)) + b * pow2(cnt);
    }
  });
  int mn = 0;
  ll mnh = INF;
  REP(i,n) {
    cerr << dpa[i] << ' ' << dpb[i] << endl;
    if (h[i+1] <= mnh) {
      mnh = h[i+1];
      mn = i;
    }
  }
  cout << dpa[mn] * pow2(mnh-1) + dpb[mn] << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<vector>
#include<string>
using namespace std;
#define l long long
#define pb push_back
#define mem(a,n) memset(a,n,sizeof(a))
#define find(v,n) find(v.begin(),v.end(),n)
#define sort1(v) sort(v.begin(),v.end())
#define lb(v,n) lower_bound(v.begin(),v.end(),n)-v.begin()
#define ub(v,n) upper_bound(v.begin(),v.end(),n)-v.begin()
#define mod 1000000007
#define reverse(s) reverse(s.begin(),s.end())
//#define pi pair<l,l> 
const double pi=3.141592653589793;
bool isprime(l n)
{
	for(l i=2;i*i<=n;i++)
	{
		if(n%i==0)
			return false;
	}
	return true;
}
/*bool fact(l n)
{
	vector<l> v;
	for(l i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			if(i%2==1||(n/i)%2==1)
			{
				return true;
			}
		}
	}
	return false;
}*/
/*l power(l a,l b)
{
	l ans=1;
	while(b>0)
	{
		if(b&1)
		{
			ans=(ans*a);
		}
		b>>=1;
		a=(a*a);
	}
	return ans;
}//prefixsums*/
/*vector<vector<l> > c(100000);
void dfs(vector<l> v[],l root,bool vis[])
{
	vis[root]=true;
	//cout<<root<<"\n";
	for(l i=0;i<v[root].size();i++)
	{
		if(vis[v[root][i]]==false)
		{
			c[root].pb(v[root][i]);
			dfs(v,v[root][i],vis);
		}
	}
}*/
void frooty()
{
	 l n,d;
	 cin>>n>>d;
	 l ans=0;
	 for(l i=0;i<n;i++)
	 {
	 	l a,b;
	 	cin>>a>>b;
	 	if((a*a)+(b*b)<=d*d)
	 		ans++;
	 }
	 cout<<ans<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int q=1;
	//cin>>q;
	//q++;
	for(int i=0;i<q;i++)
	{
		frooty();
	}
}

Measured memory_bytes: 3656
#include <stdio.h>

int main()
{
	int n;
	while(scanf("%d", &n)!=EOF) {
		int a, b, c, d, ans=0;
		for(a=0;a<=9;a++) {
			for(b=0;b<=9;b++) {
				for(c=0;c<=9;c++) {
					for(d=0;d<=9;d++) {
						if(a+b+c+d==n) ans++;
					}
				}
			}
		}
	printf("%d\n", ans);
	}			
	return (0);
}


Measured memory_bytes: 2040
#include<stdio.h>
int main(void)
{
 int num=0;
 int max=0;
 int i;
 char s[11];
 scanf("%s",s);
 for(i=0;i<10;i++){
         if(s[i]=='A'||s[i]=='C'||s[i]=='G'||s[i]=='T')
            num++;
         else
            num=0;
     if(max<num)
        max=num;
 }
 printf("%d",max);
  return 0;
}

Measured memory_bytes: 128
using System;

namespace HowManyDivisors
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			int[] data = getInputdata (" ");

			int d, r;
			double f;

			d = data [0] / data [1];
			r = data [0] % data [1];
			f = (double)(data[0])/(double)(data[1]);

			Console.WriteLine("{0} {1} {2}", d, r, f.ToString("f6"));

		}
		public static int[] getInputdata (string token)
		{
			string[] data = Console.ReadLine ().Split (token.ToCharArray ());
			int[] idata = new int[data.Length];

			for (int i = 0; i < data.Length; i++) {
				idata [i] = int.Parse (data [i]);
			}
			return idata;
		}


	}
}

Measured memory_bytes: 17968
N = int(input())

max_min = 0
cumsum = 0
while cumsum <= 10 ** 7:
    max_min += 1
    cumsum += max_min
    if N <= cumsum:
        break

ans = [i + 1 for i in range(max_min)]
rm_value = cumsum - N
if rm_value != 0:
    ans.remove(rm_value)

for i in ans:
    print(i)


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e5+5;

ll dp[N];

int main()
{
	int n, W;
	cin >> n >> W;
	memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	for (int i = 0; i < n; i++)
	{
		int w, v;
		cin >> w >> v;
		for (int j = N-5; j >= v; j--)
			dp[j] = min(dp[j], dp[j-v] + w);
	}
	for (int i = N-5; i >= 0; i--)
	{
		if (dp[i] != inf && dp[i] <= W)
		{
			cout << i;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

map<ll, ll> prime_factorization(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while(n >= a*a){
    if(n % a == 0){
      ans[a]++;
      n /= a;
    }else{
      a++;
    }
  }
  ans[n]++;

  return ans;
}

int main(){
  ll n;
  cin >> n;
  if(n == 1){
    cout << 0 << endl;
    return 0;
  }
  auto pm = prime_factorization(n);
  ll ans = 0;
  for(auto p : pm){
    int sum = 0;
    int co;
    for(co = 1; ; co++){
      sum += co;
      if(sum > p.second) break;
    }
    co--;
    // cerr << p.first << " " << p.second << " " << co << endl;
    ans += co;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
//C
#include <cassert>
//#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//ここまで標準include

using namespace std;

long aCb(long a, long b) {
	long out = 1;
	for (long i = 1; i <= b; i++) {
		out = out * (a + 1 - i) / i;
	}
	return out;
}

int main() {
	int n, a, b;
	cin >> n >> a >> b;
	cout << min(n * a, b) << endl;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
List = [input() for i in range(H)]
queue = [(0, 0, 1)]
cout = sum([row.count("#") for row in List])
used = [(0, 0)]


def check(x, y, c):
    if x > W - 1 or y > H - 1 or x < 0 or y < 0:
        return
    if List[y][x] == '#':
        return
    if (x, y) in used:
        return
    queue.append((x, y, c))
    used.append((x, y))

f = -1
final =  0
while queue:
    x, y, c = queue.pop(0)
    if x == W - 1 and y == H - 1:
        f = 1
        final = c
        break
    check(x + 1, y, c + 1)
    check(x, y + 1, c + 1)
    check(x - 1, y, c + 1)
    check(x, y - 1, c + 1)

print(f if f == -1 else(H * W - final - cout))

Measured memory_bytes: 3188
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		char in = scanner.next()
						 .charAt(0);
		char c = 0;
		switch (in)
		{
			case 'A':
				c = 'T';
				break;
			case 'T':
				c = 'A';
				break;
			case 'G':
				c = 'C';
				break;
			case 'C':
				c = 'G';
				break;
		}
		System.out.println(c);
	}
}


Measured memory_bytes: 20948
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

main = do
  [n, m, q] <- getIntList
  qs <- V.replicateM q $ do
    [a, b, c, d] <- getIntList
    return (a, b, c, d)

  let dfs len xs
        | len == n  = score xs
        | len == 0  = maximum [dfs 1 [x] | x <- [1..m]]
        | otherwise = let x = head xs
                      in maximum [dfs (len+1) (y:xs) | y <- [x..m]]

      score xs = let v = V.fromList xs
                 in V.sum $ V.map (\(a, b, c, d) ->
                                     if v V.! (n-b) - v V.! (n-a) == c
                                     then d
                                     else 0) qs

  print $ dfs 0 []

Measured memory_bytes: 5224
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N,M,z=0;
	cin>>N>>M;
	vector<int> A(M);
	for(int i=0;i<M;i++)
	cin>>A[i];
	for(int j=0;j<M;j++)
	z+=A[j];
	if  (z<=N)
	cout<<N-z;
	else cout<<-1;
	
	
}

Measured memory_bytes: 3600