akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
int main()
{
  int n;
  cin >> n;
  int i,j;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  vector<bitset<20>> bs(n);
  rep(i,n) bs[i] = bitset<20>(a[i]);
  vector<vector<int>> bcount(n+1,vector<int>(20,0));
  rep(i,n)
  {
    rep(j,20)
    {
      bcount[i+1][j] = bcount[i][j] + bs[i][j];
    }
  }
  int left=0;
  int right=1;
  ll ans=0;
  while(right<=n)
  {
    bool ok=true;
    rep(j,20)
    {
      if(bcount[right][j]-bcount[left][j]>1)
      {
        ok=false;
      }
    }
    if(ok)
    {
      ans+=(right-left);
      right++;
    }
    else
    {
      left++;
      if(left>=right)right=left;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 25984
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int maxX = sc.nextInt();
        int minY = sc.nextInt();
        
        for(int i = 0; i < N; i++){
            int x = sc.nextInt();
            maxX = Math.max(maxX, x);
        }
        
        for(int i = 0; i < M; i++){
            int y = sc.nextInt();
            minY = Math.min(minY, y);
        }
        
        if( maxX < minY ){
            System.out.println("No War");
        } else {
            System.out.println("War");
        }
        
    }
}


Measured memory_bytes: 23764
#include <stdio.h>
#include <assert.h>

#define BUF_SIZE 1000
#define STACK_SIZE 1000

static int stack[STACK_SIZE];
static int top;

void initialize(void)
{
  top = 0;

  return ;
}

void push(int n)
{
  stack[top] = n;
  top ++;

  return;
}

int pop(void)
{
  top--;
  assert(top >= 0);

  return stack[top];
}

void print_stack(void)
{
  int i;

  for(i = 0; i < top; i++){
    printf("%d\n", stack[i]);
  }
  return;
}

int main(void)
{
  char buf[BUF_SIZE];
  char c;
  int n0, n1;

  while((c = fgetc(stdin)) != '\n'){
    if(c == ' ' ) continue;

    if(isdigit(c)){
      int i = 0;
      do{
        buf[i] = c;
        i++;
        c = fgetc(stdin);
      }while(isdigit(c));

      ungetc(c, stdin);

      buf[i] = '\0';
      push(atoi(buf));
      continue;
    }

    /* print_stack(); */

    switch(c){
    case '+':
      n1 = pop();
      n0 = pop();
      push(n0 + n1);
      break;
    case '-':
      n1 = pop();
      n0 = pop();
      push(n0 - n1);
      break;
    case '*':
      n1 = pop();
      n0 = pop();
      push(n0 * n1);
      break;
    default:
      assert(0);
    }
  }

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

  return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <float.h>
#include <limits>
#include <vector> 
#include <string.h>
#include <iomanip>

#define rep(i,a,n) for(ll int (i) = (a);(i) < (n);(i)++)
#define urep(i,a,n) for(ll int (i) = (a);(i) > (n);(i)--)
#define MOD 1000000007
#define INF 2147483647
#define ll long long
#define asort(a) sort(a.begin(),a.end());//昇順ソート
#define usort(a) sort(a.rbegin(),a.rend());//降順ソート

using namespace::std;

int jo(ll int a, ll int b){//累乗
    ll int num=1;
    rep(i,0,b) num=num*a;
    return num;
}
char tobig(char s){//char大文字化
  return (s-0x20);
}
char tolow(char s){//char小文字化
  return (s+0x20);
}
int ctoi(char a){//char->int
  if('0'<=a&&a<='9') return (a-'0');
  return -1;
}

int gcd(ll int a,ll int b) {//最大公約数
  if(a<b) return gcd(b,a);
  int c;
  while ((c=a%b)) {
    a=b;
    b=c;
  }
  return b;
}
int lcm(ll int a,ll int b){//最小公倍数
 return (a*b)/gcd(a,b);
}


int act(int num){
  num=floor((double(jo(num,2))+4.0)/8.0);
  return num;
}

int main(){
  string S;
  cin>>S;
  string ans="";
  rep(i,0,S.length()){
    if(S[i]=='B'){
      if(ans!=""){
        ans.pop_back();
      }
    }else{
      ans=ans+S[i];
    }
  }
  cout<<ans;
      
      
}




// vector<vector<int>> 変数名(左の個数, vector<int>(右の個数));

//cout<<fixed<<setprecision(n);  //小数点n桁まで表示

//  vector<pair<int,int>> data(N);  //2つのデータを格納、.first/.secondで参照
// pairのソートはfirst優先の昇順


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String... args) {
		Scanner scan = new Scanner(System.in);
		scan.nextInt();
		char[] chars = scan.next().toCharArray();
		HashMap<Character, ArrayList<Integer>> map = new HashMap<Character, ArrayList<Integer>>();
		for (char c = 'a'; c <= 'z'; c++) {
			map.put(c, new ArrayList<Integer>());
		}
		for (int i = 0; i < chars.length; i++) {
			map.get(chars[i]).add(i);
		}

		int q = scan.nextInt();
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < q; i++) {
			int q1 = scan.nextInt();
			if (q1 == 1) {
				int q2 = scan.nextInt();
				char q3 = scan.next().charAt(0);
				remove(map, q2);
				add(map, q2, q3);
			} else {
				int q2 = scan.nextInt();
				int q3 = scan.nextInt();
				list.add(count(map, q2, q3));
			}
		}

		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
		scan.close();
	}

	private static void remove(HashMap<Character, ArrayList<Integer>> map, int q2) {
		for (char c = 'a'; c <= 'z'; c++) {
			ArrayList<Integer> list = map.get(c);
			int index = search(list, 0, list.size(), q2 - 1);
			if (index < list.size() && list.get(index) == q2 - 1) {
				list.remove(index);
			}
		}
	}

	private static void add(HashMap<Character, ArrayList<Integer>> map, int q2, char q3) {
		ArrayList<Integer> list = map.get(q3);
		int index = search(list, 0, list.size(), q2 - 1);
		if (index < list.size()) {
			list.add(index, q2 - 1);
		}else {
			list.add(q2 - 1);
		}
	}

	private static int count(HashMap<Character, ArrayList<Integer>> map, int q2, int q3) {
		int count = 0;
		for (char c = 'a'; c <= 'z'; c++) {
			ArrayList<Integer> list = map.get(c);
			if (list.size() > 0) {
				int index = search(list, 0, list.size(), q2 - 1);
				if (index < list.size() && list.get(index) <= q3 - 1) {
					count++;
				}
			}
		}

		return count;
	}

	private static int search(ArrayList<Integer> list, int start, int end, int value) {
		int length = (end - start) / 2;
		int target = Math.max(Math.min(start + length, end - 1), 0);

		if (target >= list.size()) {
			return target;
		}else if (list.get(target) == value) {
			return target;
		} else if (list.get(target) > value) {
			if (length < 1) {
				return target;
			}
			return search(list, start, start + length, value);
		} else {
			if (length < 1) {
				return target + 1;
			}
			return search(list, target + 1, end, value);
		}
	}
}

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

