akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef _MY_DEBUG
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sat Apr  4 21:00:24 JST 2020
 **/

template <class T, class S> T make_vec(S x) { return x; }
template <class T, class... Ts> auto make_vec(size_t n, Ts... ts) {
    return std::vector<decltype(make_vec<T>(ts...))>(n, make_vec<T>(ts...));
}

const Int N = 10;
signed main() {
    Int K;
    std::cin >> K;
    auto dp = make_vec<Int>(N, 10, 0);
    REP(j, 10) dp[0][j] = 1;
    Int len = -1;
    std::string ans;
    [&] {
        REP(i, N) {
            REP(j, 10) {
                if (i) {
                    REP(j2, 10) {
                        if (abs(j - j2) >= 2) continue;
                        dp[i][j] += dp[i - 1][j2];
                    }
                }
                if (j) K -= dp[i][j];
                if (K <= 0) {
                    len = i;
                    ans.push_back('0' + j);
                    K += dp[i][j];
                    return;
                }
            }
        }
    }();
    for (Int i = len - 1; i >= 0; i--) {
        REP(j, 10) {
            if (std::abs((Int)(ans.back() - '0') - j) >= 2) continue;
            K -= dp[i][j];
            if (K <= 0) {
                ans.push_back('0' + j);
                K += dp[i][j];
                break;
            }
        }
    }
    std::cout << ans << std::endl;
}


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

int main() {
	int n, d[50];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> d[i];
	}
	sort(d, d + n);
	int u = 0, v = 0, r = 12;
	for (int i = 0; i < n - 1; i++) {
		if (u <= v) {
			r = min(r, d[i] - u);
			u = d[i];
		} else {
			r = min(r, d[i] - v);
			v = d[i];
		}
	}
	r = min(r, max(min(d[n - 1] - u, 24 - v - d[n - 1]), min(d[n - 1] - v, 24 - u - d[n - 1])));
	cout << r << endl;
	return 0;
}


Measured memory_bytes: 256
use std::fs;
use std::io::{stdin, Read};
struct UnionFind {
    parents: Vec<usize>,
}
impl UnionFind {
    pub fn new(n: usize) -> Self {
        let par = (0..n).collect();
        UnionFind { parents: par }
    }
    pub fn root(&mut self, x: usize) -> usize {
        if self.parents[x] == x {
            return x;
        }
        let par = self.parents[x];
        self.parents[x] = self.root(par);
        self.parents[x]
    }
    pub fn union(&mut self, x: usize, y: usize) {
        let rx = self.root(x);
        let ry = self.root(y);
        if rx == ry {
            return;
        }
        self.parents[rx] = ry;
    }
    pub fn is_same(&mut self, x: usize, y: usize) -> bool {
        let rx = self.root(x);
        let ry = self.root(y);
        rx == ry
    }
}

macro_rules! parse {
    ($it: ident) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: ident,2) => {
        (parse!($it), parse!($it))
    };
    ($it: ident,3) => {
        (parse!($it), parse!($it), parse!($it))
    };
    ($it: ident,4) => {
        (parse!($it), parse!($it), parse!($it), parse!($it))
    };
    ($it: ident, $n: expr) => {
        (&mut $it).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    let (n, m): (usize, usize) = parse!(it, 2);
    let mut edges = (0..m)
        .map(|_| {
            let (i, j): (usize, usize) = parse!(it, 2);
            (i - 1, j - 1)
        })
        .collect::<Vec<(usize, usize)>>();
    edges.reverse();
    let mut uf = UnionFind::new(n);
    let mut ret = vec![];
    let mut nc = vec![1; n];
    let mut cur = n * (n - 1) / 2;
    for (i, j) in edges {
        ret.push(cur);
        let ri = uf.root(i);
        let rj = uf.root(j);
        if ri != rj {
            cur -= nc[ri] * nc[rj];
            uf.union(i, j);
            let rn = uf.root(i);
            let rf = if rn == ri { rj } else { ri };
            nc[rn] += nc[rf];
            nc[rf] = 0;
        }
    }
    ret.reverse();
    for r in ret {
        println!("{}", r);
    }
}

