akhauriyash/Code-Regression huggingface dataset:
h , w = map(int,input().split())
S = [input() for i in range(h)]

dxy = [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]

ans = [''] * h

for y in range(h):
    for x in range(w):
        if S[y][x] == '#':
            ans[y] += '#'
        else:
            b = 0
            for dx,dy in dxy:
                nx, ny = x + dx , y + dy
                if not 0 <= nx < w: continue
                if not 0 <= ny < h: continue
                if S[ny][nx] == '#':
                    b += 1
            
            ans[y] += str(b)

print(*ans,sep = '\n')

Measured memory_bytes: 3316
#include <stdio.h>

int n;
int sx[10];
int sy[10];

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

int tansaku(int x,int y,int now) {
	int i;
	if(now>n)return 1;
	if(x<0 || x>9 || y<0 || y>9)return 0;
	if(now>0 && (x<sx[now-1]-1 || sx[now-1]+1<x ||
		y<sy[now-1]-1 || sy[now-1]+1<y))return 0;
	for(i=0;i<12;i++) {
		if(tansaku(x+dx[i],y+dy[i],now+1))return 1;
	}
	return 0;
}

int main(void) {
	int x,y;
	int i;
	while(1) {
		scanf("%d%d",&x,&y);
		if(x==0 && y==0)break;
		scanf("%d",&n);
		for(i=0;i<n;i++)scanf("%d%d",&sx[i],&sy[i]);
		puts(tansaku(x,y,0)?"OK":"NA");
	}
	return 0;
}

Measured memory_bytes: 584
import java.util.*;

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

        int n = sc.nextInt();
        int[] A = new int[n];
        for(int i = 0;i < n;i++){
            A[i] = sc.nextInt();
        }

        int q = sc.nextInt();
        for(int i = 0;i < q;i++){
            int b = sc.nextInt();
            int e = sc.nextInt();
            int t = sc.nextInt();
            int tmp = 0;

            for(int k = 0;k < (e - b);k++){
                tmp = A[b + k];
                A[b + k] = A[t + k];
                A[t + k] = tmp;            
            }
        }

        for(int i = 0;i < n;i++){
            if(i != 0)  System.out.print(" ");
            System.out.print(A[i]);
        }
        System.out.println();
    }
}


Measured memory_bytes: 37072
#include <bits/stdc++.h>
using namespace std ;
#define An setprecision(16) 
int main(){
    int N;
    cin >> N;
    int A[N];
    for(int i=0;i<N;i++)cin >> A[i];
    int flag=0;
    for(int i=0;i<N;i++){
        if(A[i]%2==0){
            if(A[i]%3!=0&&A[i]%5!=0)flag--;
        }
    }
    if(flag==0)cout<<"APPROVED\n";
    else cout<<"DENIED\n";
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  for(int i = 0; i < N ; i++)
      cin >> d.at(i);
  sort(d.begin(),d.end());
  int count = 1;
  if(N > 1){
    for(int i = 0; i < N-1; i++){
      if(d.at(i) < d.at(i+1))
        count++;
    }
  }
  cout << count <<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

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

    ll a[n],f[n];
    for(int i=0;i<n;i++)
        cin>>a[i];

    for(int i=0;i<n;i++)
        cin>>f[i];

    sort(a,a+n);
    sort(f,f+n);

    ll hi=1e12,lo=0,mid,ans,res=0;

    while(hi>=lo){
        mid=(hi+lo)/2;
        res=0;
        for(int i=0;i<n;i++){
            if(a[i]*f[n-1-i]>mid){
                res+=(a[i]-(mid/f[n-i-1]));
            }
        }

        if(res<=k){
            ans=mid;
            hi=mid-1;
        }
        else{
            lo=mid+1;
        }
    }

    cout<<ans;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  string s;
  cin >> s;
  int n=s.size();
  int cnt=0;
  rep(i,n){
    if(s[i]=='0')cnt++;
  }
  cout << 2*min(cnt,n-cnt) << endl;
}


Measured memory_bytes: 512
n,k=map(int,input().split())
*p,=map(int,input().split())
*c,=map(int,input().split())

ans=-10**20
for i in range(n):
    loop=1
    j=p[i]-1
    acm=[c[j]]
    while j!=i:
        j=p[j]-1
        acm.append(acm[-1]+c[j])
        loop+=1
    
    if acm[-1]>0:
        if k<=loop:
            cur=max(acm[:k])
        else:
            cur=(k//loop)*acm[-1]
            if k%loop>0:
                cur=max(cur,cur+max(acm[:k%loop]))
            else:
                cur-=acm[-1]
                cur+=max(acm)
    else:
        cur=max(acm[:min(k,loop)])
    
    ans=max(cur,ans)
    
print(ans)

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

int main(){
    int N;
    cin >> N;
    for (int i = 0; i < 26; i++)
    {
        for (int j = 0; j < 15; j++)
        {
            if(4*i+7*j == N){
                cout << "Yes" << endl;
                return 0;
            }
        }
        
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vec=vector<ll>;
using mat=vector<vec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
#define endl "\n"
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}while(0)
using datas=pair<ll,ll>;
using tdata=pair<ll,datas>;

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll modncrlistp[200000],modncrlistm[200000];

ll modncrs(ll n,ll r){
  ll i,j;
  if(modncrlistp[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistp[i])break;
    }
    if(i<0){
      modncrlistp[0]=1;
      rep1(i,n+1){
        modncrlistp[i]=(modncrlistp[i-1]*i)%mod;
      }
    }else{
      For(j,i+1,n+1){
        modncrlistp[j]=(modncrlistp[j-1]*j)%mod;
      }
    }
  }
  if(modncrlistm[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistm[i])break;
    }
    if(i<0){
      modncrlistm[0]=1;
      rep1(i,n+1){
        modncrlistm[i]=(modncrlistm[i-1]*modinv(i))%mod;
      }
    }else{
      For(j,i+1,n+1)modncrlistm[j]=(modncrlistm[j-1]*modinv(j))%mod;
    }
  }
  return (((modncrlistp[n]*modncrlistm[r])%mod)*modncrlistm[n-r])%mod;
}