int main() {
    long long K, A, B;
    long long num;
    long long ans = 1;
    cin >> K >> A >> B; 

    if (A+1 > K){
        ans = ans + K;
        cout << ans << endl;
        return 0;
        }

    if (A+1 <= K && A+2 <= B){
        K = K-(A+1);
        ans = B;

        num = K/2;
        K = K%2;
        ans = ans + num*(B-A) ;
        }
    
    ans = ans + K;
    cout << dec << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int in[5][5];
int count(int a,int b,int c,int d){
  bool h=true;
  loop(i,a,b+1)loop(j,c,d+1)if(in[i][j]!=1)h=false;
  if(!h)return 0;
  return (b-a+1)*(d-c+1);
}
int main(){
  int n;
  cin>>n;
  while(n--){
    rep(i,5)rep(j,5)cin>>in[i][j];
    int maxi=0;
    rep(a,5)loop(b,a,5)rep(c,5)loop(d,c,5)maxi=max(maxi,count(a,b,c,d));
    cout<<maxi<<endl;
  }
}

Measured memory_bytes: 1164
def main():
    from collections import defaultdict

    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))

    for i in range(1, N + 1):
        A[i] += A[i - 1]
        A[i] %= K

    for i in range(1, N + 1):
        A[i] -= i
        A[i] %= K

    # print (A)

    d = defaultdict(int)

    for i in range(1, min(N + 1, K)):
        d[A[i]] += 1

    ans = 0
    tmp = min(N + 1, K)
    for i in range(N):
        ans += d[A[i]]
        d[A[i + 1]] -= 1
        if tmp <= N:
            d[A[tmp]] += 1
            tmp += 1

    print (ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 114508
import Control.Monad
import Data.Bool
import Data.List

readInt = readLn :: IO Int
readInts = map read . words <$> getLine :: IO [Int]
readNInts = flip replicateM readInts

main :: IO ()
main = do
  s <- getLine
  print $ maximum $ map length $ filter f $ nub $ concatMap inits $ tails s

f :: String -> Bool
f xs = null xs'
  where
    xs' = filter (\x -> x `notElem` ['A', 'C', 'G', 'T']) xs

Measured memory_bytes: 508
a,b,k = map(int,input().split())
x=0
y=[0]
c=min(a,b)

if a==1 or b==1:
    print(1)
    exit()
    
for d in range(1,c+1):
    if a%d==0 and b%d==0:
            y.append(d)

print(y[-k])

Measured memory_bytes: 3060
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#include<stdio.h>
#include<functional>
#include<queue>

using ll = long long;

using namespace std;

ll mod = 1000000007;

ll n_pow(ll a, ll n) {
	if (n == 0)return 1;
	ll t = n_pow(a, n / 2);
	t *= t;
	t %= mod;
	if (n % 2 == 1)t *= a;
	return t % mod;
}

const int INF = 1001001001;


int main() {
	int n, m;
	cin >> n >> m;
	vector<bool>step(n + 1, true);
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		step[a] = false;
	}
	vector<ll>dp(n + 1);
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		for (int jump = 1; jump <= 2; jump++) {
			if (i + jump > n)continue;
			if (step[i + jump]) {
				dp[i + jump] += dp[i];
				dp[i + jump] %= mod;
			}
		}
	}
	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)

int N, A[1 << 18], B[1 << 18];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = N; i >= 1; i--) {
		int sum = A[i];
		for (int j = i * 2; j <= N; j += i) sum ^= B[j];
		B[i] = sum;
	}
	vector<int> vec;
	for (int i = 1; i <= N; i++) { if (B[i] == 1) vec.push_back(i); }

	cout << vec.size() << endl;
	for (int i = 0; i < vec.size(); i++) { if (i) cout << " "; cout << vec[i]; } cout << endl;
	return 0;
}

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

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

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

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

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

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) &= ~(1 << (b))
#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)
#define bitcount(a) __builtin_popcountll((a))

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

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

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

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

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

  int c0 = 0;
  for (int i = 0; i < s.size(); i++) {
    if (i % 2 == 0) {
      if (s[i] == '0') {
        c0++;
      }
    } else {
      if (s[i] == '1') {
        c0++;
      }
    }
  }

  int c1 = 0;
  for (int i = 0; i < s.size(); i++) {
    if (i % 2 == 0) {
      if (s[i] == '1') {
        c1++;
      }
    } else {
      if (s[i] == '0') {
        c1++;
      }
    }
  }

  cout << min(c0, c1) << endl;
  return 0;
}


Measured memory_bytes: 512
import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().rstrip()
MOD = 10**9+7