fn test() {
    let mut f = fs::File::open("foo.txt").unwrap();
    let mut s = String::new();
    f.read_to_string(&mut s).unwrap();
    solve(&s);
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_main() {
        test();
    }
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 13052
l = input()

mod = 10 ** 9 + 7
ans = 1
one = 1
zero = 0
for i in l:
    if i == "1":
        zero = 1 * one + 3 * zero
        one *= 2
        ans = one + zero
    else:
        one = one
        zero = 3 * zero
        ans = one + zero
    one %= mod
    zero %= mod
    ans %= mod
print(ans % mod)


Measured memory_bytes: 3188
from sys import stdin
H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append([x for x in input()])
AT = list(zip(*A))
tate = []
yoko = []

for i in range(H):
    if '#' in A[i]:
        tate.append(i)
for i in range(W):
    if '#' in AT[i]:
        yoko.append(i)

for i in tate:
    for j in yoko:
        print(A[i][j], end='')
    print('')


Measured memory_bytes: 4596
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
using namespace std;
int main() {
  int a;
  string s;
  cin >> a >> s;
  if (a >= 3200) {
	  cout << s << endl;
	}
  else {
	  cout << "red" << endl;
	}
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int INF = 987654321;
const ll MOD = 1000000007;

int main(void) {
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL); 
  cout.tie(NULL);
  //freopen("in.txt", "r", stdin);
  int n; cin >> n;
  vi a;
  a.resize(n);
  rep(i,0,n) {
    cin >> a[i];
  }
  map<int, int> cnt;
  rep(i,0,n) {
    if(cnt.find(a[i]) != cnt.end()) {
      cnt[a[i]]++;
    } else {
      cnt[a[i]] = 1;
    }
  }
  if(n%3) {
    if(cnt.size() > 1) {
      cout << "No" << endl;
    } else if (cnt.find(0) != cnt.end()) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  } else {
    if(cnt.find(0) != cnt.end()) {
      if(cnt.size() == 2 && cnt[0] == n/3) {
        cout << "Yes" << endl;
        return 0;
      } else if(cnt.size() == 1) {
        cout << "Yes" << endl;
        return 0;
      }
    }
    for(auto it = cnt.begin(); it != cnt.end(); ++it) {
      if(it->S != (n/3)) {
        cout << "No" << endl;
        return 0;
      }
    }
    auto it = cnt.begin();
    int a = it->F;
    int b = (++it)->F;
    int c = (++it)->F;
    if((a ^ b) != c || (a ^ c) != b || (b ^ c) != a) {
      cout << "No" << endl;
    } else {
      cout << "Yes" << endl;
    }
  }
  return 0;
}


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

int main() {
	int n, i, a[10010], ans;
	cin >> n;
	ans = 0;
	for (i = 0;i < n;i++) {
          	cin >> a[i];
	    while (a[i] % 2 == 0) {
	        ans++;
	        a[i] = a[i] / 2;
	    }
	}
	cout << ans;
	return 0;
}


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

using namespace std;

#define INF 2000000000

int main() {
    long long x;
    cin >> x;

    long long ans;
    ans = (x / 11) * 2;

    if (x % 11 == 0) {

    }
    else if (x % 11 <= 6) {
        ans += 1;
    }
    else {
        ans += 2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
n=int(input())
s=[int(i) for i in input().split()]
s[0]-=1
b=True
for i in range(1,n):
    if s[i]>s[i-1]:
        s[i]-=1
    elif s[i]<s[i-1]:
        b=False
        break
if b:
    print("Yes")
else:
    print("No")

    


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

int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a==b&&b==c)printf("No");
    else if(a!=b&&b!=c&&a!=c)printf("No");
    else printf("Yes");
    return 0;
}

Measured memory_bytes: 256
from sys import stdin
import fractions

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
# インデックスを直感で使えるように先頭にダミーを入れる
A = [0] + A

"""
L(i) := A_1, A_2, ..., A_i-1 の最大公約数
R(i) := A_i, A_i+1, ..., A_N の最大公約数
Aiを書き換えることにした場合の最大公約数をM_iとすると
M_i = gcd(L(i), R(i+1))

ただし L(0)=0, R(N+1)=0
"""

L = [0 for _ in range(N+1)]
R = [0 for _ in range(N+2)]

for i in range(N):
    L[i+1] = fractions.gcd(L[i], A[i])


for i in range(N, 0, -1):
    R[i] = fractions.gcd(R[i+1], A[i])

M = []

for i in range(1, N+1):
    M_i = fractions.gcd(L[i], R[i+1])
    M.append(M_i) 

print(max(M))


Measured memory_bytes: 89580
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
def run():
    N, K = map(int, sysread().split())

    ans = 0
    if not K % 2:
        val = (N - K //2) // K + 1
        val = val ** 3
        ans += val

    val = N // K
    val = val ** 3
    ans += val
    print(ans)
if __name__ == "__main__":
    run()


Measured memory_bytes: 9236
#include<stdio.h>
int main(){
  int s[10000],t[500],n,q,i,j,count=0,k;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&s[i]);
  }
   scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&t[i]);
  }
  for(i=0;i<q;i++){
    k=t[i];
      for(j=0;j<n;j++){
	if(k==s[j]){
	  count++;
	  break;
	}
      }
  }
  printf("%d\n",count);
  return 0;
}
		    
	  



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

const int MAXN = 1e5 + 5;
const int MOD = 998244353;

int N;
int a[MAXN];

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) 
		scanf("%d", a + i);
	
	sort(a, a + N);
	
	int ans = 1;
	for (int i = 0; i < N; i++)
		ans = (long long)ans * __gcd(a[i], i) % MOD;
	
	printf("%d\n", ans);
	
	return 0;
}

Measured memory_bytes: 640
#include <iostream>

int main(void){
  int n, k, dsp = 1, i;
  std::cin >> n >> k;
  for(i = 0; i < n; i++){
    if(dsp < k) dsp *= 2;
    else dsp += k;
  }
  std::cout << dsp << std::endl;
  return 0;
}

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

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)