ll euclidean_gcd(ll a, ll b) {
  if(a<b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)){a=b;b=r;}
  return b;
}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

void printmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  For(i,0,H+2){
    For(j,0,W+2){cout<<a[i*(W+2)+j];}
    cout<<endl;
  }
}
void inputmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  string ss;
  For(i,1,H+1){
    cin>>ss;
    For(j,1,W+1){
      if(ss[j-1]=='#'){
        a[i*(W+2)+j]=1;
      }else{
        a[i*(W+2)+j]=0;
      }
    }
  }
}
ll lpow(ll a,ll b){
  ll i,res=1;
  rep(i,b){
    res*=a;
  }
  return res;
}

struct sumsegtree{
  ll N;
  vec tree;
  sumsegtree(ll K){
    N=1;
    while(N<K)N*=2;
    tree.resize(2*N-1,0);
  }
  void input(ll i,ll a){
    i+=N-1;
    tree[i]+=a;
    while(i){
      i=(i-1)/2;
      tree[i]=tree[i*2+1]+tree[i*2+2];
    }
  }
  ll res(ll a,ll b,ll k,ll l,ll r){
    if(r<0)r=N;
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b)return tree[k];
    ll vl=res(a,b,2*k+1,l,(l+r)/2);
    ll vr=res(a,b,2*k+2,(l+r)/2,r);
    return vl+vr;
  }
  ll q(ll a,ll b){
    return res(a,b,0,0,-1);
  }
  void prt(){
    output(tree);
  }
};
int main(){
  ll N,i;
  cin>>N>>i;
  cout<<euclidean_gcd(N,i)<<endl;
  return 0;
}


Measured memory_bytes: 3088
#include<iostream>
#include<vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
const int MOD = 1000000007;

using namespace std;

int main(){
    int n,m;
    scanf("%d %d",&n,&m);

    vector<bool> issafe(n+1,true);
    rep(i,m){
        int a;cin>>a;
        issafe[a] = false;
    }

    vector<int> dp(n+1,0);

    dp[0] = 1;
    if(issafe[1])dp[1] = 1;//1段目は壊れている可能性がある

    for(int i = 2;i <= n;++i){
        if(issafe[i-1]) dp[i] += dp[i-1];//1段前から飛んだッ！！！
        if(issafe[i-2]) dp[i] += dp[i-2];//2段前から飛んだッ！！！
        dp[i] %= MOD;
    }

    cout << dp[n] << endl;
}


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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int n;
    int l = 0;
    int index = 1;
    int cnt = 0;
    cin >> n;
    int a[n];
    
    for(int i=0; i<n; i++) cin >> a[i];

    for(int i=0; i<n; i++){
        if(a[i]==index){
            index++;
            cnt++;
        }
    }
    if(cnt==0) cout << -1;
    else cout << n - cnt;
    cout << endl;

    return 0;
}

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

#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define forup(i,l,r) for (register int i = l ; i <= r ; i += lowbit(i))
#define fordown(i,id) for (register int i = id ; i ; i -= lowbit(i))
#define pb push_back
#define prev prev_
#define stack stack_
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) (x&(-x))

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pr;

const ld inf = 2e18;
const int N = 3e6 + 10;
const int maxn = 300020;
const ll mod = 1e9 + 7;
const ull base = 907;

struct node{
	int next,to;
};
node e[maxn * 2];
int head[maxn],cnt;	
int n,m,dfstime;

int a[maxn],b[maxn],vis[maxn],tag[maxn];
int id,fa[maxn],p[maxn];
ll sum[maxn],sumf[maxn],f[maxn],mn[maxn];

void clear(){
	rep(i,1,n) head[i] = 0;
	cnt = 0;
}
void adde(int x,int y){
	e[++cnt].to = y;
	e[cnt].next = head[x];
	head[x] = cnt;
}
void init(){
	rep(i,1,m){
		int x,y;
		scanf("%d %d",&x,&y);
		adde(x,y),adde(y,x);
	}
}
void findroot(int x){
	if ( max(0,a[id] - b[id]) < max(0,a[x] - b[x]) ) id = x;
	vis[x] = dfstime;
	fore(i,x){
		if ( vis[e[i].to] == dfstime || tag[e[i].to] ) continue;
		findroot(e[i].to);
	}	
}
ll ans = 0;
int solve(int x){
	++dfstime, id = x , findroot(x);
	int rt = id;
	tag[rt] = 1;

	sum[rt] = b[rt];
	f[rt] = max(a[rt] - b[rt],0);
	fore(i,rt){
		if ( tag[e[i].to] ) continue;
		int to = solve(e[i].to); //注意e[i].to不是下一块的根！
		sum[rt] += sum[to];
		f[rt] = min(f[rt],max(f[to],a[rt] - b[rt] - sum[to]));
	}
	if ( x == 1 ) ans = f[rt] + sum[rt];
	return rt;
}
int getfa(int x){
	return x == fa[x] ? x : fa[x] = getfa(fa[x]); 
}
bool cmp(int x,int y){
	return max(a[x] - b[x],0) < max(a[y] - b[y],0);
}
int main(){
	scanf("%d %d",&n,&m);
	rep(i,1,n) scanf("%d %d",&a[i],&b[i]), p[i] = i , fa[i] = i;
	init();
	sort(p + 1,p + n + 1,cmp);
	rep(i,1,n){
		int x = p[i];
		sum[x] = b[x];
		f[x] = max(a[x] - b[x],0);
		fore(j,x){
			int to = getfa(e[j].to);
			if ( !tag[to] ) continue;
			sum[x] += sum[to];
			f[x] = min(f[x],max(f[to],a[x] - b[x] - sum[to]));
			fa[to] = x;
		}
		tag[x] = 1;
	}
	//solve(1);
	cout<<f[p[n]] + sum[p[n]]<<endl;
//	rep(i,1,n) cout<<i<<" : "<<f[i]<<" "<<sum[i]<<endl;
}


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