n, k = map(int, input().split())
g = [list() for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

cnt = [0] * n

def dfs(v, p):
    n_cnt = 1 if p == -1 else 2
    for nv in g[v]:
        if nv == p: continue
        cnt[nv] = n_cnt
        n_cnt += 1
        dfs(nv, v)

dfs(0, -1)
ans = 1

for x in cnt:
    ans *= max(0, (k - x))
    ans %= MOD

print(ans)


Measured memory_bytes: 88112
# 入力
N,A,B=map(int,input().split())

c=0
for x in range(1,N+1):
  y=list(str(x))

  # 各桁の和を求める
  z=sum([int(a) for a in y])

  # 各桁の和がA以上B以下なら加算
  if A<=z and z<=B:
    c+=x

# 出力
print(c)

Measured memory_bytes: 2940
#include <iostream>
#include <vector>
using namespace std;
int n,k;
vector<int> v[2000];

int f(int x, int y, int z, int w){
    int r=0;
    if(z>w)r++;
    for(int i=0;i<v[y].size();i++){
        if(v[y][i]!=x){
            r+=f(y, v[y][i], z+1, w);
        }
    }
    return r;
}

int main(void){
    cin>>n>>k;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int c=1e9;
    for(int i=0;i<n;i++){
        int d=0;
        if(k%2==0){
            d=f(-1, i, 0, k/2);
        }else{
            int e=0;
            for(int j=0;j<v[i].size();j++){
                int x=f(i, v[i][j], 1, k/2);
                int y=f(i, v[i][j], 1, k/2+1);
                d+=x;
                e=max(e, x-y);
            }
            d-=e;
        }

        c=min(c, d);
        //cout<<d<<endl;
    }
    cout<<c<<endl;
}


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

bool overflow(long long a, long long b)
{
    if (a <= (1000000000000000000 / b)) return 0;
    return 1;
}

int main()
{
    long long n;
    cin >> n;
    vector<long long> v(n);
    bool f = 1;
    for (int i = 0; i < n; i++){
        cin >> v[i];
        if (v[i] == 0) f = 0;
    }
    if (f == 0){
        cout << 0 << endl;
        return 0;
    }
    f = 0;
    long long mul = 1LL;
    for (int i = 0; i < n; i++){
        if (overflow(mul, v[i])){
            f = 1;
            break;
        }
        mul *= v[i];
    }
    if (overflow(mul, 1LL)) f = 1;
    if (f) puts("-1");
    else cout << mul << endl;
}

Measured memory_bytes: 4048
def gcd(a,b):
  if a < b:
    a, b = b, a
  while a % b != 0:
    a, b = b, a % b
  return b

def getAns(a, b, c):
  num_c = b // c - (a - 1) // c
  return num_c

a, b, c, d = map(int, input().split())

# cについて
num_c =getAns(a,b,c)
#print(num_c)

# dについて
num_d =getAns(a,b,d)
#print(num_d)

# cとdの公倍数について
cd = c * d // gcd(c,d)
num_cd = getAns(a,b,cd)
#print(num_cd)

print(b - a + 1 - (num_c + num_d - num_cd))


Measured memory_bytes: 38256
#include<bits/stdc++.h>
#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
class Point
{
    public:
    double x, y;

    Point(double x = 0, double y = 0): x(x), y(y) {}

    Point operator + (Point p) {return Point(x + p.x, y + p.y); }
    Point operator - (Point p) {return Point(x - p.x, y - p.y); }
    Point operator * (double a) {return Point(x * a, y * a);}
    Point operator / (double a) {return Point(x / a, y / a);}

    double abs() {return sqrt(norm());}
    double norm() {return x * x + y * y;}
    
    bool operator < (const Point &p) const {
        return x != p.x ? x < p.x : y < p.y;
    }

    bool operator == (const Point &p) const{
        return equals(x, p.x) && equals(y, p.y);
    }
};typedef Point Vector;

struct Segment {
    Point p1, p2;
    Segment(Point p1, Point p2):p1(p1), p2(p2){}
};typedef Segment Line;

double dot(Vector a, Vector b){
    return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b){
    return a.x * b.y - a.y * b.x;
}

bool isOrthogonal(Vector a, Vector b){
    return equals(dot(a, b), 0.0);
}

bool isOrthogonal(Point a1, Point a2, Point b1, Point b2){
    return isOrthogonal(a1 - a2, b1 - b2);
}

bool isParallel(Vector a, Vector b){
    return equals(cross(a, b), 0.0);
}

bool isParallel(Point a1, Point a2, Point b1, Point b2){
    return isParallel(a1 - a2, b1 - b2);
}
double get_distance(Point a, Point b){
    return (a-b).abs();
}
double get_distance(Line l, Point p){
    return abs(cross(l.p2 - l.p1, p - l.p1) / (l.p2 - l.p1).abs());
}
double get_distanceSP(Segment s, Point p){
    if(dot(s.p2 - s.p1, p - s.p1) < 0.0) return (p - s.p1).abs();
    if(dot(s.p1 - s.p2, p - s.p2) < 0.0) return (p - s.p2).abs();
    return get_distance(s, p);
}
int ccw(Point p0, Point p1, Point p2){
    Vector a = p1 - p0, b = p2 - p0;
    if (cross(a, b) > EPS) return 1;
    if (cross(a, b) < -EPS) return -1;
    if (dot(a, b) < -EPS) return 2;
    if (a.norm() < b.norm()) return -2;
    return 0;
}
bool intersect(Point p0, Point p1, Point p2, Point p3){
    if (ccw(p0, p1, p2) == 0 || ccw(p0, p1, p3) == 0 || 
        ccw(p2, p3, p0) == 0 || ccw(p2, p3, p1) == 0)
        return true;
    if (ccw(p0, p1, p2) * ccw(p0, p1, p3) == -1 && ccw(p2, p3, p0) * ccw(p2, p3, p1) == -1)
        return true;
    return false;
}
double get_distanceSS(Segment s1, Segment s2){
    if (intersect(s1.p1, s1.p2, s2.p1, s2.p2)) return 0.0;
    return min(min(get_distanceSP(s1, s2.p1), get_distanceSP(s1, s2.p2)),
    min(get_distanceSP(s2, s1.p1), get_distanceSP(s2, s1.p2)));
}

#include<iostream>
#include<iomanip>
int main(){
    int q, dots[8];
    std::cin >> q;
    for (int i = 0; i < q; i++)
    {
        for (int i = 0; i < 8; i++)
            std::cin >> dots[i];
        Point a1 = Point(dots[0], dots[1]);
        Point a2 = Point(dots[2], dots[3]);
        Point b1 = Point(dots[4], dots[5]);
        Point b2 = Point(dots[6], dots[7]);
        Segment s = Segment(a1, a2), t = Segment(b1, b2);
        cout << fixed << setprecision(10) << get_distanceSS(s, t) << endl;
    }   
}


Measured memory_bytes: 3296
N = int(raw_input())
nums = list(map(int,raw_input().split()))
lo = -pow(10,9)
hi = pow(10,9)

def f(cur):
    res = 0
    for i in range(N):
        res += abs(nums[i]-(cur+i+1))
    return res

ans = pow(10,15)

while lo<=hi:
    mid = (lo+hi)/2
    t1,t2 = f(mid),f(mid+1)
    ans = min(ans,t1,t2)
    if t1>t2:
        lo = mid+1
    else:
        hi = mid-1

print ans

Measured memory_bytes: 56156
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int i,sum=0;
  for(i=0;i<s.size();i++){
    sum+=(s[i]-'0');
  }
  if(sum%9==0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

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

int main(){
  int H,W;
  cin >> H >> W;
  for(int i=0;i<H;i++){
    string C;
    cin >> C;
    cout << C << endl;
    cout << C << endl;
  }
}

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

#include <iostream>
#define rep(i,a,b) for(i=a;i<=b;i++)
#define pb push_back
#define sort_incr(v) sort(v.begin(),v.end());
#define sort_decr(v) {sort(v.begin(),v.end()); reverse(v.begin(),v.end());}
#define take_input(v,n) for(ll i=0,temp;i<n;i++){cin>>temp;v.pb(temp);}
#define fastio {ios_base::sync_with_stdio(false);    cin.tie(NULL);}
#define ALL(v) v.begin(),v.end()

typedef long long ll;
using namespace std; 

int main() 
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt","r", stdin);
    freopen("output.txt","w", stdout);
    #endif

    int n;
    cin>>n;
    if(n>=30)
    	cout<<"Yes";
    else cout<<"No";


	return 0;
} 























Measured memory_bytes: 3592
// #pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define N 1000000007
#define N2 998244353
#define Nmax 100001
#define INF (ll)1e18
#define pll pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
#define vv vector
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(ll i=m;i<(n);i++)
#define repr(i,n) repr2(i,n,0)
#define repr2(i,m,n) for(ll i=m;i>=(n);i--)
#define get(n) ll (n); scanf("%lld",&(n));
#define get2(n,k) ll (n),(k); scanf("%lld%lld",&(n),&(k));
#define get3(n,m,k) ll (n),(m),(k); scanf("%lld%lld%lld",&(n),&(m),&(k));
#define gets(s) string (s); cin >> (s);
#define ALL(c) (c).begin(),(c).end()
#define fill_nums(A,n) vector<ll> A((n)); for(ll i=0;i<n;i++) scanf("%lld",&A[i]);
#define fill_edges(adj,m) for(ll i=0;i<m;i++) {ll a, b; scanf("%lld %lld",&a,&b); adj[a-1].pb(b-1); adj[b-1].pb(a-1);}
#define fill_direct(adj,m) for(ll i=0;i<m;i++) {ll a, b; scanf("%lld %lld",&a,&b); adj[a-1].pb(b-1);}
#define pi 3.1415926535897
#define noop

int main() {

    get(n);
    gets(s);

    set<ll> se1, se2, se3;

    repr(i,n-1) {

        for(auto j:se2) {
            se3.insert((s[i]-'0')*100+j);
        }

        for(auto j:se1) {
            se2.insert((s[i]-'0')*10+j);
        }

        se1.insert(s[i]-'0');
    }
    
    printf("%lld\n", (ll)se3.size());

    return 0;  
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

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

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
dest = [[] for _ in range(n)]
comein = [0 for _ in range(n)]
ro = [True for _ in range(n)]
dp = [0 for _ in range(n)]
for _ in range(m):
	x, y = map(int, input().split())
	dest[x-1].append(y-1)
	comein[y-1] += 1
	ro[y-1] = False

def search(leaf):
	global dp
	for i in dest[leaf]:
		comein[i] -= 1
		dp[i] = max(dp[i], dp[leaf] + 1)
		if comein[i] == 0:
			search(i)
	return

for j in range(n):
	if ro[j] == True:
		search(j)

print(max(dp))

Measured memory_bytes: 168752
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <sstream>
using namespace std;


vector<string>split(string s, char delim){
  int len = s.length();
  string currStr = "";
  vector<string>retVec;
  for(int i = 0;i<len;i++){
    char ch = s[i];
    if(ch==delim){
      retVec.push_back(currStr);
      currStr = "";
    }else{
      currStr += ch;
    }
  }
  retVec.push_back(currStr);
  return retVec;
}



vector<int>strToIntVec(string s){
  int len = s.length();
  //  s = s.substr(1,len-2);
  vector<string>strVec = split(s,' ');
  vector<int>retVec;
  for(int i=0;i<strVec.size();i++){
    int el = atoi(strVec[i].c_str());
    retVec.push_back(el);
  }
  return retVec;
}

class CircleChat{
public:
  long long getMaxComfort(int n, vector<int>&aVec){
    sort(aVec.begin(),aVec.end());
    long long retC = aVec[n-1];
    int currInd = n-2;
    bool shouldChange = false;
    for(int i=n-3;i>=0;i--){
      retC += aVec[currInd];
      if(shouldChange){
	currInd--;
	shouldChange = false;
      }else{
	shouldChange = true;
      }
    }
    return retC;
  }

};
  int main(int argc, const char*argv[]){
    CircleChat cc;
    string nLn,aLn;
    getline(cin,nLn);
    getline(cin,aLn);
    int n = atoi(nLn.c_str());
    vector<int>aVec = strToIntVec(aLn);
    long long maxC = cc.getMaxComfort(n,aVec);
    cout<<maxC<<endl;
    return 0;
  }


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

static const int N = 10001;
static const int INF = (1 << 30);
static const int WHITE = 0;
static const int GRAY  = 1;
static const int BLACK = 2;

int n;
vector<pair<int ,int> > adj[N];

void dijkstra(){
    priority_queue<pair<int,int> > p_q;
    int color[N];
    int d[N];
    for(int i=0;i<n;i++){
        d[i] = INF;
        color[i] = GRAY;
    }

    d[0] = 0;
    p_q.push(make_pair(0,0));
    color[0] = GRAY;

    while(!p_q.empty()){
        pair<int,int> f = p_q.top();
        p_q.pop();
        int u = f.second;
        color[u] = BLACK;

        if(d[u] < f.first*-1) continue;

        for(int i=0;i<adj[u].size();i++){
            int v = adj[u][i].first;
            if(color[v] == BLACK) continue;
            if(d[v] > d[u]+adj[u][i].second){
                d[v] = d[u]+adj[u][i].second;
                p_q.push(make_pair(d[v]*-1,v));
                color[v] = GRAY;
            }
        }
    }

    for(int i=0;i<n;i++){
        cout << i << ' ';
        if(d[i] == INF)
            cout << -1;
        else 
            cout << d[i];
        cout << endl;
    }
}

int main(){
    int k,u,v,c;

    cin >> n;
    for(int i=0;i<n;i++){
        cin >> u >> k;
        for(int j=0;j<k;j++){
            cin >> v >> c;
            adj[u].push_back(make_pair(v,c));
        }
    }

    dijkstra();
}



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

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

    ll h[n];
    rep(i, n){
        cin >> h[i];
    }

    ll dp[n];
    rep(i, n){
        if(i == 0){
            dp[i] = 0;
        }else if(i == 1){
            dp[i] = dp[i-1] + abs(h[i] - h[i-1]);
        }else{
            dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
        }
    }

    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
long long x[N],y[N];
char ch[]={'U','D','R','L'};
int main() 
{
	ios::sync_with_stdio(false); 
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>x[i]>>y[i];
	int m2=0;
	if((x[0]+y[0])%2==0) 
	{
		m2=1;
		for(int i=0;i<n;i++)
			x[i]--;
	}
	for(int i=0;i<n;i++) 
	{
		if((x[i]+y[i])%2==0) 
		{
			cout<<-1<<endl;
			return 0;
		}
	}
	vector<long long>v;
	for(int i=0;i<=31;i++)
		v.push_back(1ll<<i);
	if(m2)
		v.push_back(1);
	reverse(v.begin(),v.end());
	cout<<v.size()<<endl;
	for(auto i=0;i<v.size();i++)
		cout<<v[i]<<" ";
	cout<<endl;
	for(int i=0;i<n;i++) 
	{
		string s;
		if(m2)
			s+="R";
		for(int j=31;j>=0;j--) 
		{
			int tmp=-1;
			long long now=LLONG_MAX;
			for(int k=0;k<4;k++) 
			{
				long long cur=abs(x[i]-dx[k]*(1ll<<j))+abs(y[i]-dy[k]*(1ll<<j));
				if(cur<now)
				{
					now=cur;
					tmp=k;
				}
			}
			x[i]-=dx[tmp]*(1ll<<j);
			y[i]-=dy[tmp]*(1ll<<j);
			s+=ch[tmp];
		}
		cout<<s<<endl;
	}
	return 0;
}
//

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

using namespace std;

#define ff first
#define ss second

int dp[3010][3010], n, T;
pair<int,int> C[3010];

int call(int i, int w) {

    if(i == n || w >= T) return 0LL;
    if(dp[i][w] != -1) return dp[i][w];

    int ret = call(i + 1, w);
    ret = max(ret, C[i].ss + call(i + 1, w + C[i].ff));

    return dp[i][w] = ret;
}

int main() {

    cin >> n >> T;

    for(int i = 0; i < n; i++)cin >>C[i].ff >> C[i].ss;

    sort(C, C+n);

    memset(dp, -1, sizeof dp);

    cout << call(0, 0) << endl;

    return 0;
}

Measured memory_bytes: 35840
#include<bits/stdc++.h>
#define endl '\n'
#define INF (1 << 21)
const int MOD = 1000000009;
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  int p;
  int d1, d2;
  int a_num, ans;
  
  
  cin >> n;

  while(n != 0){
    ans = -1;
    for(int i = 0;i < n;i++){
      cin >> p >> d1 >> d2;
      
      if(d1 + d2 > ans){
	ans = d1 + d2;
	a_num = p;
      }
    }
    cout << a_num << ' ' << ans << endl;
    cin >> n;
  }
         
  return 0;
}




Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)