int main(void)
{
  double in[6];
  while (cin >> in[0]) {
    FOR(i,1,6) cin >> in[i];
    double x,y;
    y=(in[5]-in[2]*in[3]/in[0])/(in[4]-in[1]*in[3]/in[0]);
    x=(in[2]-in[1]*y)/in[0];
    x*=1000;
    x=round(x);
    x/=1000;
    y*=1000;
    y=round(y);
    y/=1000;
    cout << fixed << setprecision(3) << x << ' ' << y << endl;
  }

  return 0;
}

Measured memory_bytes: 1292
#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
vector<int> e[505];
int p[505]={};
void bin(int u, int col){
  if(p[u] && col != p[u]){
    cout << -1 << endl;
    exit(0);
  }
  if(p[u])return;
  p[u] = col;
  for(auto s: e[u]){
    bin(s, (col%2) + 1);
  }
}
void solve(long long n, std::vector<string> s) {
  rep(i,n)rep(j,n)if(s[i][j]=='1')e[i].push_back(j);
  bin(0,1);

  lli ans = 0;
  rep(start,n){
    queue<pair<lli,lli>> que;
    que.push(make_pair(start,1));
    lli m = 0;
    rep(i,n)p[i] = 0;
    while(!que.empty()){

      auto ps = que.front();
      auto ss = ps.first;
      que.pop();
      if(p[ss])
        continue;
      p[ss] = ps.second;
      for(auto to:e[ss])
        if(p[to]==0)
          que.push(make_pair(to,ps.second+1));
      m = max(m, ps.second);
    }
    //cout << start << " " << m << endl;
    ans = max(ans,m);
  }
  cout << ans << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<string> S(N);
  for (int i = 0; i < N; i++) {
    cin >> S[i];
  }
  solve(N, std::move(S));
  return 0;
}


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

int main(){
    int k,s,ans = 0;
    cin >> k >> s;
    for(int x = 0; x <= k; x++){
        for(int y = 0; y <= k; y++){
            if(s-x-y >= 0 && s-x-y <= k) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
/*
g++ -std=c++11 -o2 -Wall ABC097D.cpp -o ./out/ABC097D.out
./out/ABC097D.out
*/

#include <bits/stdc++.h>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define tr(c, i) for (iter(c) != (c).begin(); i != (c).end(); ++i)
#define pb push_back
#define mp make_pair

typedef long long ll;

class Union_Find{
private:
    vector<int> par, rank;

    int find(int x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    }
public:
    Union_Find(int Max_Node){
        par.resize(Max_Node);
        rank.resize(Max_Node);
    }

    void init(int n) {
        for(int i = 0; i < n; i++){
            par[i] = i;
            rank[i] = 0;
        }
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y)return ;

        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y])rank[x]++;
        }
    }

    bool same(int x, int y){
        return (find(x) == find(y));
    }
};