public class Main {
    public static Node node[];
    public static int cnt = 1;
    public static int status[];
    public static int s[];
    public static int e[];
    
    private static class Node{
        int id;
        int next_size;
        int next[];
        
        Node(int u, int k){
            this.id = u;
            this.next_size = k;
            this.next = new int[k+1];
        }
    }
    
    private static void printNode(Node head){
        System.out.println("head.id = " + head.id);
        System.out.println("head.next_size = " + head.next_size);
        for (int i = 1; i < head.next_size + 1; i++){
            System.out.println("head.id = " + head.id + "  head.next[ " + i + " ] = " + head.next[i]);
            if (node[head.next[i]].next_size !=0){
                printNode(node[head.next[i]]);
            }
        }
    }
    
    private static void stackNode(Node head){
    
        
        if (status[head.id] == 0) {
            s[head.id] = cnt++;
            //System.out.println(head.id + " cnt = " + cnt);
            
        }
        
        if (status[head.id] != 2 ) {
            status[head.id] = 1;
        
            for (int i = 1 ; i < head.next_size + 1; i++){
                if(status[head.next[i]]==0){
                    if (head.id !=head.next[i]){
                        stackNode(node[head.next[i]]);
                    }
                }
                
            }
            
            status[head.id] = 2;
            e[head.id] = cnt++;
            //System.out.println(head.id + " cnt = " + cnt);


        }
       
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();
        node = new Node[n + 1];
        status = new int[n + 1];
        s = new int[n + 1];
        e = new int[n + 1];
        
        for (int i = 1; i < n + 1; i++){
            int u = in.nextInt();
            int k = in.nextInt();
            
            node[i] = new Node(u,k);
            for (int j = 1; j < k + 1; j++){
                
                node[i].next[j] = in.nextInt();
            }
        }
        
        /*
        for(int i = 1; i < n + 1; i++){
            Node head = node[i];
            if (status[head.id]==0){
                printNode(node[i]);
            }
        }
        */
       
        for(int i = 1; i < n + 1; i++){
            Node head = node[i];
            if (status[head.id]==0){
                 stackNode(head);      
            }
        }
      
        
     
        for (int i = 1; i < n + 1; i++){
            System.out.println(node[i].id + " " + s[i] + " " + e[i]);
        }
    }  
}

Measured memory_bytes: 28476
#include<bits/stdc++.h>
#include<boost/multiprecision/cpp_int.hpp>
#include<boost/rational.hpp>
#include<boost/multiprecision/cpp_dec_float.hpp>

int main(){
    using namespace std;
    using real = boost::rational<__int128>;
    using point = complex<real>;
    using circle = pair<point, real>;
    unsigned long N;
    cin >> N;
    vector<point> p(N);
    for(auto& i : p){
        unsigned long im, re;
        cin >> im >> re;
        i.imag(real(im));
        i.real(real(re));
    }
    {
        mt19937_64 mt{random_device{}()};
        shuffle(p.begin(), p.end(), mt);
    }
    const auto& circle_from_diameter = [](const point& a, const point& b) -> circle {
        auto center = (a + b) / real(2);
        return {center, norm(a - center)};
    };
    const auto& circle_from_triangle = [](const point& a, const point& b, const point& c) -> circle {
        if(((a - b) / (a - c)).imag() == 0)return circle{};
        auto center = ((a - b) * norm(c) + (b - c) * norm(a) + (c - a) * norm(b)) / ((a - b) * conj(c) + (b - c) * conj(a) + (c - a) * conj(b));
        return {center, norm(a - center)};
    };
    const auto& is_included = [](const circle& c, const point& a) -> bool {
        return norm(a - c.first) <= c.second;
    };
    const auto& is_all_include = [&p, &is_included](const circle& c) -> bool {
        return all_of(p.begin(), p.end(), [&c, &is_included](const point& a){return is_included(c, a);});
    };
    auto c = circle_from_diameter(p[0], p[1]);
    for(unsigned long i{2}; i < N; ++i)if(!is_included(c, p[i])){
        c = circle_from_diameter(p[0], p[i]);
        for(unsigned long j{1}; j < i; ++j)if(!is_included(c, p[j])){
            c = circle_from_diameter(p[i], p[j]);
            for(unsigned long k{0}; k < j; ++k)if(!is_included(c, p[k]))c = circle_from_triangle(p[i], p[j], p[k]);
        }
    }
    boost::multiprecision::cpp_dec_float_100 t = boost::multiprecision::sqrt(boost::rational_cast<boost::multiprecision::cpp_dec_float_100>(c.second));
    cout << t.str() << endl;
    return 0;
}