class rollinghash
{
public:
  const ll MOD = (1LL << 61) - 1;
  const ll MASK61 = MOD;
  const ll MASK31 = (1LL << 31) - 1;
  const ll MASK30 = (1LL << 30) - 1;
  const ll Base = rand() % 1024 + 256;
  const ll POSITIVISER = MOD * 3;

  ll mul(ll a, ll b)
  {
    ll au = a >> 31; // (a / MASK31)
    ll ad = a & MASK31; // (a % MASK31)
    ll bu = b >> 31;
    ll bd = b & MASK31;
    ll m = au * bd + ad * bu;
    ll mu = m >> 30;
    ll md = m & MASK30;

    return au * bu * 2 + mu + (md << 31) + ad * bd;
  }

  ll calcmod(ll x)
  {
    ll xu = x >> 61;
    ll xd = x & MASK61;

    ll ret = xu + xd;
    if (ret >= MOD)
      ret -= MOD;

    return ret;
  }

  vector<ll> powmem;
  vector<ll> hash;

  rollinghash(string S)
  {
    ll N = S.size();

    powmem.resize(N + 1);
    powmem.at(0) = 1;
    for (ll i = 0; i < N; i++)
    {
      powmem.at(i + 1) = calcmod(mul(powmem.at(i), Base));
    }
    
    hash.resize(N + 1);
    hash.at(0) = 1;
    for (ll i = 0; i < N; i++)
    {
      hash.at(i + 1) = calcmod(mul(hash.at(i), Base) + S.at(i));
    }
  }