int main(){
//    freopen("./input/input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> in(n);
    for(int i = 0; i < n; i++)cin >> in[i];
    Union_Find uf(n + 10);
    uf.init(n + 1);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        uf.unite(a, b);
//        uf.unite(b, a);
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){
        if(uf.same(in[i], i+1)){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <stdio.h>
#include <string>
#include <complex>
using namespace std;
int main(void) {
  long long int n;
  int x=0, y=0, t=0, x2, y2, t2;
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> t2 >> x2 >> y2;
    if((t2 - t) < abs(x2 - x) + abs(y2 - y) || (t2 - t) % 2 != (abs(x2 - x) + abs(y2 - y))%2) {
      cout << "No" << endl;
      return 0;
    }
    t = t2;
    x = x2;
    y = y2;
  }
  cout << "Yes" << endl;
  return 0;
}

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

#define VIC ios::sync_with_stdio(0);cin.tie(0);ios_base::sync_with_stdio(0);
#define wtf(s) freopen((s), "w", stdout)
#define rff(s) freopen((s), "r", stdin)
#define pi (2 * acos(0))
typedef long double ld;
typedef long long ll;
typedef complex<ld> point;
#define endl '\n'
#define matrix vector<vector<ll>>
#define EPS 1e-9
#define X real()
#define Y imag()
#define vec(a, b) ((b) - (a))
#define dot(a, b) ((conj(a) * (b)).real())
#define cross(a, b) ((conj(a) *(b)).imag())
#define lengthsqr(v) (dot(v, v))
#define length(v) ((ld)hypot((v).Y, (v).X))
#define same(a, b) (lengthsqr(vec(a, b)) < EPS)

//Base case: reach rock number n
//states: rock index
//transitions: min(F(idx + i) for i from 1 to k + diff[i])
const int N = 2e5 + 5, inf = 2e9, mod = 1e9 + 7;
int n, k, a[N], dp[N];

int solve(int idx)
{
    if (idx == n - 1)
        return dp[idx] = 0;
    //if result of index is calc
    //return result
    if (dp[idx] != -1)
        return dp[idx];
    int ans = inf;
    for (int i = 1; i <= k && i + idx < n; i++)
        ans = min(ans, solve(idx + i) + abs(a[idx] - a[idx + i]));
    return dp[idx] = ans;
}

int main()
{
    VIC
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    memset(dp, -1, sizeof dp);
    cout << solve(0);
    cerr << ' ' << dp[0] << ' ' << dp[n - 1] << endl;
    return 0;
}


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

int main(int argc, const char * argv[]) {
    int N,res=0;
//    cout << "Hello" << endl;
    cin >> N;
    for (int i=0; i<4; i++) {
        if(N%10==2){
            res++;
        }
        N = N / 10;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
import math
import queue
from collections import defaultdict

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1

n,k = readInts()
p = readInts()
#print(p)
maxValue = sum(p[0:k])
be = maxValue
memo = p[0:k]
ans = 0
for i in range(1,n-k+1):
	be+=-p[i-1]+p[i+k-1]
	if maxValue<be:
		maxValue = sum(p[i:i+k])
		memo = p[i:i+k]

for i in range(k):
	ans+=(memo[i]+1)/2

print(ans)

Measured memory_bytes: 26624
"use strict"
const create = () => {
    const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
    const res = {
        "list": input, "index": 0, "max": input.length,
        "hasNext": function() {return this.index < this.max},
        "next": function() { if (!this.hasNext()) {throw "ArrayIndexOutOfBoundsException";}else{return this.list[this.index++];}}
    };
    return res;
}
const o = create();
const next = () => o.next()
const nextInt = () => parseInt(o.next())
const nextStrArray = () => o.next().split(" ")
const nextIntArray = () => o.next().split(" ").map(el => parseInt(el))
const nextCharArray = () => o.next().split("")
const hasNext = () => o.hasNext()
const myout = (...x) => console.log(...x)

const pow = (x,y) => {
    let r = 1
    for(let i = 0; i<y; i++){
        r = r * x % 1000000007
    }
    return r
}

const Main = () => {
    let n = nextInt()
    let ans = pow(10, n) - (pow(9, n) * 2) + pow(8,n)
    ans = ans % 1000000007
    ans = (ans + 1000000007) % 1000000007
    console.log(ans)
}
Main()



Measured memory_bytes: 33212
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		
		String S = scan.next();
		
		if(S.length()==3){
			char[] Si = new char[S.length()];

    		for(int i = 0; i < S.length(); i++){
            	 Si[i] = S.charAt(i);
            }

				if(Si[1]=='A' && Si[2]=='A' && Si[0]=='A'){
					System.out.println("No");
				}
				else if(Si[1]=='B' && Si[2]=='B' && Si[0]=='B'){
					System.out.println("No");
				}
				else{
					System.out.println("Yes");
				}
		}
	}
}


Measured memory_bytes: 22996
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final String LINE_SPR = System.getProperty("line.separator");
    final int BIG_MOD = 1000000007;

    void run() throws Exception {
        int n = ni();
        int dept = 100000;
        for(int i = 0; i < n; i++) {
            dept += dept * 5 / 100;
            dept = (int)Math.ceil(dept / 1000.0f) * 1000;
        }
        System.out.println(dept);
    }


    /*
     * Templates
     */
    void dumpObjArr(Object[] arr, int n) {
        for(int i = 0; i < n; i++) {
            System.out.print(arr[i]);
            if(i < n - 1)
                System.out.print(" ");
        }
        System.out.println("");
    }

    void dumpObjArr2(Object[][] arr, int m, int n) {
        for(int j = 0; j < m; j++) 
            dumpObjArr(arr[j], n);
    }

    int ni() throws Exception {
        return Integer.parseInt(br.readLine().trim());
    }

    long nl() throws Exception {
        return Long.parseLong(br.readLine().trim());
    }

    String ns() throws Exception {
        return br.readLine();
    }

    boolean isPrime(int n) {
        for(int i=2;i<n;i++) {
            if(n%i==0)
                return false;
        }
        return true;
    }

    int getPrime(int n) {
        List<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        int count = 1;

        int x = 1;
        while(primes.size() < n) {
            x+=2;
            int m = (int)Math.sqrt(x);
            for(int p : primes) {
                if(p > m) {
                    primes.add(x);
                    break;
                }

                if(x % p == 0) 
                    break;
            }
        }

        return primes.get(primes.size() - 1);
    }

    long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    long gcd(long a, long b) {
        if(a < b) {
            long tmp = a;
            a = b;
            b = tmp;
        }
        // a >= b
        long mod = a % b;
        if(mod == 0) 
            return b;
        else 
            return gcd(b, mod);
    }

    void gcjPrint(String str, int t) {
        System.out.println("Case #" + t + ": " + str);
    }

    public static void main(String[] args) throws Exception {
        new Main().run();
    }
}

Measured memory_bytes: 16872
#include <cstdio>
#include <algorithm>
using namespace std;

int len,k;
char c[105];