Measured memory_bytes: 384
//last updated on 28.12.2019
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
using namespace std;

#define ll              long long
#define ld              long double
#define pii             pair <int, int>
#define piii            pair <int, pii>
#define pll             pair <ll, ll>
#define plll            pair <ll, pll>
#define pss             pair <string, string>

#define fa(i, n, N)     for (ll i = n; i <= N; i++)
#define fac(i, n, b, N) for (ll i = n; i <= N && b; i++)
#define fd(i, n, N)     for (ll i = n; i >= N; i--)

#define mp              make_pair
#define pb              push_back
#define pob             pop_back
#define pf              push_front
#define pof             pop_front
#define fi              first
#define se              second

#define ms(arr,t)       memset (arr, t, sizeof(arr));
#define all(x)          x.begin(), x.end()
#define len             length()
#define endl            '\n'

#define db(x)           cerr << ">>>>>> " << #x << " -> " << x << endl

const ll inf = 1e9;
const ll inf2 = 1e18;
const ll MAX = 1e5+5;
const ll MOD = 1e9+7;
const double pi = acos(-1.0);
const double EPS = 1e-9;

void init(int precision){
  	ios_base::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	cout.setf(ios::fixed);
  	cout.setf(ios::showpoint);
  	cout.precision(precision);
}

inline void iofile (){
	freopen ("input.txt", "r", stdin);
	//freopen ("output.txt", "w", stdout);
}

char a;

int main() {
    init(10);
    //iofile();

    cin >> a;
    cout << char(a+1) << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main (){
    string S;
    cin >> S;
    int count = 0;
    int y;
    for(int i = 0; i < 3; i++){
        if (S[i] == 'o') count++;
    }
    y = 700 + count*100;
    cout << y << endl;
}

Measured memory_bytes: 3576
#include<stdio.h>
#include<algorithm>
#include<functional>
using namespace std;
int main(void)
{
	int N, K;
	int a[200010];
	int count[200010] = { 0 };
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%d", &a[i]);
		count[a[i]]++;
	}
	sort(count, count +N+1,greater<int>());
	int i = 0;
	int sum = 0;
  for(int i=0;i<K;i++){
    sum+=count[i];
  }
	printf("%d", N-sum);


	return 0;
}


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

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

    vector<int> pays;
    while (1) {
        int tmp;
        cin >> tmp;
        if (tmp == 0) {
            break;
        } else {
            pays.push_back(tmp);
        }
    }

    vector<int> coins = {500, 100, 50, 10, 5, 1};
    for (auto pay : pays) {
        int back = 1000 - pay; // お釣り
        int ans = 0;
        for (auto coin : coins) {
            int use = back / coin; // coin円 を使用する枚数
            back -= coin * use;
            ans += use;
        }
        cout << ans << endl;
    }
    return 0;
}



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

struct point{
  double x, y ,z;
  point(){}
  point (double x, double y, double z):x(x),y(y),z(z){}
  point operator - (const point &t)const{
    return point(x-t.x, y-t.y, z-t.z);
  }
  point operator * (double r )const{
    return point (x*r, y*r, z*r);
  }
  
  point operator + (const point &t)const{
    return point(x+t.x, y+t.y, z+t.z);
  }
};

inline double myabs2(const point &p){
  return (p.x*p.x + p.y*p.y + p.z*p.z);
}

struct sphere{
  point center;
  double r;
  sphere();
  sphere(double x, double y, double z, double r):center(x,y,z),r(r){}
};

point from;
point to;
point gg;

inline double f(double p){
  point v = to - from;
  point x = v * p + from;
  return myabs2(x-gg);
}

const double r5 = sqrt(5.);
const double eps = 1e-3;

double find_min(double a, double b, double f(double)){
  const double r = 2./(3.+r5);
  double c = a+r * (b-a), d = b - r*(b-a);
  double fc = f(c), fd = f(d);
  while( d-c > eps ){
    if( fc > fd){
      a = c; c = d; d =b - r * (b-a);
      fc = fd; fd = f(d);
    }else{
      b= d; d = c; c= a+r*(b-a);
      fd = fc; fc = f(c);
    }
  }
  return fc;
}

double get_dist(const point &a, const point &la, const point &lb)
{
  from = la;
  to = lb;
  gg = a;
  return find_min(0,1,f);
}