  ll sub(ll pos, ll len)
  {
    return calcmod(hash.at(pos + len) + POSITIVISER - mul(hash.at(pos), powmem.at(len)));
  }
};

ll N;
string S;

bool check(rollinghash rol, ll len)
{
  map<ll, ll> mp;
  for (ll i = 0; i <= N - len; i++)
  {
    ll tmp = rol.sub(i, len);
    if (mp.count(tmp))
    {
      if (mp.at(tmp) + len - 1 < i)
        return true;
    }
    else
      mp[tmp] = i;
  }
  return false;
}

int main()
{
  cin >> N;
  cin >> S;
  rollinghash rol(S);

  ll ok = 0, ng = N / 2 + 1;
  while (abs(ok - ng) > 1)
  {
    ll mid = (ok + ng) / 2;
    if (check(rol, mid))
      ok = mid;
    else
      ng = mid;
  }
  cout << ok << endl;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

#define ll long long

void output(int*,int);

int main() {

	string S;
	cin >> S;

	vector<ll> vec(4);
	int opt;

	for (int i = 0; i < 4; i++) {
		char c = S[i];
		vec[i] = atoi(&c);
		vec[i] /= 10;
	}

	for (int i = 0; i < (1 << 3); i++) {
		int ans = vec[0];

		for (int j = 2,cnt=1; j >=0; j--,cnt++) {
			if ((1 & (i >> j)) == 1) {
				ans += vec[cnt];
			}
			else {
				ans -= vec[cnt];
			}
		}

		if (ans == 7) {


			cout << vec[0];

			for (int j = 2, cnt = 1; j >= 0; j--, cnt++) {
				if ((1 & (i >> j)) == 1) {
					cout << "+";
				}
				else {
					cout << "-";
				}
				cout << vec[cnt];
			}
			cout << "=7";

			break;
		}

	}

	cout << endl;

	return 0;
}

void output(int* vec,int num) {

	cout << vec[0];

	for (int j = 2, cnt = 1; j >= 0; j--,cnt++) {
		if ((1 & (num >> j)) == 1) {
			cout << "+";
		}
		else {
			cout << "-";
		}
		cout << vec[cnt];
	}
	cout << "=7";
	return;
}

Measured memory_bytes: 256
A,B,M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

ans = []
waribiki = []

for _ in range(M):
    x,y,c = map(int,input().split())
    waribiki.append(a[x-1]+b[y-1]-c)
a_min=min(a)
b_min=min(b)
ab_min = a_min+b_min
waribiki_min = min(waribiki)
print(min(waribiki_min,ab_min))

Measured memory_bytes: 18736
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll N,A,B;
  cin>>N>>A>>B;
  ll zan=N%(A+B);
  ll ans=(N/(A+B))*A;
  ans += min(zan, A);
  cout<<ans<<endl;
}

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

