akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
#define Yes "Yes"
#define No "No"
#define YES "YES"
#define NO "NO"
typedef long long ll;

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

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/
struct mint {
    long long x;
    mint(long long _x=0):x((_x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint modpow(long long t) const {
        if (!t) return 1;
        mint a = modpow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return modpow(MOD-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};
struct combination {
    vector<mint> fact, ifact;
    //constructor(initiation)
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < MOD);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint Comb(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
    mint H(int n, int m){
        return Comb(n + m, m);
    }
};

combination comb(2000100);
// (0, 0) ~ (a, b)までの和
// (2, 2)だったら、(3 + 3) C (3) - 1
mint f(int a, int b){
    return comb.Comb(a+1 + b + 1, a + 1) - 1;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int a,b,c,d;
    cin>>a>>b>>c>>d;

    mint ans = f(c, d) - f(a-1, d) - f(c, b-1) + f(a-1, b-1);
    cout<<ans.x<<endl;
}

Measured memory_bytes: 31488
a=input()
cnt=0
e=["L","U","D"]
o=["R","U","D"]
for i in range(len(a)):
  if i%2==0:
    if a[i] in o:
      pass
    else:
      cnt+=1
      break
  else:
    if a[i] in e:
      pass
    else:
      cnt+=1
      break

if cnt==0:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n,k;
  cin>>n;
   int A[n];
  for(int i=0;i<n;i++){
    cin>>A[i];
  }
  int dp[n];
  dp[0]=0;
  dp[1]=abs(A[1]-A[0]);
  for(int i=2;i<n;i++){
  	dp[i]=min(dp[i-2]+abs(A[i]-A[i-2]),dp[i-1]+abs(A[i]-A[i-1]));
  }
   cout<<dp[n-1];
    }


Measured memory_bytes: 4300
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  vector<int> M(N, 0);
  if (S[0] == 'M'){
    M[0] = 1;
  }
  for (int i = 1; i < N; i++){
    if (S[i] == 'M'){
      M[i] = M[i - 1] + 1;
    } else {
      M[i] = M[i - 1];
    }
  }
  vector<long long> M2(N, 0);
  for (int i = 1; i < N; i++){
    if (S[i] == 'C'){
      M2[i] = M2[i - 1] + M[i - 1];
    } else {
      M2[i] = M2[i - 1];
    }
  }
  vector<int> C(N, 0);
  if (S[0] == 'C'){
    C[0] = 1;
  }
  for (int i = 1; i < N; i++){
    if (S[i] == 'C'){
      C[i] = C[i - 1] + 1;
    } else {
      C[i] = C[i - 1];
    }
  }
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++){
    int k;
    cin >> k;
    long long ans = 0;
    for (int j = 0; j < N; j++){
      if (S[j] == 'D'){
        int R = min(N - 1, j + k - 1);
        ans += M2[R] - M2[j];
        ans -= (long long)(C[R] - C[j]) * M[j];
      }
    }
    cout << ans << endl;
  }
}

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


int main() {
  string s;
  cin >> s;
  int sum = 0;
  
  for(char x : s) sum += (x -'0');
  
  cout << ((sum%9 == 0)? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 3724
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>

using namespace std;
#define     loop(n,i,a)     for(int i=a;i<n;i++)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     vi              vector<int>
#define     vll             vector<ll>
#define     sz(x)           (int)x.size()
#define     pb              push_back
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

int main() {
	int n;cin>>n;
	int arr[n+1],cum[n+1]={},Xo[n+1]={};
	loop(n+1,i,1){
		cin>>arr[i];
		if(!i)
			cum[i]=arr[i],Xo[i]=arr[i];
		else{
			cum[i]=cum[i-1]+arr[i];
			Xo[i]=(Xo[i-1]^arr[i]);
		}
	}
	ll res=0;
	loop(n+1,i,1){
		int l=i,r=n,len=i;
		while(l<=r){
			int mid=(l+r)/2;
			if(cum[mid]-cum[i-1]==(Xo[mid]^Xo[i-1])){
				len=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		res+=(len-i+1);
	}
	cout<<res<<endl;
}


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

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

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

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

    // input;
    vector<ll> A(3);
    FOR(i, 0, 3){
        cin >> A.at(i);
    }
    sort(ALL(A));
    if(A[0]==5 && A[1]==5 && A[2]==7){
        p_yes();
    }else{
        p_no();
    }
    
    return 0;
}

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

int main()
{
    int n;
    cin >> n;
    ll a[n];
    for(int i=0; i<n; i++)
    {
       cin >> a[i];
    }
    ll L[n+1], R[n+1];
    L[0]=0;
    R[n]=a[n-1];
    for(int i=0; i<n-1; i++)
    {
        L[i+1] = __gcd(L[i], a[i]);
    }
    for(int i=n; i>=1; i--)
    {
        R[i-1] = __gcd(R[i], a[i-1]);
    }
    ll ans=0;
    for(int i=0; i<n; i++)
    {
        if(i==0)
            ans=max(ans, R[i+1]);
        else if(i==n-1)
            ans=max(ans, L[i]);
        else
        ans=max(ans, __gcd(L[i], R[i+1]));

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


Measured memory_bytes: 2560
#include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int X1, Y1, X2, Y2, W, H;
        rep(i,n){
            cin >> X1 >> Y1 >> W >> H;
            X2 = X1 + W;
            Y2 = Y1 + H;
            int cat, cx, cy, ans = 0;;
            cin >> cat;
            rep(j, cat){
                cin >> cx >> cy;
                if((cx >= X1 && cy >= Y1) && (cx <= X2 && cy <= Y2))
                    ans++;
            }
            cout << ans << endl;
        }
    }
}

Measured memory_bytes: 1160
fun main(args: Array<String>) {
    val L = nextInt()
    var l = L
    var dl = 0
    var ce = 0
    val te = BooleanArray(20)
    while (l > 0) {
        if (l and 1 != 0) {
            te[dl] = true
            ce += 1
        }
        l = l ushr 1
        dl += 1
    }
    println("${dl} ${(dl - 1) * 2 + ce - 1}")
    l = L
    var t = 1
    for (i in 1 until dl) {
        println("${i} ${i + 1} ${0}")
        println("${i} ${i + 1} ${t}")
        if (te[i - 1]) {
            println("${i} ${dl} ${l - t}")
            l -= t
        }
        t = t shl 1
    }
}
fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }


Measured memory_bytes: 33784
#include <iostream>

using namespace std;

int n, p[105], cnt[105], cal[10];
bool pri[105];

void euler()
{
	for (int i = 1; i <= 100; i++) pri[i] = 1;
	pri[0] = 0;
	pri[1] = 0;
	for (int i = 2; i <= 100; i++)
	{
		if (pri[i])
		{
			p[++p[0]] = i;
		}
		for (int j = 1; j <= p[0], i * p[j] <= 100; j++)
		{
			pri[i * p[j]] = 0;
			if (i % p[j] == 0) break;
		}
	}
}

int main()
{
	cin >> n;
	euler();
	for (int i = 1; i <= n; i++)
	{
		int now = 1, cur = i;
		while (cur > 1)
		{
			if (cur % p[now] == 0)
			{
				cur /= p[now];
				cnt[now]++;
			}
			else now++;
		}
	}
	for (int i = 1; i <= 100; i++)
	{	
		if (cnt[i] >= 74) cal[5]++;	
		if (cnt[i] >= 24) cal[4]++;
		if (cnt[i] >= 14) cal[3]++;
		if (cnt[i] >= 4) cal[2]++;
		if (cnt[i] >= 2) cal[1]++;
	}
	
	cout << cal[2] * max(0, cal[2] - 1) * max(0, cal[1] - 2) / 2 + cal[3] * max(0, cal[2] - 1) + cal[4] * max(0, cal[1] - 1) + cal[5] << endl;
	return 0;
}
/*
75 = 
75 = 74
3 * 25 = 2 * 24
5 * 15 = 4 * 14
3 * 5 * 5 = 2 * 4 * 4 */

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

using namespace std;

int main (){
	
	//freopen("t.txt","r",stdin);
	int n; cin>>n;
	int a[MAXN];
	long long dp[MAXN];
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[1]=0;
	dp[2]=abs(a[2]-a[1]);
	for (int i=3;i<=n;i++){
		
		dp[i]=min ( (dp[i-1]+abs(a[i]-a[i-1])),	
					(dp[i-2]+abs(a[i]-a[i-2])) );
	}
	cout<<dp[n];
}

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

int main()
{
  int N; cin >> N;
  vector<ll> A(N+1), B(N);
  rep(i,N+1) cin >> A[i];
  rep(i,N) cin >> B[i];
  ll ans = 0;
  rep(i,N) {
    ans += min(A[i], B[i]);
    if(A[i]<B[i]) {
      if(A[i+1] < B[i]-A[i]) {
        ans += A[i+1];
        A[i+1] = 0;
      } else {
        ans += B[i]-A[i];
        A[i+1] -= B[i]-A[i];
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**7)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N, M = reads()
X = reads()
X.sort()
diff = [X[i] - X[i-1] for i in range(1, M)]
diff.sort()
i = max(M-N, 0)
print(sum(diff[:i]))


Measured memory_bytes: 56744
package main

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

const pi = math.Pi

var mod int = pow(10, 9) + 7
var Umod uint64 = 1000000007
var ans, cnt, sum int = 0, 0, 0

type key struct {
	i, num int
}

func main() {
	reader.Split(bufio.ScanWords)
	N, _ := strconv.Atoi(read())
	A := make(SortBy, N)
	for i := 0; i < N; i++ {
		v, _ := strconv.Atoi(read())
		A[i] = key{i + 1, v}
	}
	sort.Sort(A)
	for i := 0; i < N-1; i++ {
		fmt.Printf("%d ", A[i].i)
	}
	fmt.Printf("%d\n", A[N-1].i)
}

/*  ----------------------------------------  */

var reader = bufio.NewScanner(os.Stdin)

func read() string {
	reader.Scan()
	return reader.Text()
}

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

func gcd(x, y int) int {
	if x%y == 0 {
		return y
	} else {
		r := x % y
		return gcd(y, r)
	}
}

var fac [1000000]int
var finv [1000000]int
var inv [1000000]int

func combination_init() {
	fac[0], fac[1] = 1, 1
	finv[0], finv[1] = 1, 1
	inv[1] = 1

	// invは a^(-1) mod p
	// pをaで割ることを考える

	// p/a*(a) + p%a = p
	// p/a*(a) + p%a = 0          (mod p)
	// -p%a = p/a*(a)             (mod p)
	// -p%a *a^(-1)= p/a          (mod p)
	// a^(-1)= p/a * (-p%a)^(-1)  (mod p)
	// a^(-1) =

	for i := 2; i < 1000000; i++ {
		fac[i] = fac[i-1] * i % mod
		inv[i] = mod - inv[mod%i]*(mod/i)%mod
		finv[i] = finv[i-1] * inv[i] % mod
	}
}

func combination(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[y] * finv[x-y] % mod) % mod
	//return fac[x] / (fac[y] * fac[x-y])
}

func permutation(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[x-y] % mod) % mod
	//return fac[x] / fac[x-y]
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}
func pow(x, y int) int { return int(math.Pow(float64(x), float64(y))) }
func abs(x int) int    { return int(math.Abs(float64(x))) }
func floor(x int) int  { return int(math.Floor(float64(x))) }
func ceil(x int) int   { return int(math.Ceil(float64(x))) }

type SortBy []key

func (a SortBy) Len() int           { return len(a) }
func (a SortBy) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool { return a[i].num < a[j].num }

type PriorityQueue []int

func (h PriorityQueue) Len() int            { return len(h) }
func (h PriorityQueue) Less(i, j int) bool  { return h[i] > h[j] }
func (h PriorityQueue) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *PriorityQueue) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *PriorityQueue) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}


Measured memory_bytes: 4224
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
using ll = long long;
#define INF 1LL << 59
//西暦⇒時代の歴

ll a[201000];
ll N, K;
ll GCD(ll a, ll b)
{
    if (a < b)
        swap(a, b);

    if (b == 0)
        return a;
    return GCD(b, a % b);
}
int main()
{
    cin >> N >> K;
    ll maxV = 0;
    for (int i = 0; i < N; ++i)
    {
        cin >> a[i];
        maxV = max(maxV, a[i]);
    }
    if (N == 1)
    {
        if (a[0] == K)
            cout << "POSSIBLE" << endl;
        else
            cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    ll d = GCD(a[0], a[1]);

    for (int i = 2; i < N; ++i)
    {
        d = GCD(d, a[i]);
    }
    if (K % d == 0 && maxV >= K)
        cout << "POSSIBLE" << endl;
    else
        cout << "IMPOSSIBLE" << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> V;

int main() {
  ll n;
  cin >> n;
  ll x = 1;
  int res = 1;
  while (1) {
    ll sn = n;
    int t = 0;
    while (sn != 0) {
      t += sn%10;
      sn /= 10;
    }
    res = max(t, res);
    n -= n%(10*x)+1;
    if (n < 0) break;
    x *= 10;
  }
  dump(res);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>

//2, 2, 9, 9

int main() {
    int n, t;

    std::cin >> n >> t;

    std::vector<int> v(n);
    std::vector<int> m(n);
    for (int i = 0; i < n; i++) {
        std::cin >> v[i];
    }

    m[n - 1] = v[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        m[i] = std::max(m[i + 1], v[i]);
    }


    int max = 0;
    for (int i = 0; i < n - 1; i++) {
        max = std::max(max, m[i + 1] - v[i]);
    }

    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        if (m[i + 1] - v[i] == max) {
            int c = std::count(v.begin() + i, v.end(), m[i + 1]);
            ans += c;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

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

		int A, B, H, M;

		A = sc.nextInt();
		B = sc.nextInt();
		H = sc.nextInt();
		M = sc.nextInt();

		double thetaA = 30 * H +  0.5 * M;
		double thetaB = 6 * M;

		double xA,yA,xB,yB;

		xA=A*(Math.sin(Math.toRadians(thetaA)));
		yA=A*(Math.cos(Math.toRadians(thetaA)));
		xB=B*(Math.sin(Math.toRadians(thetaB)));
		yB=B*(Math.cos(Math.toRadians(thetaB)));


		double di=(xA-xB)*(xA-xB)+(yA-yB)*(yA-yB);
		double dist=Math.sqrt(di);
		System.out.println(dist);
	}
}


Measured memory_bytes: 35972
/*
AizuOnline A0501
Data Conversion
*/
#include <stdio.h>

char conv_table[256];
long int m;
int n;

void init_conv_table()
{
  int i;
  for(i=0;i<256;i++)
    conv_table[i] =i; 
}

main()
{
  int i;
  char from,to;
  char c;

  while(EOF != scanf("%d",&n) && n)
    {
      init_conv_table();

      for(i=0;i<n;i++)
	{
	  scanf(" %c %c",&from,&to);
	  conv_table[from] = to;
	}

      scanf("%ld",&m);

      while(m--)
	{   scanf(" %c",&c);
	    printf("%c",conv_table[c]);
	}

      printf("\n");
    }
  return(0);
}

Measured memory_bytes: 0
H, W = map(int, input().split())
a = []
for i in range(H):
    y = input()
    if "#" in y:
        a.append(y)
#print(a)
#print(len(a))
ans = [""] * len(a)
for i in range(len(a[0])):
    flag = 0
    for j in range(len(a)):
        if a[j][i] == "#":
            flag = 1
    if flag == 1:
        for j in range(len(a)):
            ans[j] += a[j][i]
for i in range(len(ans)):
    print(ans[i])

Measured memory_bytes: 66596
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<functional>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PA;
const int MOD = 1000000007;
const ll INF=2e18;

ll N,M;
ll a[100010],b[100010];
ll num[10];
string s;
ll F(string now){
  if(now.length()==s.length()){
    ll n=stol(now);
    if(n>N){
      return 0;
    }
    map<ll,ll> mp;
    for(ll i=0;i<now.length();i++){
      mp[now[i]-'0']++;
    }
    if(mp[3]>0 && mp[5]>0  && mp[7]>0 ){
      return 1;
    }
    return 0;
  }
  return F(now+'3')+F(now+'5')+F(now+'7');
}
int main(){
    cin>>N;
    s=to_string(N);
    ll ans=F("");
    for(ll i=0;i<s.length();i++){
      ll n=pow(10,i);
      ans+=F(to_string(n));
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int main(){
    int h,w;
    while(1){
        int h,w;
        scanf("%d %d",&h,&w);
        cin.ignore();
        if (h==0 & w==0){
            return 0;
        }
        char ma[100][100];
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                scanf(" %c",&ma[i][j]);
            }
        }
        int px,py;
        px = py = 0;
        while(1){
            // printf("%d %d %c\n",py,px,ma[py][px]);
            switch(ma[py][px]){
                case '>':
                    ma[py][px] = 'x';
                    px += 1;
                    break;
                case '^':
                    ma[py][px] = 'x';
                    py -= 1;
                    break;
                case '<':
                    ma[py][px] = 'x';
                    px -= 1;
                    break;
                case 'v':
                    ma[py][px] = 'x';
                    py += 1;
                    break;
            }
            if(ma[py][px] == 'x'){
                printf("LOOP\n");
                break;
            }else if (ma[py][px] == '.'){
                printf("%d %d\n", px,py);
                break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3144
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <set>
#include <sstream>
using namespace std;
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
#define chmax(a, b) a = (((a)<(b))?(b):(a))
#define chmin(a, b) a = (((a)<(b))?(a):(b))

const int INF = 1001001001;
const ll MOD = 1e9+7;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){std::fill((T*)array, (T*)(array+N),val);}

class CompareDist
{
public:
    bool operator()(PLL n1,PLL n2) {
				if(n1.first!=n2.first) return n1.first<n2.first;
				else return n1.second<n2.second;
    }
};

#define lengthof(x) (sizeof(x) / sizeof(*(x)))


__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}

signed main(){
  int n; cin>>n;
  int a[2][n];
  rep(i,2){
    rep(j,n) cin>>a[i][j];
  }
  int dp[2][n];
  dp[0][0] = a[0][0]; dp[1][0] = a[0][0] + a[1][0];
  reps(i,n-1){
    dp[0][i] = a[0][i] + dp[0][i-1];
    dp[1][i] = a[1][i] + max(dp[0][i],dp[1][i-1]);
  }
  cout << dp[1][n-1] << endl;
  return 0;
}


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

#define rep(i,a,n) for (int i = a;i<=n;++i)
#define per(i,a,n) for (int i = n;i>=a;--i)
#define all(x) (x).begin(), (x).end()     
#define SZ(x) ((int)x.size())

typedef vector<int> VI;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef long double ld;

mt19937 mrand(random_device{}());
ll rnd(ll a, ll b) { return a + mrand() % (b - a + 1); }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int main() {
      ios::sync_with_stdio(false); cin.tie(0);
#ifdef arrias
      freopen("a.txt", "r", stdin);
#endif
      int N;
      cin >> N;
      ll res = 0;
      rep(i, 1, N) {
            if (i % 3 && i % 5) res += i;
      }
      cout << res << "\n";
      return 0;
}

Measured memory_bytes: 3684
#include<iostream>
#include<cstdio>
#include<string.h>

using namespace std;

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

#define F first
#define S second

int main(){
  string s;
  char sign[3];
  int a[4];
  int temp;
  cin>>s;
  
  for(int i=0;i<4;i++){
    a[i]=s[i]-'0';
  }

  for(int i=0;i<8;i++){
    temp=a[0];
    for(int j=0;j<3;j++){
      if((i>>j)%2) sign[j]='-';
      else sign[j]='+';
    }

    for(int j=0;j<3;j++){
      if(sign[j]=='+') temp+=a[j+1];
      else temp-=a[j+1];
    }
    if(temp==7){
      printf("%d",a[0]);
      for(int j=0;j<3;j++){
	printf("%c%d",sign[j],a[j+1]);
      }
      printf("=7\n");
      break;
    }
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define jkl int debug = 0;
#define RREP(i,a) for(int i=a-1;i>=0;i--)
#define rrep(i,a,b) for(int i=a-1;i>=b;i--)
#define printall(n,array) {for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<int, Pi> V;
typedef vector<ll> VE;
const ll mod = 1e9 + 7; //10^9+7


int main(){
    ll n;
    ll a[100002];
    cin >> n;
    ll four = 0, even = 0, odd = 0;
    REP(i, n){
        cin >> a[i];
        if(a[i] % 4 == 0)four++;
        else if(a[i] % 2 == 0)even++;
        else odd++;
    }
    jkl;
    if(even)odd++;
    if(four + 1 >= odd){print("Yes");}
    else print("No");
}

Measured memory_bytes: 1024
(defun abc130b ()
  (let* ((n (read))
	 (x (read))
	 (li (loop repeat n
		collect (read)))
	 (hoge (loop for i in li
		  for a = 0 then a
		  collect (+ a i)
		  do (setf a (+ a i))))
	 (hage (count-if (lambda (a) (>= x a)) hoge))) 
    (format t "~d~%" (+ 1 hage))))

(abc130b)

Measured memory_bytes: 16224
#include<bits/stdc++.h>
using namespace std;
int a[10005];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,cnt=0;
	cin >> n;
	for(int i=1;i<=150;i++){
		for(int j=1;j<=150;j++){
			for(int k=1;k<=150;k++){
				int x = (i+j)*(i+j)+(k+j)*(k+j)+(i+k)*(i+k);
				if(!(x&1)&&x/2<=10000) a[x/2]++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

Measured memory_bytes: 3712
using System;

namespace AOJ{
  class Program{
    static void Main(string[] args){
      int S=Int32.Parse(Console.ReadLine());
      int a=S%3600;
      int h=S/3600;
      int m=a/60;
      int s=a%60;
      Console.WriteLine(h+":"+m+":"+s);
    }
  }
}

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

using namespace std;

#ifdef ZERO_IQ
ios_base::sync_with_stdio ( false ), cin.tie ( 0 ), cout.tie ( 0 );
#endif

int main() {
    int n,m;
    cin>>n>>m;
    vector<int>v(n);
    for (int i = 0; i < n; ++i) {
        cin>>v[i];
    }
    sort(v.rbegin(),v.rend());
    int minn=INT_MAX;
    for (int j = 0; j <=n-m; ++j) {
        minn=min(minn,(v[j]-v[(j+m-1)]));
    }
    cout<<minn<<endl;
    return 0;
}

Measured memory_bytes: 640
program prob2
    implicit none
    integer::i, l, j
    character(len=100)::S,T
    character::s1,t1
    read(*,*) S
    read(*,*) T
    l = len_trim(S)

    do j = 1, l
        do i = 1, l
            if(S(i:i) .ne. T(i:i))then
                exit
            else if(i == l)then
                write(*,'(a)') "Yes"
                stop
            end if
        end do
        s1 = S(1:1)
        t1 = T(1:1)
        do i = 1, l-1
            S(i:i) = S(i+1:i+1)
        end do
        S(l:l) = s1
    end do

    write(*,'(a)')  "No"
    stop
end program

Measured memory_bytes: 2912
# coding: utf-8


def solve():
    N, *bl = map(int, open(0).read().split())
    al = [0] * N
    al[0], al[-1] = bl[0], bl[-1]
    
    for i in range(N-2, 0, -1):
        al[i] = min(bl[i], bl[i-1])
    
    print(sum(al))


if __name__ == '__main__':
    solve()

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <utility>
#include <string>
#include <cmath>
#include <set>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; ++i)
typedef long long ll;
typedef pair<int,int> pii;
int main(){
    int n;
    cin >> n;
    vector<int>x(n+1);
    ll ans = 0;
    ll temp = 0;
    rep(i,n){
        cin >> x[i];
    }
    x[n]=0;
    rep(i,n+1){
        if(x[i]!=0){
            temp += x[i];
        }
        else{
            ans += temp/2;
            temp = 0;
        }
    }
    cout << ans << endl;
}

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

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int w, h, x, y, r;

    cin >> w >> h >> x >> y >> r;

    if((x + r) > w) cout << "No" << endl;
    else if((x - r) < 0) cout << "No" << endl;
    else if((y + r) > h) cout << "No" << endl;
    else if((y - r) < 0) cout << "No" << endl;
    else cout << "Yes" << endl;
    
}


Measured memory_bytes: 3216
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define fore(x, c) for(auto &&x : c)
#define rep(i, a, n) for(int i = a, i##len = (int)(n); i < i##len; ++i)
#define rrep(i, a, n) for(int i = (int)(n - 1); i >= a; --i)
#define sz(c) ((int)c.size())
#define contains(c, x) (c.find(x) != end(c))
#define inseg(l, x, r) ((l) <= (x) && (x) < (r))
#define dump(...)
#define pb push_back
#define eb emplace_back
#define _ 0
const signed INF_ = 1001001001; const long long INF = 1001001001001001001LL;
const int DX[9] = {0,1,0,-1,1,1,-1,-1,0}, DY[9] = {-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os, const vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is, vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
  is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a, const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a, const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap = priority_queue<T, deque<T>, greater<T>>;
struct before_main_function {
  before_main_function() {
      cin.tie(nullptr); ios::sync_with_stdio(false);
      cout << setprecision(15) << fixed;
  }
} before_main_function;
// clang-format on
//------------------8<------------------------------------8<--------------------

signed main() {
  int H, W, K;
  cin >> H >> W >> K;
  int C = 0;
  rep(i, 0, H) {
    string s;
    cin >> s;
    rep(j, 0, W) {
      if (s[j] == '#') C |= (1LL << (i * W + j));
    }
  }
  int tot = __builtin_popcountll(C);
  int ans = 0;
  rep(r, 0, (1LL << H)) {
    rep(c, 0, (1LL << W)) {
      int mask = 0;
      rep(i, 0, H) {
        rep(j, 0, W) {
          if (((r >> i) & 1) || ((c >> j) & 1)) {
            mask |= (1LL << (i * W + j));
          }
        }
      }
      int tmp = tot - __builtin_popcountll(mask & C);
      if (tmp == K) {
        ans++;
      }
    }
  }
  cout << ans << endl;
  return (0 ^ _ ^ 0);
}



Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
#define int long long
//ask the right questions.		

int32_t main() 
{
	int N, W;
	cin >> N >>W;
	int weights[N];
	int value[N];

	int x;
	for(int i=0;i<2*N;i++)
	{
		cin >> x;
		if(i%2==0)
		{
			weights[i/2]=x;
		}
		else
		{
			value[(i-1)/2]=x;
		}
	}

	//let denote the max value when you have capacity_left of w and deciding upon nth item.
	int dp[N+1][W+1];

	//trivial case : choosing over no elements
	for(int i=0; i<=W; i++)
	{
		dp[0][i]=0;
	}

	//base case: choosing when wight capacity is 0
	for(int i=0; i<=N; i++)
	{
		dp[i][0]=0;
	}


	//TIP:
	//you are deciding on the ith item: to take or not
	//if you want to take then you look previously for a state which has not seen ith item and with weight gap of at least 
	//weight[i-1] (ie weight of ith item)
	//you need not look for a greater gap as the max value obtained by a state with greater
	//weight capacity will always be equal or greater than max value obtained by a lower weight capacity state.


	// shift i-1 in weights and values
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=W; j++)
		{			
			if(j>=weights[i-1])     										//want to take
			{
				dp[i][j] = max(dp[i-1][j], dp[i-1][ j-weights[i-1] ] + value[i-1]);	       		
			}
			else
				dp[i][j] = dp[i-1][j];								//dont want to:		
		}		
	}

	cout << dp[N][W] <<endl;

	return 0;
	
}

Measured memory_bytes: 82436
#define _GLIBCXX_IOSTREAM
#include<bits/stdc++.h>
#define maxn 501000
using namespace std;
typedef long long ll;
typedef long double ldb;
struct point{ldb x,y;point(){}point(ldb x,ldb y):x(x),y(y){}}q[maxn],p;
int l,r,n,L;
ldb cross(point a,point b,point c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int main(){
//	printf("[%.3lf]",cross(point{0,0},point{1,1},point{1,0}));
	scanf("%d%d",&n,&L);
	q[r++]=point(0,0);
	for(int i=1;i<=n;++i){
		scanf("%Lf%Lf",&p.y,&p.x);
		p.y*=p.x,p.x+=q[r-1].x,p.y+=q[r-1].y,q[r]=p;
		while(p.x-q[l+1].x>L&&l+1<r)l++;
		if(q[r].x-q[l].x>L){
			ldb k=(q[l+1].y-q[l].y)/(q[l+1].x-q[l].x),b=q[l].y-k*q[l].x;
			q[l].x=p.x-L,q[l].y=q[l].x*k+b;	
		}
//		printf("{%.7lf,%.7lf}",q[l].x,q[l].y);
		printf("%.7Lf\n",(p.y-q[l].y)/(ldb)(p.x-q[l].x));
		while(l+1<r&&cross(q[r-2],p,q[r-1])>=0)r--;//,printf("[ok]");
		q[r++]=p;
	}
}

Measured memory_bytes: 24576
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
//using Debug;
//using static System.Globalization.CultureInfo;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
        Solve();
        //WriteLine(Solve());
    }
    static void Solve()
    {
        var num = Input.num;
        var ar = Input.ar;
        var dp = new long[num + 1,2];
        dp[1, 0] = ar[0];
        dp[1, 1] = -ar[0];
        for(var i = 1; i < num-1; i++)
        {
            dp[i + 1, 0] = Max(dp[i, 0] + ar[i], dp[i, 1] - ar[i]);
            dp[i + 1, 1] = Max(dp[i, 0] - ar[i], dp[i, 1] + ar[i]);
        }
        WriteLine(Max(dp[num-1, 0]+ar[num-1], dp[num-1, 1]-ar[num-1]));
    }
}

public class Input
{
    public static string read => ReadLine();
    public  static int[] ar => Array.ConvertAll(read.Split(' '), int.Parse);
    public  static int num => ToInt32(read);
    public static long[] arL => Array.ConvertAll(read.Split(' '), long.Parse);
    public  static long numL => ToInt64(read);
    public static char[][] gred(int h) 
        => Enumerable.Repeat(0, h).Select(v => read.ToCharArray()).ToArray();
    public static int[][] ar2D(int num)
        => Enumerable.Repeat(0, num).Select(v => ar).ToArray();
    public static long[][] arL2D(int num)
        => Enumerable.Repeat(0, num).Select(v => arL).ToArray();
    public const long Inf = (long)1e18;
    public const double eps = 1e-6;
    public  const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public  const int MOD = 1000000007;
}


Measured memory_bytes: 28636
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def prime(n):
    if(n<=1): return []
    S=[1]*(n+1)
    S[0]=0; S[1]=0
    for i in range(2,n):
        if(S[i]==0): continue
        for j in range(2*i,n+1,i): S[j]=0
    return [p for p in range(n+1) if(S[p])]

def resolve():
    x=int(input())
    P=prime(2*10**5)
    for p in P:
        if(p>=x):
            print(p)
            return
resolve()

Measured memory_bytes: 41584
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int T = scan.nextInt();
        int A = scan.nextInt();
        float[] arr = new float[n];
        
        for(int i = 0; i < n; i++) arr[i] = (float)Math.abs(A - (T - 0.006 * scan.nextInt()));
        
        int res_index = 0;
        float min = Float.MAX_VALUE;
        
        for(int i = 0; i < n; i++){
            if(arr[i] < min){
                res_index = i+1;
                min = arr[i];
            }
        }
        
        System.out.println(res_index);
    }
}


Measured memory_bytes: 22356
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

int main() {
    
    ll n,x;
    while(true) {
        cin >> n >> x;
        if(n == 0 and x == 0){
            break;
        }
        ll ans = 0;
        for(ll i=1;i<=n;i++){
            for (ll j=1;j<=n;j++){
                for (ll k=1;k<=n;k++){
                    if(i+j+k == x and i != j and j != k and k != i){
//                        cout << i << j << k << endl;
                        ans++;
                    }
                }
            }
        }
        cout << ans/6 << endl;
    }



}





Measured memory_bytes: 3084
#include <stdio.h>
#define SIZE 64

int main(void) {
  char str[SIZE],buf[SIZE];
  fgets(str,SIZE,stdin);

  int i = 0;
  while(1) {
    if((str[i] == '\0')||(str[i] == '\n')) break;
    buf[i] = str[i];
    i++;
  }

  int j;
  for(j = i-1;j >= 0;j--) {
    printf("%c",buf[j]);
  }

  printf("\n");

  return 0;
}

Measured memory_bytes: 520
#include <stdio.h>

int main(void)
{
    static int i = 0;
    int n;
   
    while(1) {
        scanf("%d", &n);
        if ( n == 0) {
            break;
        } else {
            i++;
            printf("Case %d: %d\n", i, n);
        }
    }

    return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1000005

using namespace std;

int n, a[N], yer[N];

int main(){
	// ///////////////////////////////////////
	// freopen("in.txt", "r", stdin);				//
	// freopen("out.txt", "w", stdout);			//
	// ///////////////////////////////////////
	cin >> n;

// a   = {2, 3, 1};
// yer = {3, 1, 2};

	for(int i = 0; i < n; i++) {
		cin >> a[i];
		yer[ a[i] ] = i + 1;
	}
	for(int i = 1; i <= n; i++)
		cout << yer[i] << " ";

	//yer[i] su anlama gelir : i. sayinin nerede oldugu

	return 0;
}


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

int main(){
	int n;
	cin >> n;
	vector<long long> v(n+1);
	
	v[0] = 2;
	v[1] = 1;
	for (int i =2; i<n+1; i++){
		v[i] = v[i-1] + v[i-2];
	}
	cout << v[n];
		
}


Measured memory_bytes: 256
N, M = map(int, input().split())
node = [0] * (N+1)

for m in range(M):
    a, b = map(int, input().split())
    node[a] += 1
    node[b] += 1

if all(map(lambda x: x%2==0, node)):
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3956
#include<stdio.h>
int main(){
  int a,b,c;
  scanf("%d %d %d",&a,&b,&c);
  int dif;
  dif = a-b;
  int ans;
  ans = c-dif;
  if(ans<=0)printf("%d",0);
  else printf("%d",ans);
  return 0;
}


Measured memory_bytes: 128
// Problem : E - Max-Min Sums
// Contest : AtCoder - AtCoder Beginner Contest 151
// URL : https://atcoder.jp/contests/abc151/tasks/abc151_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e10
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

int binpow(int x,int y){
    x %= mod;
    int res = 1;
    while(y){
        if(y&1) res = (res*x)%mod;
        x = (x*x)%mod;
        y = y/2;
    }
    return res;
}
 
int inv(int a){
    return binpow(a,mod-2);
}
 
int fact[N], invfact[N];
 
void precompute(){
    fact[0] = 1;
    for(int i=1;i<N;i++) fact[i] = (fact[i-1]*i)%mod;
    invfact[N-1] = inv(fact[N-1])%mod;
    for(int i=N-2;i>=0;i--) invfact[i] = (invfact[i+1]*(i+1))%mod;
}
 
int ncr(int n, int r){
    if(n<r) return 0;
    return (((fact[n]*invfact[r])%mod)*invfact[n-r])%mod;
}

void solve(){
    precompute();
    int n,k;
    cin>>n>>k;
    vi a(n);
    for(int &i : a) cin>>i;
    sort(all(a));
    int smx = 0, smn = 0;
    for(int i=0;i<n;i++){
        smx = (smx + ((ncr(i,k-1)*a[i])%mod+mod)%mod)%mod;
        smn = (smn + ((ncr(n-i-1,k-1)*a[i])%mod+mod)%mod)%mod;
    }
    int ans = (smx-smn+mod)%mod;
    cout<<ans<<endl;
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 5528
using System;

public class Hello
{
    public const int MOD = 1000000007;
    public static void Main()
    {
        var t = Console.ReadLine().Trim();
        var b = Console.ReadLine().Trim();
        var ans = goDP(t, b);
        Console.WriteLine(ans);

    }
    static long goDP(string t, string b)
    {
        var tL = t.Length;
        var bL = b.Length;
        var dp = new long[bL + 1, tL + 1];
        for (int i = 1; i <= tL; i++)
            if (b[0] == t[i - 1]) dp[1, i] = dp[1, i - 1] + 1;
            else dp[1, i] = dp[1, i - 1];
        for (int i = 2; i <= bL; i++)
            for (int j = 1; j <= tL; j++)
            {
                if (b[i - 1] == t[j - 1]) dp[i, j] = dp[i, j - 1] + dp[i - 1, j - 1];
                else dp[i, j] = dp[i, j - 1];
                dp[i, j] %= MOD;
            }
        return dp[bL, tL];
    }
}


Measured memory_bytes: 23104
n = int(input())
an = list(map(int, input().split()))

steps = []
amin, amax = min(an), max(an)
sum_min, sum_max = amin, amax
flg_min, flg_max = True, True

for a in an:
  if a == amin and flg_min:
    flg_min = False
    continue
  if a == amax and flg_max:
    flg_max = False
    continue
  
  if a >= 0:
    steps.append([sum_min, a])
    sum_min -= a
  else:
    steps.append([sum_max, a])
    sum_max -= a

steps.append([sum_max, sum_min])

print(sum_max - sum_min)
for step in steps:
  print(' '.join(map(str, step)))

Measured memory_bytes: 22452
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(final String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Map<String, Integer> map = new HashMap<String, Integer>();
		while(n-->0) {
			String z = sc.next();
			map.put(z, map.getOrDefault(z, 0) + 1);
		}
		System.out.println("AC x " + map.getOrDefault("AC", 0));
		System.out.println("WA x " + map.getOrDefault("WA", 0));
		System.out.println("TLE x " + map.getOrDefault("TLE", 0));
		System.out.println("RE x " + map.getOrDefault("RE", 0));
	}
}


Measured memory_bytes: 58464
// Note that by default C++ creates a max-heap 
// for priority queue 
#include <iostream> 
#include <queue> 
#include <bits/stdc++.h>
using namespace std; 



int main () 
{ 
       int n;
       cin>>n;
       unordered_map<string,int>m;
       while(n--)
       {
           string s;
           cin>>s;
           m[s]++;
       }
       cout<<m.size()<<endl;
       
       
    
} 



Measured memory_bytes: 17792
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k,x=0;
    cin>>k;
    for(int i=1; i<=k; i++){
        for(int j=1; j<=k; j++){
            for(int l=1; l<=k; l++){
                int y= __gcd(__gcd(i, j),l);
                x=x+y;
            }
        }
    }
    cout<<x;
}


Measured memory_bytes: 3628
n = int(input())

ll = []
for i in range(n):
  a = list(str(i+1))
  ll.append(a[0]+a[-1])
ls = sorted(list(set(ll)))
lc = []
for s in ls:
  lc.append(ll.count(s))

r = len(ls)
ans = 0
for i in range(r):
  if ls[i][0] == ls[i][1]:
    ans += lc[i] ** 2
  for j in range(i):
    if ls[i][0] == ls[j][1] and ls[i][1] == ls[j][0]:
      ans += 2 * lc[i] * lc[j]

print(ans)

Measured memory_bytes: 15808
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
using namespace std;

int main(){

    unsigned long long int x;
    cin >> x;


//*
    const int max = 8000;

    vector<unsigned long long int> five(max, 0);

    for (int i = 0; i < max;++i)
    {
        unsigned long long int tmp = 1;
        for (int j = 0; j < 5;++j){
            tmp *= i;
        }
        five[i] = tmp;
    }

 //   for(const auto& a:five){
  //      cout << a << endl;
   // }

    for (int i = 0; i < max;++i){
        for (int j = 0; j < max;++j){
            unsigned long long int tmp = five[i] - five[j];
            if(tmp==x){
                cout << i << " " << j << endl;
                return 0;
            }
            tmp = five[i] + five[j];
            if(tmp==x){
                cout << i << " " << -j << endl;
                return 0;
            }
        }
    }

        for (const auto &a : five)
        {
            cout << a << endl;
        }
//*/
        return 0;
}

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

#define step(i, s, n, d) for(int i=s; i<n; i+=d)
#define FOR(i,s,n) step(i,s,n,1)
#define rep(i,n) FOR(i,0,n)
#define gets(x) x; cin >> x;
#define puts(x) x; cout << x << endl;
#define list_input(x, n) x[n]; rep(i,n){ gets(x[i]);}
#define ll long long

int main(){
  int a, b;
  cin >> a >> b;
  if(a+b >= 10){
    puts("error")
  }else{
    puts(a+b)
  }
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    //AtCoder Beginner Contest 175
    public class QuestionA
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            long result = 0;  //Ans用

            //入力
            string[] str = Console.ReadLine().Split(' ');
            var n = long.Parse(str[0]);  //用意する数
            var x = long.Parse(str[1]);  //1回の個数
            var t = long.Parse(str[2]);  //1回の時間

            //焼き回数
            var bakeCount = n / x;
            if (n % x != 0)
            {
                bakeCount++;
            }

            result = bakeCount * t;

            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 27480
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int p, q, r;
  cin >> p >> q >> r;

  int ans = p+q;
  ans = min(ans, p+r);
  ans = min(ans, q+r);

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

ll n, a, b, c;
string s;

vector<string> vs;
vector<P> vi;

bool flag(P i, P j){
	if (i.first == j.first){
		return i.second < j.second;
	}
	else return i.first > j.first;
}

int main(){
	bool f = 0;
	while (cin >> n&&n){
		REP(i, n){
			cin >> s >> a >> b >> c;
			vi.push_back(make_pair(a * 3 + c, i));
			vs.push_back(s);
		}
		sort(ALL(vi), flag);
		if (f)cout << endl;
		REP(i, vi.size()){
			cout << vs[vi[i].second] << "," << vi[i].first << endl;
		}
		f = 1;
		vs.clear();
		vi.clear();
	}
}

Measured memory_bytes: 1212