int main()
{
  while(true){
    int N,M,R;
    
    scanf("%d%d%d", &N, &M, &R);
    // cin >> N >> M >> R;
    if( N == 0 && M == 0 && R == 0 ) break;

    vector<sphere> vs;
    for(int i = 0; i < N; ++i){
      int x,y,z,r;
      // cin >> x >> y >> z >> r;
      scanf("%d%d%d%d", &x, &y, &z, &r);
      vs.push_back( sphere(x,y,z,r) );
    }
    
    vector<point> vl;
    vector<double> vb;

    for(int i = 0; i < M; ++i){
      int x,y,z,b;
      // cin >> x >> y >> z >> b;
      scanf("%d%d%d%d", &x, &y, &z, &b);
      vl.push_back( point(x,y,z) );
      vb.push_back( b );
    }

    point E;
    // cin >> E.x >> E.y >> E.z;
    
    scanf("%lf%lf%lf", &E.x, &E.y, &E.z);
    bool touched[vl.size()][vs.size()];
    for(int i = 0; i < (int)vl.size(); ++i){
      for(int j = 0; j < (int)vs.size(); ++j){
        touched[i][j] = false;
        double rr = vs[j].r * vs[j].r;
        // cout << get_dist(vs[j].center, vl[i], E) << endl;
        if( ( get_dist(vs[j].center, vl[i], E) ) < rr &&
            ( myabs2(vs[j].center-vl[i]) > rr ||
              myabs2(vs[j].center-E) > rr ) )
          {
            touched[i][j] = true;
          }
      }
    }
    
    double res = 0;
    for(int bit = 0; bit < (1<<M); ++bit){
      int S[N];
      for(int i = 0; i < N; ++i) S[i] = 0;
      
      double illum = 0;
      for(int k = 0; k < M; ++k){
        if( bit & (1<<k) ){
          illum += vb[k] / myabs2(E-vl[k]);
          for(int i = 0; i < N; ++i){
            if( touched[k][i] ){
              S[i] |= 1;
            }
          }
        }
      }

      int sz = 0;
      for(int i = 0; i < N; ++i){
        sz += S[i];
      }
      if( sz > R ) continue;
      else res = max(res, illum);
    }
    
    printf("%.8lf\n", res);    
  }
  return 0;
}

Measured memory_bytes: 1424
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    while moveA_q:
        x, y = moveA_q.pop()
        moveB_q.append([x, y])
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])
                

    # 移動bで動けるマスをmodeA_qに格納
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])


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

int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<int>> a(h + 1, vector<int>(w + 1, 0));
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
        }
    }

    int count = 0;
    vector<int> y_prev(h * w), x_prev(h * w), y_next(h * w), x_next(h * w);
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j < w; j++) {
            if (a[i][j] & 1) {
                a[i][j]--;
                y_prev[count] = i;
                x_prev[count] = j;
                a[i][j + 1]++;
                y_next[count] = i;
                x_next[count] = j + 1;
                count++;
            }
        }
        if (a[i][w] & 1 && i < h) {
            a[i][w]--;
            y_prev[count] = i;
            x_prev[count] = w;
            a[i + 1][w]++;
            y_next[count] = i + 1;
            x_next[count] = w;
            count++;
        }
    }

    cout << count << endl;
    for (int i = 0; i < count; i++) {
        cout << y_prev[i] << " " << x_prev[i] << " " << y_next[i] << " " << x_next[i] << endl;
    }
}

Measured memory_bytes: 7296
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
template <class T>
using max_priority_queue = priority_queue<T>;
template <class T>
using min_priority_queue = priority_queue<T, std::vector<T>, std::greater<T>>;