int main()
{
    std::string s;
    std::cin >> s;
    size_t s_size = s.length();

    for(int i=0; i<s_size; i++){
            if (i%2==0){
                if(s[i] == 'L'){
                    std::cout << "No" << std::endl;
                    return 0;
                }
            }
            else{
                if(s[i] == 'R'){
                    std::cout << "No" << std::endl;
                    return 0;
                }
            }
    }


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


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using P = pair<int,int>;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int n; cin >> n;
    ll ans = 0;
    srep(i,1,n+1) {
        if (i%3==0||i%5==0) continue;
        else ans += (ll)i;
    }
    cout << ans << endl;
    return 0;
}






























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

int main()
{
    int n;
    cin >> n;
    int a[n] , b[n], c[n]; 
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=0; i<n; i++) cin >> b[i];
    for(int i=0; i<n; i++) cin >> c[i];
    sort(a, a+n);
    sort(b, b+n);
    sort(c, c+n);
    
  	long long ans = 0;
	for (int i = 0; i < n; i++) {
		long long na = lower_bound(a, a+n, b[i]) - a;
		long long nc = upper_bound(c, c+n, b[i]) - c;
		ans += na * (n-nc);
	}
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,x,y;
struct node{int y,nxt,t;
}g[1000010];int h[100010],tot=0;
int cnt[3],col[100010],_point,_link;
bool vis[100010],_is;
void dfs(int x)
{
    cnt[col[x]]++;vis[x]=1;_point++;
    for(int i=h[x];i;i=g[i].nxt)
    {
        _link+=(g[i].t==1);
        if (!vis[g[i].y]) col[g[i].y]=(col[x]+g[i].t+3)%3,dfs(g[i].y);
        else if (col[g[i].y]!=(col[x]+g[i].t+3)%3) _is=0;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        g[++tot]=node{y,h[x],1};h[x]=tot;
        g[++tot]=node{x,h[y],-1};h[y]=tot;
    }
    long long ans=0;
    for (int i=1;i<=n;i++)
    {
        if (vis[i]) continue;
        _is=1;_point=_link=0;cnt[0]=cnt[1]=cnt[2]=0;
        dfs(i);
        if (!_is) ans+=1ll*_point*_point;
        else if (cnt[0]&&cnt[1]&&cnt[2]) ans+=1ll*cnt[0]*cnt[1]+1ll*cnt[1]*cnt[2]+1ll*cnt[2]*cnt[0];
        else ans+=_link;
    }
    printf("%lld",ans);
    
}