int main(void){
	scanf("%d",&len);
	scanf("%s",c);
	scanf("%d",&k);
	k--;
	for(int i=0;i<len;i++)
	if(c[k]!=c[i])printf("*");
	else printf("%c",c[i]);
	printf("\n");
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
typedef long long ll;
ll dp[maxn][2];
vector<int> G[maxn];
void test(int x,int y)
{
	dp[x][0] = dp[x][1] = 1;
	for(auto u : G[x])
	{
		if(y != u)
		{
			test(u,x);
			dp[x][0] = dp[x][0] * (dp[u][0] + dp[u][1]) % mod;
			dp[x][1] = dp[x][1] * dp[u][0] % mod;
		}
	}
}
int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	for(int i = 1;i < n; ++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	test(1,0);
	for(int i = 0;i < 100000000; ++i);
	printf("%lld\n",(dp[1][0] + dp[1][1]) % mod);
	return 0;
}

Measured memory_bytes: 14208
//#include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <time.h>
#include <stdio.h>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mapa make_pair
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<typename T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template<typename T>
inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<typename T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }
template<typename T>
void vdeb(std::vector<T> &da) {
	for (int i = 0;i < da.size();i++) {
		if (i == da.size() - 1) std::cout << da[i];
		else std::cout << da[i] << ' ';
	}
	std::cout << std::endl;
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
	for (int i = 0;i < da.size();i++) vdeb(da[i]);
	std::cout << std::endl;
}
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<string> da(n);
	rip(i,n,0) cin >> da[i];
	map<string, int> mp;
	rip(i,n,0){
		if(mp.count(da[i])){
			mp[da[i]]++;
		}
		else{
			mp[da[i]] = 1;
		}
	}
	vector<string> ans(0);
	int ma = 0;
	for(auto i:mp){
		chmax(ma, i.second);
	}
	for(auto i:mp){
		if(ma == i.second){
			ans.push_back(i.first);
		}
	}
	rip(i, ans.size(),0){
		cout << ans[i] << endl;
	}
}