const int INF = 1 << 29;
const ll LL_INF = 1LL << 60;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int N;
string S;
const int MAX_N = 300010;
int west[MAX_N];
int east[MAX_N];
int main()
{
    cin >> N;
    cin >> S;
    for (int i = 0; i < N; i++)
    {
        if (S[i] == 'W')
        {
            west[i + 1]++;
        }
        else
        {
            east[i + 1]++;
        }
        west[i + 1] += west[i];
        east[i + 1] += east[i];
    }
    int res = INF;
    for (int i = 1; i <= N; i++)
    {
        int west1 = west[i - 1];
        int east1 = east[N] - east[i];
        res = min(res, west1 + east1);
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 3068
import sys
s = raw_input()
ts = ['']
while True:
  nts= []
  for t in ts:
    for w in ['dreamer', 'eraser', 'dream', 'erase']:
      if s == t + w:
        print 'YES'
        sys.exit()
      if s.startswith(t + w):
        nts.append(t + w)
  if len(nts) == 0:
    print 'NO'
    sys.exit()
  ts = nts


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

using namespace std ;

int main() {
	int n , x, t;
	cin >> n >> x >> t;

	if (n % x != 0) {
		cout << ((n / x) + 1)*t << endl;
	}
	else cout << (n / x)*t << endl;
	return 0;
}

Measured memory_bytes: 3532
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;

int main() {
    string s; cin >> s;

    string ans = "";
    for (char c: s) {
        if (c == '0') {
            ans += '0';
        } else if (c == '1') {
            ans += '1';
        } else if (c == 'B'){
            ans = ans.substr(0, ans.size() - 1);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
	int a, b, q;
	cin >> a >> b >> q;
	vector<long long> s(a);
	vector<long long> t(b);
	for (int i = 0; i < a; i++)
		cin >> s[i];
	for (int i = 0; i < b; i++)
		cin >> t[i];
	for (int i = 0; i < q; i++) {
		long long x;
		cin >> x;
		auto sit = lower_bound(s.begin(), s.end(), x);
		auto tit = lower_bound(t.begin(), t.end(), x);
		long long lefts = -1, rights = -1;
		long long leftt = -1, rightt = -1;
		if (sit != s.end()) {
			if (*sit == x) {
				lefts = x;
				rights = x;
			}
		}
		if (lefts == -1 && rights == -1) {
			if (sit == s.end()) {
				lefts = *(s.end()-1);
			} else if (sit == s.begin()) {
				rights = *(s.begin());
			} else {
				lefts = *(sit-1);
				rights = *(sit);
			}
		}

		if (tit != t.end()) {
			if (*tit == x) {
				leftt = x;
				rightt = x;
			}
		}
		if (leftt == -1 && rightt == -1) {
			if (tit == t.end()) {
				leftt = *(t.end()-1);
			} else if (tit == t.begin()) {
				rightt = *(t.begin());
				if (*tit == x) {
					leftt = x;
				}
			} else {
				leftt = *(tit-1);
				rightt = *(tit);
			}
		}
		long long ans = (long long)1e15;
		if (lefts == -1) {
			if (leftt == -1) {
				ans = min(ans, (max(rights, rightt)-x));
			} else if (rightt == -1) {
				ans = min(ans, ((rights-leftt)+(x-leftt)));
				ans = min(ans, ((rights-leftt)+(rights-x)));
			} else {
				ans = min(ans, ((rights-leftt)+(x-leftt)));
				ans = min(ans, ((rights-leftt)+(rights-x)));
				ans = min(ans, (max(rights, rightt)-x));
			}
		} else if (rights == -1) {
			if (rightt == -1) {
				ans = min(ans, x-min(lefts, leftt));
			} else if (leftt == -1) {
				ans = min(ans, (rightt-lefts)+(x-lefts));
				ans = min(ans, (rightt-lefts)+(rightt-x));
			} else {
				ans = min(ans, (rightt-lefts)+(x-lefts));
				ans = min(ans, (rightt-lefts)+(rightt-x));
				ans = min(ans, x-min(lefts, leftt));
			}
		} else {
			if (leftt == -1) {
				ans = min(ans, max(rights, rightt)-x);
				ans = min(ans, rightt-lefts + (x-lefts));
				ans = min(ans, rightt-lefts + (rightt-x));
			} else if (rightt == -1) {
				ans = min(ans, x-min(lefts, leftt));
				ans = min(ans, rights-leftt + (x-leftt));
				ans = min(ans, rights-leftt + (rights-x));
			} else {
				ans = min(ans, max(rights, rightt)-x);
				ans = min(ans, x-min(lefts, leftt));
				ans = min(ans, rights-leftt + (x-leftt));
				ans = min(ans, rights-leftt + (rights-x));
				ans = min(ans, rightt-lefts + (x-lefts));
				ans = min(ans, rightt-lefts + (rightt-x));
			}
		}
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 4768
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
ostream &operator<<(ostream &os, const vector<int> &a) {
	os<<"[";
	rep(i,a.size()){
		os<<a[i];
		if(i<a.size()-1) os<<",";
	}
	os<<"]";
	return os; 
}
int dp[114][114];
int gr[114][114];
int ma[114];
int n;
void cal(int v,int r,int d){
	int ret=0;
	rep(i,n){
		if(i==r || gr[v][i]!=1) continue;
		ret++;cal(i,v,d+1);
	}
	//cout<<v<<' '<<r<<' '<<d<<' '<<ret<<endl;
	ma[d]=max(ma[d],ret);
}
int main()
{
	int inf=114,a,b;
	rep(i,114) rep(j,114) gr[i][j]=inf;
	rep(i,114) gr[i][i]=0;
	cin>>n;
	rep(i,n-1){
		cin>>a>>b;a--;b--;
		gr[a][b]=gr[b][a]=1;
	}
	rep(k,n) rep(i,n) rep(j,n) gr[i][j]=min(gr[i][j],gr[i][k]+gr[k][j]);
	int x=0,y=0;
	rep(i,n){
		if(gr[x][y]<gr[x][i]) y=i;
	}
	rep(i,n){
		if(gr[x][y]<gr[y][i]) x=i;
	}
	vector<int> v;int de=gr[x][y];v.pb(x);
	//cout<<x<<' '<<y<<' '<<de<<endl;
	rep(i,de){
		rep(j,n){
			if(gr[x][j]==1 && gr[j][y]==de-1-i){
				x=j;break;
			}
		}
		v.pb(x);
	}
	//cout<<v<<endl;
	int out1=de/2+1;
	memset(ma,false,sizeof(ma));
	if(de%2==0){
		lint out2=(1LL<<62)-1;int c=v[de/2];
		cal(c,c,0);
		lint now=1;
		rep(i,out1-1) now*=ma[i];out2=min(out2,now);
		rep(j,n){
			if(gr[c][j]!=1) continue;
			memset(ma,0,sizeof(ma));
			cal(c,j,0);cal(j,c,0);
			now=2;
			rep(i,out1-1) now*=ma[i];out2=min(out2,now);
		}
		cout<<out1<<' '<<out2<<endl;
	}
	else{
		cal(v[de/2],v[(de+1)/2],0),cal(v[(de+1)/2],v[de/2],0);
		lint out2=2;
		rep(i,out1-1) out2*=ma[i];
		cout<<out1<<' '<<out2<<endl;
	}
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
// const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1},
//           dx[] = {0, -1, -1, -1, 0, 1, 1, 1};

struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cerr << fixed << setprecision(10);
  }
} iosetup;
/*-------------------------------------------------*/
int main() {
  int n; cin >> n;
  cout << n * (n + 1) / 2 << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define rep(i,n) for(ll i=0;i<(n);i++)
using namespace std;

int main(){
    int a[4];
    cin>>a[0]>>a[1]>>a[2]>>a[3];
    sort(a,a+4);
    if(a[0]==1 and a[1]==4 and a[2]==7 and a[3]==9) cout<<"YES"<<endl;
    else cout<<"NO" <<endl;
      return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;

int main(){
	int n; cin >> n;
	vector<ll> h(n);
	for(int i=0;i<n;i++){
		cin >> h[i];
	}
	int ma=0;
	int cnt=0;
	for(int i=0;i<n-1;i++){
		if(h[i]>=h[i+1])cnt++;
		else{
			ma=max(ma,cnt);
			cnt=0;
		}
	}
	ma=max(ma,cnt);
	cout << ma << endl;
}

Measured memory_bytes: 1024
import math
x,y = list(map(int, input().split()))
mod = 7 + (10**9)
ans = 0
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
    exit()
else:
    m = (2*x - y)//3
    n = (2*y - x)//3
    if n < 0 or m < 0:
        print(0)
        exit()
    #m+n C m を計算
    #(m+n)! / n! * m!を計算したいが、mod上で割り算できない。
    #逆元を使う
    factorial = [1]*(m+n+1)
    for i in range(1,m+n+1):
        factorial[i] = (factorial[i - 1] * i) % mod
    ans = factorial[m+n] * mod_inv(factorial[m], mod)
    ans %= mod
    ans *= mod_inv(factorial[n], mod)
    ans %= mod
    print(ans)


Measured memory_bytes: 43760
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#include <unordered_map>

using namespace std;

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

    vector<long> a(n,0);

    for(long i = 0; i < n ;i++){
        cin >> a[i];
        a[i]--;
    }

    set<long> used;
    vector<long> road;
    road.reserve(n);
    long next = 0;
    long count = -1;

    while(true){
        if (used.count(next)==0){
            road.push_back(next);
            used.insert(next);
            next = a[next];
            count++;
            if(k-count == 0){
                break;
            }
            
            
        }else{
            auto result = find(road.begin(), road.end(), next);
            if(*result != 0){
                k = k-distance(road.begin(),result);
                road.erase(road.begin(),result);
            }
            break;
        }
    }

    cout << road[k%road.size()]+1 << endl;

    return 0;
}

Measured memory_bytes: 13436
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

#define Pr(f,...) //fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)

typedef long long ll;

template<typename T>
void read(T &x){
	x=0; 
	char c;
	for(c=getchar();!isdigit(c);c=getchar()); 
	for(;isdigit(c);c=getchar())x=x*10+c-'0'; 
}

const int N=1e5+50,P=1e9+7;

int mul(int a,int b){ return 1ll*a*b%P; }
int add(int a,int b){ a+=b; return a>=P?a-P:a; }
int sub(int a,int b){ a-=b; return a<0?a+P:a; }

ll n,a[N],b[N]; 

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	//freopen("dat.in","r",stdin);
	//freopen("my.out","w",stdout);
#endif
	read(n); 
	rep(i,1,n){
		read(a[i]); 
		read(b[i]); 
	}
	ll sum=0; 
	dec(i,n,1){
		a[i]+=sum;
		sum+=(b[i]-a[i]%b[i]+b[i])%b[i];
	}
	printf("%lld\n",sum); 
	return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>

int main()
{
	int n, i, a, b;
	

	while (1) {
                int at = 0, bt = 0;

		scanf("%d", &n);
		if (n == 0) {
			break;
		}

		for (i = 0; i < n; i++) {
			scanf("%d", &a);
			scanf("%d", &b);

			if (a > b) {
				at += a + b;
			}
			else if (a < b) {
				bt += a + b;
			}
			else {
				at += a;
				bt += b;
			}
		}

		printf("%d %d\n", at, bt);
	}

    return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <climits>
#include <memory>
#include <sstream>
#include <iomanip>
#include <cstdio>

using namespace std;

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	string s;
	cin >> n;
	cin >> s;

	vector<int> w_num(n + 1);
	vector<int> b_num(n + 1);
	w_num[0] = 0;
	b_num[0] = 0;
	for (int i = 1; i < n + 1; i++) {
		w_num[i] = w_num[i - 1];
		b_num[i] = b_num[i - 1];
		if (s[i - 1] == '.') {
			w_num[i]++;
		}
		else {
			b_num[i]++;
		}
	}

	int ans = INT_MAX;
	for (int i = 0; i < n + 1; i++) {
		ans = min(ans, b_num[i] + (w_num[n] - w_num[i]));
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2196
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		solver();
	}

	static void solver() {
		Scanner sc = new Scanner(System.in);
		long s = sc.nextLong();
		long l = 0;
		long r = 200000000000000000L;;
		while (r - l > 1) {
			long mid = (l + r) / 2;
			if (calc(mid) >= s)
				r = mid;
			else
				l = mid;
		}

		StringBuilder sb = new StringBuilder("");
		for (int i = 0; i < 25; i++) {
			long ns = l + i + 1;
			if (ns % 15 == 0) {
				sb.append("FizzBuzz");
			} else if (ns % 3 == 0) {
				sb.append("Fizz");
			} else if (ns % 5 == 0) {
				sb.append("Buzz");
			} else {
				sb.append(ns);
			}
		}
		System.out.println(sb.toString().substring((int) (s - calc(l) - 1), 20 + (int) (s - calc(l) - 1)));
	}

	static long calc(long a) {
		long ret = a / 3 * 4 + a / 5 * 4;
		long l = 0;
		for (long p = 1; a >= p; p *= 10) {
			l++;
			long R = Math.min(a, p * 10 - 1);
			long L = p - 1;
			ret += ((R - R / 3 - R / 5 + R / 15) - (L - L / 3 - L / 5 + L / 15)) * l;
		}
		return ret;
	}
}

Measured memory_bytes: 26280
n=int(input())
mod=10**9+7
a=[int(x) for x in input().split()]
a.sort(reverse=True)
ruiseki=[a[0]]
for i in range(1,n):
  ruiseki.append(a[i]+ruiseki[i-1])

ans=0
ruiseki.sort(reverse=True)

a.sort()
for i in range(1,n):
  ans+=((a[i-1])*ruiseki[i])%mod

print(ans%mod)


Measured memory_bytes: 31760
#include <iostream>
using namespace std;
//#define MAX 1000

int main(){
    int n,l,r,ans=0;
    
    cin>>n;
    
    for(int i=0;i<n;i++){
        cin>>l>>r;
        ans+=r-l+1;
    }
    
    cout<<ans<<endl;
}


Measured memory_bytes: 3628
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
//typedef tuple<pii,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int n;
	cin>>n;
	int co=0;
	int a=n;
	while(a){
		co+=a%10;
		a/=10;
	}
	if(n%co)cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
}





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

using namespace std;

typedef unsigned long long ull;

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

    int n, r;
    cin >> n >> r;
    if (n >= 10)
        cout << r;
    else
        cout << (10 - n) * 100 + r;

    return 0;
}

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

int n, m;
typedef pair<int, int>pint;
vector<pint>p;

bool cmp(pint x, pint y) { return x.second<y.second; }

int main() {
	cin >> n >> m;
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		p.push_back(pint(a, b));
	}
	sort(p.begin(), p.end(), cmp);
	int ans = 0;
	int endtime = 0;
	for (int i = 0; i < m; i++) {
		if (p[i].first >= endtime) {
			endtime = p[i].second;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1400
#include <stdio.h>

int bubbleSort(int A[], int N){
  int i, j, tmp;
  int c = 0;
  for(i=0; i<(N - 1); i++){
    for(j=(N - 1); j>i; j--){
      if(A[j-1] > A[j]){
        tmp = A[j-1];
        A[j-1] = A[j];
        A[j] = tmp;
        c++;
      }
    }
  }
  return c;
}

void printSort(int A[], int N, int c){
  int a;
  for(a=0; a<N; a++){
    printf("%d", A[a]);
    if(a == N-1) break;
    printf(" ");
  }
  printf("\n%d\n", c);
}

int main(){
  int N, count = 0;
  scanf("%d", &N);
  int A[N];
  int x,i;
  for(i=0; i<N; i++){
    scanf("%d", &A[i]);
  }
  count = bubbleSort(A, N);
  printSort(A, N, count);
}

Measured memory_bytes: 1772
import java.util.Scanner;

/**
 * https://abc044.contest.atcoder.jp/tasks/arc060_a
 */
public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int[] x = new int[N];
		int sum = 0;
		for(int i=0; i<N; i++){
			x[i] = sc.nextInt();
			sum += x[i];
		}
		sc.close();
		
		long[][][] dp = new long[N][N+1][sum+1];
		dp[0][1][x[0]]=1;
		for(int i=1; i<N; i++){
			for(int k=1; k<=(i+1); k++){
				for(int s=0; s<=sum; s++){
					if(s<x[i]){
						dp[i][k][s] = dp[i-1][k][s];
					}else if(s>=x[i]){
						if(k==1 && x[i]==s){
							dp[i][k][s] = dp[i-1][k][s]+1;
						}else{
							dp[i][k][s] = dp[i-1][k][s]+dp[i-1][k-1][s-x[i]];
						}
					}
				}
			}
		}
		
		long ans = 0;
		for(int k=1; k<=N; k++){
			if(k*A<=sum) ans += dp[N-1][k][k*A];
		}
		
		System.out.println(ans);
		
	}
	

}


Measured memory_bytes: 85704
#include<iostream>
using namespace std;
int main()
{
  int n;
  cin>>n;
  long long int count=0,temp=0,a;
  for(int i=0;i<n;i++)
  {
    cin>>a;
    if(temp>a)
    {
      count+=(temp-a);
      continue;
    } 
    temp=a;  
  }
  cout<<count<<endl;
  return 0;
} 
    

Measured memory_bytes: 3568
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <bitset>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
 
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INPUT1(n, a) for(int i##n = 0; i##n < n; i##n++) {cin >> a[i##n]; } //n = count, a = vector 
#define OUTPUT1(n, a) cout << "---count---" << endl << n << endl << "---content---" << endl; for(const auto b : a){cout << b << endl; }
#define INPUT2(x, y, field) for(int i##x = 0; i##x < y; i##x++) { for(int j##x = 0; j##x < x; j##x++) { cin >> field[i##x][j##x]; } }
#define OUTPUT2(x, y, field) cout << "---count---" << endl << x << " " << y << endl <<"---content---" << endl; for(int i##x = 0; i##x < y; i##x++) { cout << i##x << "   "; for(int j##x = 0; j##x < x; j##x++) { cout << field[i##x][j##x] << " "; } cout << endl; }
 
using namespace std;
int main(void){
    // Your code here!
    int n(0), r(0);
    cin>>n>>r;
    if(n<10)cout<<r + 100*(10-n)<<endl;
    else cout<<r<<endl;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int A[3][3];

signed main(){
    cin>>A[0][0];
    cin>>A[0][1];
    cin>>A[1][1];
    int k=A[1][1]*3;
    A[0][2]=k-A[0][0]-A[0][1];
    A[2][0]=k-A[0][2]-A[1][1];
    A[1][0]=k-A[0][0]-A[2][0];
    A[1][2]=k-A[1][0]-A[1][1];
    A[2][1]=k-A[0][1]-A[1][1];
    A[2][2]=k-A[0][0]-A[1][1];

    rep(i,3){
        rep(j,3){
            if(j)cout<<" ";
            cout<<A[i][j];
        }cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 256