Measured memory_bytes: 7424
#include <bits/stdc++.h>
typedef long long lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()

using namespace std;

void execute()
{
	string input;
	int len;
	cin >> input;
	len = input.size();

	int ans = len / 2;

	for (int i = 0; i < len; i++)
	{
		if (input[i] == 'p')
			ans--;
	}
	cout << ans << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD long(1e9 + 7)
#define INF 98765431219876543
#define bitcnt(a) (ll) __builtin_popcount((a))
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;

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

int main() {
  vector<ll> v[40];
  map<char, char> m;
  map<char, bool> b;
  string s, t;
  cin >> s >> t;

  REP(i, s.size()) {
    if (b[s[i]] == 1) {
      if (t[i] != m[s[i]]) {
        cout << "No" << endl;
        return 0;
      }
    }
    b[s[i]] = 1;
    m[s[i]] = t[i];
  }

  m.clear();
  b.clear();

  REP(i, s.size()) {
    if (b[t[i]] == 1) {
      if (s[i] != m[t[i]]) {
        cout << "No" << endl;
        return 0;
      }
    }
    b[t[i]] = 1;
    m[t[i]] = s[i];
  }

  cout << "Yes" << endl;
}

Measured memory_bytes: 776
#include <iostream>

using namespace std;

int main(){
	
	int r, g, b;
	int soma = 0;
	int i=0;
	
	cin >> r >> g >> b;
	
	while (i < r){
		soma = soma + 100;
		i++;
	}
	
	i = 0;
	while (i < g){
		soma = soma + 10;
		i++;
	}
	
	i = 0;
	
	while (i < b){
		soma = soma + 1;
		i++;
	}

	if(soma%4 == 0){
		cout << "YES";
	}else{
		cout << "NO";
	}
	
	return 0;
}

Measured memory_bytes: 256
//{{{
#include <bits/stdc++.h>
using namespace std;
#define repX(a,b,c,x,...) x
#define repN(a) repX a
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop))(__VA_ARGS__)
#define rrep(...) repN((__VA_ARGS__,rrep3,rrep2))(__VA_ARGS__)
#define loop(n) rep2(i_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define rrep2(i,n) rrep3(i,n,0)
#define rrep3(i,begin,end) for(int i=(int)(begin-1),i##_end=(int)(end);i>=i##_end;--i)
#define foreach(x,a) for(auto&x:a)
using ll=long long;
const ll MOD=(ll)1e9+7;
//}}}

int main(){
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;
  int ansW = a * 100;
  int ansS = 0;
  double ans = 0;
  rep(ai, 31){
    rep(bi, 31){
      int sumW = a * ai * 100 + b * bi * 100;
      if(sumW == 0) continue;
      int sumS = 0;
      if(sumW >= f) continue;
      for(int ci = 0; sumW + ci * c <= f; ci++){
        for(int di = 0; sumW + ci * c + di * d <= f; di++){
          sumS = ci * c + di * d;
          double g = (double)sumS * 100 / (sumS + sumW);
          if(e * (sumS + sumW) >= sumS * (100 + e) && ans < g){
            ans = g;
            ansW = sumW;
            ansS = sumS;
          }
        }
      }
    }
  }
  cout << (ansW + ansS) << " " << (ansS) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int abs(int a){if(a<0)a*=-1;return a;}
int main(){
   int D,N,T[300],A[300],B[300],C[300],dp[300][300];
   cin>>D>>N;
   for(int i=0;i<D;i++)cin>>T[i];
   for(int i=0;i<N;i++)cin>>A[i]>>B[i]>>C[i];
   fill(dp[0],dp[0]+90000,-1);

   for(int i=0;i<N;i++){
        if(A[i]<=T[0]&&B[i]>=T[0])dp[0][i]=0;
   }

   for(int i=0;i<D-1;i++){
        for(int j=0;j<N;j++){
            if(dp[i][j]==-1)continue;
            for(int k=0;k<N;k++){
                if(A[k]>T[i+1]||B[k]<T[i+1])continue;
                dp[i+1][k]=max(dp[i+1][k],dp[i][j]+abs(C[j]-C[k]));
            }
        }
   }
   int M=-1;
   for(int i=0;i<N;i++)M=max(M,dp[D-1][i]);
   cout<<M<<endl;
  
}

Measured memory_bytes: 1516
//“ In order to be irreplaceable, one must always be different”
#include <bits/stdc++.h>
using namespace std;
# define ll long long
#define endl "\n"
# define pi 3.14159265359
# define str string
# define vll vector<ll>
# define vstr vector<str>
# define vchar vector<char>
# define pb push_back
# define popb pop_back
# define pf push_front
# define popf pop_front
# define sll set<ll>
# define schar set<char>
//find()
//erase(x) removes element x
//erase(position,position)
# define qll queue<ll>
# define qstr queue<str>
//front(),back()
# define stll stack<ll>
# define ststr stack<str>
//top()
# define dll deque<ll>
//at()
# define mll map<ll,ll>
#define mchar map<char, ll>
# define mstr map<str,ll>
# define mss map<str,str>
# define mci map<char,ll>
# define vp vector< pair<ll,ll> >
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
# define f(x,y) for(int x=0;x<y;x++)
# define r(x,y) for(int x=y;x>=0;x--)
# define fr(x,y,z) for(int x=y;x<z;x++)
# define rr(x,y,z) for(int x=y;x>z;x--)
ll power(ll a , ll b){ll res=1;for(ll i=0; i<b; ++i){res*=a;}return res;}
ll logx(ll base, ll num){int cnt=0;while(num!=1){num/=base; ++cnt;}return cnt;}
ll gcd(ll a, ll b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b){
    return (a*b)/gcd(a, b);
}
void print(vll a){
    for(int i=0;i<a.size();i++){
        cout<<a[i]<<' ';
    }
    cout<<endl;
}
vll inp(int n){
    vll a;
    ll x;
    f(i,n){
        cin>>x;
        a.pb(x);
    }
    return a;
}

// Return the maximum volume. 
double  maxvolume(double s) 
{ 
	// finding length 
	double length = s / 3; 

	s -= length; 

	// finding breadth 
	double breadth = s / 2; 

	// finding height 
	double height = s - breadth; 
    //cout<<length * breadth * height;
	return length * breadth * height; 
} 


int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int L;
 scanf("%d",&L);
 printf("%.12f\n",(double)L*L*L/27);
}




Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <bitset>
#include <cmath>
#include <vector>
#include <memory>
#include <algorithm>
#include <unordered_set>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <numeric>