Measured memory_bytes: 28532
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int l, r;
    cin >> l >> r;
    int diff = r - l;
    if(diff > 2019){
        cout << 0 << endl;
        return 0;
    }
    int ans = INF;
    rep(i, l, r + 1){
        rep(j, i + 1, r + 1){
            ans = min(ans, i * j % 2019);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
public class Main {

  private static void solve() {
    int k = ni();
    int x = ni();
    for (int i = x - k + 1; i <= x + k - 1; i++) {
      out.print(i + " ");
    }
    out.println();

  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}



Measured memory_bytes: 21972
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;

int main() {
  string s;
  cin >> s;
  long long n = s.length();
  long long ans = (n * (n - 1)) / 2;
  ans++;

  vector<long long> a(26);
  for (int i = 0; i < 26; i++) {
    a[i] = 0;
  }

  for (int i = 0; i < n; i++) {
    a[s[i] - 'a']++;
  }

  for (int i = 0; i < 26; i++) {
    cerr << a[i] << endl;
    if (a[i] > 1) {
      ans -= (a[i] * (a[i] - 1)) / 2;
    }
  }

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


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


using namespace std;

int a[3];


int main(){
    for(int i = 0; i < 3; i++) a[i] = 0;
    string str;
    cin >> str;
    a[str[0]-'a']++;
    a[str[1]-'a']++;
    a[str[2]-'a']++;
    if(a[0] == 1 && a[1] == 1 && a[2] == 1)
        cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
//  cout.precision(15); cout << fixed;

typedef pair<ll, ll> P;

int main() {
  int a, b, c, d; cin >> a >> b >> c >> d;
  
  if (a > c) {
    swap(a, c);
    swap(b, d);
  }
  
  [&]{
    // a b c d
    if (b <= c) { cout << 0 << endl; return; }
    // a c b d
    if (c < b and b <= d) { cout << b-c << endl; return; }
    // a c d b
    if (c < b and d <= b) { cout << d-c << endl; return; }
    
    assert(false);
  }();
  
  return 0;
}


Measured memory_bytes: 3596
#[macro_use]
mod input {

use std;
use std::io;

const SPLIT_DELIMITER: char = ' ';

#[macro_export]
#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

#[allow(dead_code)]
pub fn input_line_str() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
pub fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}

#[allow(dead_code)]
pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
where
    T: std::str::FromStr,
{
    let mut v: Vec<Vec<T>> = Vec::new();

    for _ in 0..line {
        let vec_line = input_vector();
        v.push(vec_line);
    }
    v
}

#[allow(dead_code)]
pub fn input_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
{
    let mut v: Vec<T> = Vec::new();

    let s = input_line_str();
    let split_result = s.split(SPLIT_DELIMITER);
    for z in split_result {
        let buf = match z.parse() {
            Ok(r) => r,
            Err(_) => panic!("Parse Error"),
        };
        v.push(buf);
    }
    v
}

#[allow(dead_code)]
pub fn str2vec(s: &str) -> Vec<char> {
    let mut v: Vec<char> = Vec::new();
    for c in s.chars() {
        v.push(c);
    }
    v
}
}

use input::*;

fn median(v: &Vec<isize>) -> (isize, isize) {
    let mut vbuf = v.clone();
    vbuf.sort();
    if vbuf.len() % 2 != 0 {
        let ans = vbuf[(vbuf.len() - 1) / 2];
        (ans, ans)
    } else {
        let a = vbuf[(vbuf.len() - 1) / 2] as f64;
        let b = vbuf[(vbuf.len() - 1) / 2 + 1] as f64;
        let ans = (a + b) / 2.0;
        (ans.floor() as isize, ans.ceil() as isize)
    }
}

fn main() {
    let n: isize;
    input!(n);
    let mut v = input_vector::<isize>();
    for (i, x) in v.iter_mut().enumerate() {
        *x = *x - i as isize - 1;
    }

    let (j, k) = median(&v);

    let mut ans = 0;
    let mut ans2 = 0;
    for z in v {
        ans += (j - z).abs();
        ans2 += (k - z).abs();
    }
    p(std::cmp::min(ans, ans2));
}

Measured memory_bytes: 8444
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

struct union_find{
    vector<ll> parent;
    union_find(ll n){
        parent.resize(n);
        rep(i, 0, n) parent[i] = i;
    }

    ll root(ll x){
        if(parent[x] == x) return x;
        parent[x] = root(parent[x]);
        return parent[x];
    }

    void unite(ll x, ll y){
        ll rx = root(x);
        ll ry = root(y);
        if(rx != ry) parent[rx] = ry;
    }

    bool same(ll x, ll y){
        ll rx = root(x);
        ll ry = root(y);
        if(rx == ry) return true;
        return false;
    }
};

int main(){
    // input
    ll N, M;
    cin >> N >> M;
    vector<ll> a(M), b(M);
    rep(i, 0, M) cin >> a[i] >> b[i];

    // union find
    ll ans = 0;
    rep(i, 0, M){
        union_find t(N+1);
        rep(j, 0, M){
            if(j == i) continue;
            t.unite(a[j], b[j]);
        }
        bool f = false;
        rep(j, 2, N+1){
            if(!t.same(1, j)) f = true;
        }
        if(f) ans++;
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 2005;
 
int n;
int a[N], cache[N][N];
pair<int, int> b[N];
 
int dp(int idx, int i, int j)
{
	if(idx > n)
		return 0;
	int &ans = cache[idx][i];
	if(ans != -1)
		return ans;
	ans = abs(i - b[idx].second) * b[idx].first + dp(idx + 1, i + 1, j);
	ans = max(ans, abs(j - b[idx].second) * b[idx].first + dp(idx + 1, i, j - 1));
	return ans;
 
}
 
int32_t main()
{
	IOS;
	memset(cache, -1, sizeof(cache));
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		b[i].first = a[i];
		b[i].second = i;
	}
	sort(b + 1, b + n + 1);
	reverse(b + 1, b + n + 1);
	int ans = dp(1, 1, n);
	cout << ans;
	return 0;
}


Measured memory_bytes: 35272
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n - 1; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define RFOR(i, start, end) for (int i = start - 1; 0 <= i; i--)
#define ALL(a) a.begin(), a.end()
using ll = long long;
using namespace std;
constexpr int INF32       = 1'050'000'000;
constexpr long long INF64 = 4'000'000'000'000'000'000;
constexpr int MOD7        = 1'000'000'007;
constexpr int MOD9        = 1'000'000'009;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
void scan() {}
template <class H, class... T> void scan(H &&head, T &&... args) {
    std::cin >> head;
    scan(std::forward<T>(args)...);
}
template <class T> void scan(std::vector<T> &v) {
    for (auto &&i : v) {
        scan(i);
    }
}

vector<string> split(const string &s, char remove) {
    istringstream stream(s);
    string field;
    vector<string> ans;
    while (getline(stream, field, remove)) {
        ans.emplace_back(field);
    }
    return ans;
}

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

    string s;
    scan(s);
    ll ans = 0;

    auto sum = [](string x) {
        auto v = split(x, '+');
        ll ret = 0;
        for (auto &&i : v) {
            ret += stoll(i);
        }
        return ret;
    };

    auto dfs = [&](auto f, int now, string frm) {
        if (now == s.size()) {
            ans += sum(frm);
            return;
        }
        f(f, now + 1, frm + string{s[now]});
        f(f, now + 1, frm + "+" + string{s[now]});
    };

    dfs(dfs, 1, {s[0]});
    print(ans);

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e3+4;
const int MD=1e9+7;
int a[M],b[M],c[M*M],d[M*M],cnt=0,cnt1=0;
ll ans=1;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		a[i]=x;
		c[x]++;
		if(c[x]>1) 
		{
			cout<<"0";
			return 0;
		}
	}
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		b[i]=x;
		d[x]++;
		if(d[x]>1) 
		{
			cout<<"0";
			return 0;
		}
	}
	for(int i=n*m;i>=1;i--)
	{
		if(c[i] && d[i]) continue;
		else if(c[i])
		{
			cnt=0;
			for(int j=1;j<=m;j++)
			{
				if(b[j]>i) cnt++;
			}
			ans=(ans*cnt)%MD;
		}
		else if(d[i])
		{
			cnt=0;
			for(int j=1;j<=n;j++)
			{
				if(a[j]>i) cnt++;
			}
			ans=(ans*cnt)%MD;
		}
		else
		{
			cnt=cnt1=0;
			for(int j=1;j<=n;j++)
			{
				if(a[j]>i) cnt++;
			}
			for(int j=1;j<=m;j++)
			{
				if(b[j]>i) cnt1++;
			}
			ll tp=cnt*cnt1-(n*m-i);
			ans=(ans*tp)%MD;
		}
		//cout<<ans<<" ";
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 2304
#include <stdio.h>
int main(void)
{
  int i,j,n,a,b,sum=0,t_sum=0,tem;
  scanf("%d%d%d",&n,&a,&b);
  for(i=1;i<=n;i++)
  {
    tem=i;
    //printf("tem:%d\n",tem);
    while(tem>0)
    {
      t_sum+=tem%10;
      tem=tem/10;
    }
    if(t_sum>=a && t_sum<=b)
    {
      sum+=i;
    }
    //printf("tsum:%d sum:%d\n",t_sum,sum);
    t_sum=0;
  }
  printf("%d\n",sum);
  return 0;
}


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

typedef long long LL;
LL C(LL n,LL m)
{
    LL sum=1;
    for(LL i=1;i<=m;i++)
        sum=sum*(n+1-i)/i;
    return sum;
}
LL foo[56];
int cmp(LL a,LL b)
{
    return a>b;
}
int main()
{
    LL n,a,b;
    cin>>n>>a>>b;
    for(int i=0;i<n;i++)
        cin>>foo[i];
    sort(foo,foo+n,cmp);
    LL goo=0;
    LL koo=0;
    LL soo=0;
    for(LL i=0;i<a;i++)
    {
        soo+=foo[i];
    }
    for(LL i=0;i<n;i++)
    {
        if(foo[i]==foo[a-1])
        {
            goo++;
            if(i<a)
                koo++;
        }
    }
    LL sum=0;
    if(koo==a)
    {
        for(int i=a;i<=b;i++)
        {
            sum+=C(goo,i);
        }
    }
    else
    {
        sum+=C(goo,koo);
    }
    cout<<fixed<<setprecision(15)<<(double)soo/a<<endl;
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
X, N = map(int, input().split())
p_lst = list(map(int, input().split()))
o_lst = list(range(0,102))
lst = list(set(p_lst) ^ set(o_lst))

if X in lst:
    print(X)
else:
    for i in range(100):
        if X - i in lst:
            print(X-i)
            break
        if X + i in lst:
            print(X+i)
            break

Measured memory_bytes: 9204
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX


lli d, n, m;
lli e[100001], k[100001];
lli p[300005], s[100005];
lli satos[100001];
lli cookies;

int func(int h);

int main(){
	
	while(true){
		
	scanf("%lld", &d);
		if(d == 0) break;
		
		memset(e,0,sizeof(e));
		memset(k,0,sizeof(k));
		memset(p,0,sizeof(p));
		memset(s,0,sizeof(s));
	
	scanf("%lld%lld", &n, &m);
	e[0] = 0;
	reg(i, 1, n-1) scanf("%lld", &e[i]);
	rep(i,m) scanf("%lld", &k[i]);
	
	
	sort(e, e + n);
	
	rep(j,3) rep(i,n) p[i + j * n] = e[i] + j * d;
	
	rep(i,m) s[i] = d + k[i];
		
	cookies =0;
	
	rep(i,m) cookies += func(i);
	
	printf("%lld\n", cookies);
		
	}
	
	return 0;
}


int func(int h){
	int lb = 0, ub = 3 * n - 3;
	
	while (ub - lb > 1){
		int mid = (lb + ub) / 2;
		
		if(p[mid] > s[h]){
			ub = mid;
		}else{
			lb = mid;
		}
	}
	
	
	//satos[h] = min(abs(p[ub] - s[h]), abs(s[h] - p[lb]));
	satos[h] = min(p[ub] - s[h], s[h] - p[lb]);
	/*if(satos[h] < 0) {
		printf("%d,%d,%d,%d\n", ub, lb, 3*n-1, p[lb]);
		exit(0);
	}*/
	
	//satos[h] = min(satos[h], abs(s[h] - p[ub+1]));
	//satos[h] = min(satos[h], abs(s[h] - p[lb-1]));
	
	
	
	return satos[h];
	
}

Measured memory_bytes: 5816
#include <iostream>
#include <string>

struct Node {
	int key;
	Node *left = nullptr;
	Node *right = nullptr;
	Node *parent = nullptr;

	Node(int k): key(k) {}
};

Node *root;

void bst_insert(int key) {
	Node *p = nullptr;
	Node *n = root;

	while (n) {
		p = n;
		if (key < n->key) {
			n = n->left;
		} else if (key > n->key) {
			n = n->right;
		}
	}

	Node *node = new Node(key);
	node->parent = p;
	if (!p) {
		root = node;
	} else if (key < p->key) {
		p->left = node;
	} else {
		p->right = node;
	}
}

bool bst_find(Node *tree, int key) {
	if (!tree) return false;

	if (tree->key == key) {
		return true;
	} else if (key < tree->key) {
		return bst_find(tree->left, key);
	} else {
		return bst_find(tree->right, key);
	}

	return false;
}

/*
bool bst_find(int key) {
	Node *n = root;
	while (n) {
		if (key == n->key) {
			return true;
		} else if (key < n->key) {
			n = n->left;
		} else {
			n = n->right;
		}
	}
	return false;
}
*/

void preorder(Node *tree) {
	if (tree) {
		std::cout << " " << tree->key;
		preorder(tree->left);
		preorder(tree->right);
	}
}

void inorder(Node *tree) {
	if (tree) {
		inorder(tree->left);
		std::cout << " " << tree->key;
		inorder(tree->right);
	}
}

int main()
{
	int m;
	std::cin >> m;
	while (m--) {
		std::string operation;
		std::cin >> operation;
		if (operation == "insert") {
			int k;
			std::cin >> k;
			bst_insert(k);
		} else if (operation == "find") {
			int k;
			std::cin >> k;
			// if (bst_find(k)) {
			if (bst_find(root, k)) {
				std::cout << "yes" << std::endl;
			} else {
				std::cout << "no" << std::endl;
			}
		} else {
			inorder(root);
			std::cout << std::endl;
			preorder(root);
			std::cout << std::endl;
		}
	}

	return 0;
}


Measured memory_bytes: 21900
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin >> n >> k;
  string s; cin >> s;
  if(s[k-1]=='A')s[k-1]='a';
  if(s[k-1]=='B')s[k-1]='b';
  if(s[k-1]=='C')s[k-1]='c';
  
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
///******* In the name of Allah *******///

#include <bits/stdc++.h>
using namespace std;

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

void Ok()
{
    long long int a,b,c,d,e,f,g,h,t,i,j,k,l1,l2,m,n,x,y,sum,ans_1,ans_2,ans_3,cnt,Max,Min,flag,div,rcv,temp;
    long double aa,bb,cc,dd,ee,ff,gg;
    char aaa[100013],bbb[1013],ccc[1013],alpbt;

    cin>>a>>b>>c;
    d = a*c;
    if(d<=b)
        cout<<c<<endl;
    else
    {
        e = (b/a);
        cout<<e<<endl;
    }

    return;
}

int main()
{
    Ok();

    return 0;
}


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

typedef long long  ll;

constexpr ll MOD = 1000000007;
ll INF = 100000000000000;
double PI = 3.1415926535;

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

ll tableF[200010];
ll tableI[200010];

ll modfact(ll a,ll m){
  if(tableF[a] != (ll)-1){
    return tableF[a];
  }
  if(a == 1){
    tableF[1] = 1;
    return (ll)1;
  }
  ll res = a * modfact(a-1,m) % m;
  tableF[a] = res;
  return res;
}

ll modpow(ll a,ll n,ll m){//modpow(a,n,m) := a ^ n (mod m)
  ll res = 1;
  while(n > 0){
    if(n & 1)res = res * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return res;
}

ll modinv(ll a,ll p){//modinv(a,p) := pを法とするaの逆元(※pは素数でなければならない)
    ll res = modpow(a,p-2,p);
    return res;
}

ll modCON(ll n,ll r,ll m){
   ll res = 1;
   if(r == 0 || n == 0){
     return (ll)1;
   }
   res *= tableF[n];
   res %= m;
   res *= tableI[r];
   res %= m;
   res *= tableI[n-r];
   res %= m;
   return res;
}


int main(){
    ll H,W,A,B;cin >> H >> W >> A >> B;
    ll ans = 0;
    fill(tableF,tableF+200010,-1);
    fill(tableI,tableI+200010,-1);
    tableF[0] = 1;
    tableI[0] = 1;
    for(int i = 1;i < 200010;i++){
      tableF[i] = modfact(i,MOD);
      tableI[i] = modinv(tableF[i],MOD);
      //cout << tableF[i] << ' ' << tableI[i] << endl;
    }
    for(int i = B+1;i <= W;i++){
        //cout <<i-1+H-A-1 << ' ' << H-A-1 << ' ' << W-i+A << ' ' <<  A-1 << endl;;
        //cout << modCON(i-1+H-A-1,H-A-1,MOD) << ' ' << modCON(W-i+A-1,A-1,MOD) << endl;
        ans += modCON(i-1+H-A-1,H-A-1,MOD)*modCON(W-i+A-1,A-1,MOD);
        ans %= MOD;
    }
    //cout << modCON(3,3,MOD) << endl;
    cout << ans << endl;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    string q;
    cin>>q;
    int p=q.size();
    bool n=false,e=false,w=false,s=false;
    rep(i,p){
        if(q[i]=='N') n=true;
        else if(q[i]=='E') e=true;
        else if(q[i]=='W') w=true;
        else if(q[i]=='S') s=true;
    }
    if(n&&!s) cout<<"No";
    else if(e&&!w) cout<<"No";
    else if(w&&!e) cout<<"No";
    else if(s&&!n) cout<<"No";
    else cout<<"Yes";
}

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

using namespace std;

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

    vector<int> v(n, k - q);
    for (int i = 0; i < q; i++) {
        int a;
        cin >> a;
        v[a - 1]++;
    }

    for (auto x:v) {
        cout << (x > 0 ? "Yes" : "No") << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
x1, y1, x2, y2 = map(int, input().split())
n = x2 - x1
m = y2 - y1
x3 = x2 - m
y3 = y2 + n
x4 = x3 - n
y4 = y3 - m
print("{0} {1} {2} {3}".format(x3, y3, x4, y4))

Measured memory_bytes: 3060