using namespace std;
using uint = unsigned int;
using ulong = unsigned long;
using ushort = unsigned short;
using uchar = unsigned char;

int main() {
#ifdef __TEST_CODE
    // A dumb way of inlining test cases
    stringstream input_s(
            "200"
    );
    stringstream output_s;

    string expected_out("10813692\n"
    );
    expected_out += "\n";
    istream &in = input_s;
    ostream &out = output_s;
#else
    istream& in = cin;
        ostream& out = cout;
#endif


    long long k;
    in >> k;
    long long result = 0;

    for (long long i = 1; i <= k; ++i) {
        for (long long j = 1; j <= k; ++j) {
            for (long long l = 1; l <= k; ++l) {
                result += gcd(gcd(i, j), l);
            }
        }
    }

    out << result << endl;


#ifdef __TEST_CODE
    string actual_out = output_s.str();
    cout << actual_out;
    cout << "Output correct: " << (expected_out == actual_out) << endl;
#endif
    return 0;
}


Measured memory_bytes: 3624
#include<cstdio>
long long a,b,x;
long long s,e;
int main()
{
    scanf("%lld%lld%lld",&a,&b,&x);
    if(a%x==0)
		s=a/x;
    else 
		s=a/x+1;
    e=b/x;
    printf("%lld",e-s+1);
    return 0;
}

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

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define ar array
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod = 1e9 + 7;
const ll inf = 2e9 + 5;
double PI = 3.14159265358979323846;

const int N = 2e6 + 5;
vi primes;
vi p(N, 1);
vi cnt(N, 0);

void sieve() {
	p[1] = p[0] = 0;
	for (ll i = 2; i < N; i++) {
		if (p[i]) {
			for (ll j = i * i; j < N; j += i) {
				p[j] = 0;
			}
			primes.pb(i);
		}
	}
}

template<typename T> T gcd(T a, T b) {
	if (a == 0) return b;
	return gcd(b % a, a);
}

template<typename T> T lcm(T a, T b) {
	return (a * b) / gcd(a, b);
}

void solve() {

	sieve();
	int n;
	cin >> n;
	int a[n];
	int G;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}


	G = a[0];
	for (int i = 1; i < n; i++) {
		G = gcd(G, a[i]);
	}

	if (G != 1) {
		cout << "not coprime" << endl;
		return;
	}


	for (int i = 0; i < n; i++) {
		int x = a[i];
		for (int k = 0; k < (int)primes.size() && primes[k]*primes[k] <= x; k++) {
			if (x % primes[k] == 0) {
				if (cnt[primes[k]]) {
					cout << "setwise coprime" << endl;
					return;
				}

				while (x % primes[k] == 0) {
					x = x / primes[k];
				}
				cnt[primes[k]]++;
			}
		}
		if (x > 1) {
			if (cnt[x]) {
				cout << "setwise coprime" << endl;
				return;
			}
			cnt[x]++;
		}
	}

	cout << "pairwise coprime" << endl;

}

int32_t main()
{
	IOS
	// int T; cin >> T; while (T--)
	solve();
	return 0;
}


Measured memory_bytes: 23548
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    ll v;
    cin >> v;
    vector<ll> a(n), c(n);
    unordered_map<ll, int> b;
    rep(i, n) {
        cin >> a[i];
    }
    rep(i, n) {
        int bb;
        cin >> bb;
        rep(j, n) {
            b[bb+a[j]]++;
        }
    }
    rep(i, n) {
        cin >> c[i];
    }
    ll ans = 0;
    rep(i, n) {
        int dd;
        cin >> dd;
        rep(j, n) {
            ans += b[v-dd-c[j]];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 81984
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll> > vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;
typedef pair<ll, ll> P;
const long long INF = numeric_limits<ll>::max();
const long long MOD = 1000000007;
const long double PI = 3.1415926;
template <class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
//char c;
 
#define Endl endl
 
/*--------------------template--------------------*/
 
int main() {
    int X;
    cin >> X;
    ll a = 1;
    FOR(i, 1, X) {
        FOR (j, 2, X) {
            ll  l = pow(i, j);
            if (X < l) {
                break;
            }
            ans = pow(i, j);
        }
        a = max(a, ans);
    }
    cout << a << endl;
    return 0;
}

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

int main() {
    ll X;
    ll ure500, kari, ure5,ans;
    cin >> X;

    ure500 = 0;
    kari = 0;
    ure5 = 0;
    ans = 0;

    ure500 = X / 500;
    kari = X % 500;
    ure5 = kari / 5;
    kari = kari % 5;

    ans = ure500*1000 + ure5*5;
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256