akhauriyash/Code-Regression huggingface dataset:
import java.io.File;
import java.io.FileNotFoundException;
import java.lang.management.ManagementFactory;
import java.lang.management.ThreadMXBean;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws FileNotFoundException {

		ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean();
		long startCpuTime = threadMXBean.getCurrentThreadCpuTime(), stopCpuTime = 0;

		Scanner scan = new Scanner(System.in);
		// Scanner scan = new Scanner(new
		// File("D:\\UserArea\\J0124567\\Downloads\\0542-input.txt"));

		while (scan.hasNext()) {

			int n = scan.nextInt();
			int m = scan.nextInt();
			if (n == 0 && m == 0)
				break;
			int[] s = new int[n];
			for (int i = 0; i < n; i++)
				s[i] = scan.nextInt();

			int p = 0, t = 0;
			for (int i = 0; i < m; i++) {
				p += scan.nextInt();
				if (p < n && t == 0)
					p += s[p];
				if (p >= n - 1 && t == 0)
					t = i + 1;

			}
			// stopCpuTime = threadMXBean.getCurrentThreadCpuTime();

			System.out.println(t);
		}

		scan.close();
		// stopCpuTime = threadMXBean.getCurrentThreadCpuTime();
		// System.out.println("CPU=" + (stopCpuTime - startCpuTime) / 1000000);

		System.exit(0);
	}
}

Measured memory_bytes: 36196
n = int(input())
S = str(input())
r = 0
for i in range(1000):
    t = "{0:03d}".format(i)
    j = 0
    for c in S:
        if t[j] == c:
            j += 1
        if j == 3:
            r += 1
            break
print(r)


Measured memory_bytes: 41052
from sys import stdin
import itertools
import bisect
N = int(stdin.readline().rstrip())
L = [int(x) for x in stdin.readline().rstrip().split()]
L.sort()
ans = 0

for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        k = bisect.bisect_left(L, a+b)
        ans += (k-j-1)
print(ans)

Measured memory_bytes: 3188
from collections import deque

n,q=[int(i) for i in input().split()]
name=[0 for i in range(n)]
time=[0 for i in range(n)]
answer_name=[]
answer_time=[]
total_time=0

for i in range(n):
    name[i],time[i]=input().split()

d_name = deque(name)
d_time = deque(time)

while len(d_name)>0:

    a=d_name.popleft()
    b=int(d_time.popleft())

    if b>q:
        d_name.append(a)
        d_time.append(b-q)
        total_time=total_time+q

    else:
        total_time=total_time+b
        answer_name.append(a)
        answer_time.append(total_time)

for i in range(len(answer_time)):
    print(answer_name[i], answer_time[i])



Measured memory_bytes: 12880
a,b,k=map(int,input().split())
if b-a+1>k:
	a=list(range(a,a+k))
	b=list(range(b-k+1,b+1))
	ans=list(set(a+b))
	ans.sort()
else:
	ans=list(range(a,b+1))
print(*ans,sep='\n')


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

int main() {
  int a;
  double b;
  cin>>a;
  if(a%2==0){
    cout<<0.5000000000<<endl;
  }
  else{
    b=(a+1)/2.00;
    cout<<b/a<<endl;
  }
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s; 
int main()
{
   cin>>s;
   for(int i=0;i<3;i++) 
     {
     	if(s[i]=='7') 
     	{
     		cout<<"Yes";return 0;
		 }
	 }

cout<<"No";
return 0;
}


Measured memory_bytes: 3628
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import combinations_with_replacement
def main():
    n,m,q=map(int,input().split())
    lis=list(combinations_with_replacement(range(1,m+1),n))
    ans=0
    Q=[[int(_) for _ in input().split()] for i in range(q)]
    for l in lis:
        cunt=0
        for q in Q:
            if int(l[q[1]-1])-int(l[q[0]-1])==q[2]:
                cunt+=q[3]
        ans=max(ans,cunt)
    print(ans)
if __name__=='__main__':
    main()

Measured memory_bytes: 21712
class Node:
    def __init__(self, key, parent=None, left=None, right=None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
        

class Tree:
    def __init__(self):
        self.root_node = None
        
    def insert(self, z):
        y = None # y stands for the parent of x
        x = self.root_node # root node
        # First, we ascend the tree until the point where we insert the new node
        while x is not None:
            y = x # set parent
            if z.key < x.key:
                x = x.left # move to the left child
            else:
                x = x.right # move to the right child
        # insert z under y
        z.parent = y
        
        if y is None:
            # when the tree is empty
            self.root_node = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    
    def find(self, k):
        x = self.root_node
        while (x is not None) and (x.key != k):
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x
        
    
    def print_preorder(self, node):
        print(f" {node.key}", end="")
        if node.left is not None:
            self.print_preorder(node.left)
        if node.right is not None:
            self.print_preorder(node.right)

    def print_inorder(self, node):
        if node.left is not None:
            self.print_inorder(node.left)
        print(f" {node.key}", end="")
        if node.right is not None:
            self.print_inorder(node.right)

    def print_nodes(self):
        if self.root_node is None:
            pass
        else:
            self.print_inorder(self.root_node)
            print("")
            self.print_preorder(self.root_node)
            print("")

        
tree = Tree()

m = int(input())

for _ in range(m):
    command = input().split()
    if command[0] == 'print':
        tree.print_nodes()
    elif command[0] == 'find':
        node = tree.find(int(command[1]))
        print("no") if (node is None) else print("yes")
    else:
        key = int(command[1])
        new_node = Node(key)
        tree.insert(new_node)


Measured memory_bytes: 85276
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        char[] s = new char[1200];
        for(int i=0; i<str1.length(); i++){
            s[i] = str1.charAt(i);
            if(Character.isLowerCase(s[i]) == true){
                s[i] = Character.toUpperCase(s[i]);
                System.out.printf("%c", s[i]);
            } else if(Character.isUpperCase(s[i]) == true){
                s[i] = Character.toLowerCase(s[i]);
                System.out.printf("%c", s[i]);
            } else System.out.printf("%c", s[i]);
        }
        System.out.println();
        sc.close();
    }
}


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


int main(){long N, K;
cin >> N >> K;
vector<long> l(N);
rep(i, N) cin >> l.at(i);
sort(l.begin(), l.end());
reverse(l.begin(), l.end());
long ans = 0;
rep(i, K) ans += l.at(i);

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std ;
 
int main(){
    int N,L;cin>>N>>L;
    
    if(L>=0) cout << (L+1+L+N-1)*(N-1)/2;
  else if(L+N-1<0) cout << (L+L+N-2)*(N-1)/2;
  else cout << (L+L+N-1)*N/2;
  
    
    
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int N;
  cin >> N;
  vector<int> v;
  rep(i,N){
    int a;
    cin >> a;
    v.push_back(a);
  }

  ll base = 0;
  vector<ll> sum;
  rep(i,N){
    base += v[i];
    sum.push_back(base);
  }

  ll ret = (ll)1e18;

  REP(i,1,N-2){
    int lhs = 0, rhs = 0;
    { //P, Q
      int lb = 0, ub = i;
      while(ub-lb>1){
        int mid = (lb+ub)/2;
        ll Psum = sum[mid];
        ll Qsum = sum[i] - Psum;
        if(Psum < Qsum) lb = mid;
        else ub = mid;
      }

      lhs = lb;
    }
    {//R, S
      int lb = i+1, ub = N-1;
      while(ub-lb>1){
        int mid = (lb+ub)/2;
        ll Psum = sum[mid] - sum[i];
        ll Qsum = sum[N-1] - sum[mid];
        if(Psum < Qsum) lb = mid;
        else ub = mid;
      }
      rhs = lb;
    }

    REP(j,-5,6){
      REP(k,-5,6){
        int p = lhs + j;
        int q = i;
        int r = rhs+k;
        if(0 <= p && p < q && q < r && r < N){
          ll Psum = sum[p];
          ll Qsum = sum[q] - sum[p];
          ll Rsum = sum[r] - sum[q];
          ll Ssum = sum[N-1] - sum[r];
          
          ll mx = max(Psum, max(Qsum, max(Rsum, Ssum)));
          ll mn = min(Psum, min(Qsum, min(Rsum, Ssum)));
          ret = min(ret, mx - mn);
        }
      }
    }
  }

  cout << ret << endl;
  
  return 0;
}


Measured memory_bytes: 4212
//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;

    vector<pii> v;

    int main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            int n,m,i,j,a,b;
            cin>>n>>m;
            int ar[n+10];
            for(i=0;i<=n+9;++i)
                ar[i]=0;
            for(i=1;i<=m;++i)
            {
                cin>>a>>b;
                ++ar[a];
                --ar[b+1];
            }
            int ct=0,ans=0;
            for(i=1;i<=n;++i)
            {
                ct=ct+ar[i];
                if(ct==m)
                    ++ans;
            }
            cout<<ans<<endl;
        }
        return 0;
    }


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

int inf = 100000000;
int MAX_N = 100005;
vector<int> par(MAX_N ,inf);
vector<int> Rank(MAX_N);

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

int find(int x){
    if(par[x] == x){
        return x;
    }else {
        return par[x] = find(par[x]);
    }
}

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

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

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

int main(){
    int n,m;
    cin >> n >> m;
    init(n);
    for(int i=0;i<m;i++){
        int x,y,z;
        cin >> x >> y >> z;
        x--;y--;
        unite(x ,y);
    }


    int sum = 0;
    for(int i=0;i<n;i++){
        if(i == par[i]) sum++;
    }

    cout << sum << endl;
}

Measured memory_bytes: 1024
from collections import defaultdict
from functools import reduce
INF = int(1e9+7)


def primeFactor(n, pf):
    # 素因数分解
    if n == 1:
        return
    f = 2
    while (f * f <= n):
        if (n % f == 0):
            pf[f] += 1
            n = n // f
        else:
            f += 1
    pf[n] += 1


def main():
    N = int(input())
    d = defaultdict(lambda: 0)
    for i in range(1, N + 1):
        primeFactor(i, d)
    print(reduce(lambda x, y : x * (y + 1) % INF, d.values(), 1))
    return


main()


Measured memory_bytes: 3564
#include <bits/stdc++.h>
#define ll long long
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

using namespace std;

int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }

int main(){
    int n; cin >> n;
    map<string, int> s;
    int max = 0;

    for (int i = 0; i < n; ++i) {
        string tmp;
        cin >> tmp;
        s[tmp]++;
        if(s[tmp]>max){
            max = s[tmp];
        }
    }

    for (const auto& x : s) {
        int v = x.second;
        if(v>max) max=v;
    }
    for(auto & it : s){
        if(it.second==max) cout<<it.first<<endl;
    }

    return 0;

}


Measured memory_bytes: 25216
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
ans = 0 ;count = 0 ;pro = 1

n=int(input())
T=list(map(int,input().split()))
S=sum(T)
m=int(input())
for i in range(m):
    p,x=map(int,input().split())
    p-=1
    print(S-(T[p]-x))


Measured memory_bytes: 38384
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if x >= A[j]:
            i += 1
            A[i], A[j] = A[j], A[i]

    A[i+1], A[r] = A[r], A[i+1]

    return i + 1


def main():
    n = int(input())
    A = list(map(int, input().split()))
    q = partition(A, 0, n-1)
    for i in range(len(A)):
        if i == q:
            A[i] = "[" + str(A[i]) + "]"
        else:
            A[i] = str(A[i])

    print(*A)


if __name__ == "__main__":
    main()


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

typedef long long int ll;
typedef long double ld;

//****************************************************                
#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define pb push_back
#define mp make_pair
#define pf push_front
#define ff first
#define ss second
#define vll vector<ll>
#define pll pair<ll,ll> 
#define vpll vector<pll>
#define all(X) X.begin(),X.end()
#define endl "\n" //comment it for interactive questions
#define trace1(a) cerr << #a << ": " << a << endl;
#define trace2(a,b) cerr << #a << ": " << a << " " << #b << ": " << b << endl;
#define trace3(a,b,c) cerr << #a << ": " << a << " " << #b << ": " << b << " " << #c << ": " << c << endl;
#define trace4(a,b,c,d) cerr << #a << ": " << a << " " << #b << ": " << b << " " << #c << ": " << c << #d << ": " << d << endl;
#define OC   
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
        //*******************************************************
//Some Functions

const ll MOD = (ll)1e9+7; //change it for other mods

ll powmod(ll a,ll b)
{
   ll res = 1;
   while(b > 0) {
      if(b & 1) res = (res * a) % MOD;
      a = (a*a)%MOD;
      b = b >> 1; 
  }
  return res % MOD;
}



void solve(ll testnum)
{
    ll n;
    cin >> n;
    ll fr = 0, fb = 0;
    vpll pr;
    for(ll i=0;i<n;i++) {
    	string s;
    	cin >> s;
    	ll sum = 0;
    	ll low = 0;
    	for(ll j=0; j<s.size();j++) {
    		if(s[j] == '(') {
    			sum += 1;
    		} else if(s[j] == ')') {
    			sum -= 1;
    			low = min(low, sum);
    		}
    	}
    	if(low == 0) {
    		fr += sum;
    	} else if(low == sum) {
    		fb -= sum;
    	} else {
    		pr.pb(mp(sum, low));
    	}
    	// cout << low << " " << sum << "\n";
    }
    sort(all(pr));
    ll ans = fr;
    for(ll i=pr.size()-1;i>=0;i--) {
    	if(ans + pr[i].second < 0) {
    		cout << "No\n";
    		return;
    	}
    	ans += pr[i].ff;
    }
    ans -= fb;
    if(ans != 0) {
    	cout << "No\n";
    } else {
    	cout << "Yes\n";
    }
}

int main()
{
    FAST_IO;
    #ifdef STIO 
      freopen("input.txt" , "r", stdin);
      freopen("output.txt" , "w", stdout);
    #endif
    ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++) {
        solve(i);
    }
}

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = long long;
constexpr ll INF = (1LL<<60);
constexpr ll MOD = (1e9+7);
//constexpr ll MOD = (998244353);
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
inline void dump(){cout<<endl;}
template<class Head,class... Tail>inline void dump(Head&& head, Tail&&... tail){cout<<head<<", ";dump(forward<Tail>(tail)...);}
template<typename T>inline istream &operator>>(istream&input,vector<T>&v){for(auto &elemnt:v)input>>elemnt;return input;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}

main(){

  ll n,l;
  cin>>n>>l;
  vector<ll> a(n);
  cin>>a;

  ll cnt = -1;
  rep(i,n-1){
    if(a[i]+a[i+1]>=l)cnt = i+1;
  }
  if(cnt==-1){
    cout<<("Impossible")<<endl;
    return 0;
  }
  cout<<("Possible")<<endl;
  for(int i=1;i<cnt;++i)cout<<i<<endl;
  for(int i=n-1;i>cnt;--i)cout<<i<<endl;
  cout<<cnt<<endl;

}

Measured memory_bytes: 1664
import math

A, B, H, M = map(int, input().split())

theta = abs((H + M / 60 ) / 12 - M / 60) * 2 * math.pi
#if theta > math.pi: theta -= math.pi

ans = math.sqrt(A * A + B * B - 2 * A * B * math.cos(theta))

print(ans)


Measured memory_bytes: 9472
#include<bits/stdc++.h>
using namespace std;
main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long i,j,k,l,m,n,o,p,q;
 while(cin>>m>>n>>o){
   m-=n;
   cout<<m%o<<endl;
 }
    return 0;
}

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

map<char,int> dx = {{'L',0},{'R',0},{'U',-1},{'D',1}};
map<char,int> dy = {{'L',-1},{'R',1},{'U',0},{'D',0}};
const int maxn = 2e5+5;
int H, W, N;
string s, t;

bool valid(int x, int y) {
    return 1 <= x && x <= H && 1 <= y && y <= W;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> H >> W >> N;
    int x, y; cin >> x >> y;
    cin >> s >> t;
    bool poss = false;
    int cx = x, cy = y;
    //try left-up
    for (int i = 0; i < N; i++) {
        if (s[i] == 'L') cy--;
        else if (s[i] == 'U') cx--;
        if (poss || !valid(cx,cy)) {
            poss = true;
            break;
        }
        if (t[i] == 'R' && valid(cx,cy+1)) cy++;
        else if (t[i] == 'D' && valid(cx+1,cy)) cx++;
    }
    cx = x, cy = y;
    //try left-down
    for (int i = 0; i < N; i++) {
        if (s[i] == 'L') cy--;
        else if (s[i] == 'D') cx++;
        if (poss || !valid(cx,cy)) {
            poss = true;
            break;
        }
        if (t[i] == 'R' && valid(cx,cy+1)) cy++;
        else if (t[i] == 'U' && valid(cx-1,cy)) cx--;
    }
    cx = x, cy = y;
    //try right-up
    for (int i = 0; i < N; i++) {
        if (s[i] == 'R') cy++;
        else if (s[i] == 'U') cx--;
        if (poss || !valid(cx,cy)) {
            poss = true;
            break;
        }
        if (t[i] == 'L' && valid(cx,cy-1)) cy--;
        else if (t[i] == 'D' && valid(cx+1,cy)) cx++;
    }
    cx = x, cy = y;
    //try right-down
    for (int i = 0; i < N; i++) {
        if (s[i] == 'R') cy++;
        else if (s[i] == 'D') cx++;
        if (poss || !valid(cx,cy)) {
            poss = true;
            break;
        }
        if (t[i] == 'L' && valid(cx,cy-1)) cy--;
        else if (t[i] == 'U' && valid(cx-1,cy)) cx--;
    }

    cout << (poss ? "NO" : "YES") << '\n';
}



Measured memory_bytes: 920
#include<stdio.h>
int A,B,C,X[100][100],Y[100][100],i,j,k;
long long t;
int main()
{
    scanf("%d%d%d",&A,&B,&C);
    for(i=0;i<A;i++)
        for(j=0;j<B;j++)
            scanf("%d",&X[i][j]);
    for(i=0;i<B;i++)
        for(j=0;j<C;j++)
            scanf("%d",&Y[i][j]);
    for(i=0;i<A;i++)
    {
        for(j=0;j<C;j++)
        {
            for(k=t=0;k<B;k++)
                t+=X[i][k]*Y[k][j];
            printf("%lld%s",t,j==C-1?"\n":" ");
        }
    }
    return 0;
}


Measured memory_bytes: 2788
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>

typedef int32_t i32;
typedef int64_t i64;

const i32 mod = 1000000007;

#define ADD(x, a) do{(x) += (a); if ((x) >= mod) (x) -= mod;} while (0)

i32 mod_pow (i32 r, i32 n) {
  i32 t = 1;
  i32 s = r;
  while (n > 0) {
    if (n & 1) t = (i64) t * s % mod;
    s = (i64) s * s % mod;
    n >>= 1;
  }
  return t;
}

i32 inv (i32 a) {
  return mod_pow (a, mod - 2);
}

#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))

#define POS(i, j) (((i) & 1) * (n + 1) + (j))

void run (void) {
  i32 n;
  scanf ("%" SCNi32, &n);
  char *s = ALLOC (n + 1, char);
  scanf ("%s", s);
  i32 k = strlen (s);
  free (s);
  i32 *dp = ALLOC (2 * (n + 1), i32);
  dp[POS(0, 0)] = 1;
  for (i32 i = 1; i <= n; ++i) {
    memset (dp + POS(i, 0), 0, sizeof (i32) * (n + 1));
    ADD(dp[POS(i, 0)], dp[POS(i - 1, 0)]);
    ADD(dp[POS(i, 1)], dp[POS(i - 1, 0)]);
    ADD(dp[POS(i, 1)], dp[POS(i - 1, 0)]);
    for (i32 j = 1; j < i; ++j) {
      ADD(dp[POS(i, j - 1)], dp[POS(i - 1, j)]);
      ADD(dp[POS(i, j + 1)], dp[POS(i - 1, j)]);
      ADD(dp[POS(i, j + 1)], dp[POS(i - 1, j)]);
    }
  }
  i32 ans = (i64) dp[POS(n, k)] * mod_pow (inv (2), k) % mod;
  printf ("%" PRIi32 "\n", ans);
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 256
#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################
N, K = map(int,input().split())
#A = [0]*N
H = sorted(list(map(int,input().split())),reverse=True)	
if len(H)<=K:
    print("0")
else:
    del H[0:K]
    print(sum(H))
    
    





Measured memory_bytes: 88908
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            int N = in.nextInt();
            int M = in.nextInt();
            int X = in.nextInt();
            int[][] books = read(in, N, M + 1);
            int minCost = Integer.MAX_VALUE;
            for (int combination = 0; combination < 1 << N; combination++)
            {
                int knoweldge[] = new int[M];
                int cost = 0;
                for (int book = 1; book <= N; book++)
                {
                    boolean isTaken = CPUtils.getIthBitFromInt(combination, book) != 0;
                    for (int algo = 1; algo <= M && isTaken; algo++)
                    {
                        knoweldge[algo - 1] += books[book - 1][algo];
                    }
                    cost += isTaken ? books[book - 1][0] : 0;
                }
                if (Arrays.stream(knoweldge).filter(el -> el >= X).count() == M)
                {
                    minCost = Math.min(minCost, cost);
                }
            }
            out.println(minCost == Integer.MAX_VALUE ? -1 : minCost);
        }

        private int[][] read(Scanner in, int n, int m)
        {
            int[][] books = new int[n][m];
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    books[i][j] = in.nextInt();
                }
            }
            return books;
        }

    }

    static class CPUtils
    {
        public static int getIthBitFromInt(int bits, int i)
        {
            return (bits >> (i - 1)) & 1;
        }

    }
}



Measured memory_bytes: 35752
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;

int main (void) {
  int N;
  cin >>N;
  int ans_max=0;
  int ans_min=1000;
  for (int i; i<=N-1; i++){
    int j; cin >> j;
    ans_max=max(ans_max,j);
    ans_min=min(ans_min,j);
  }
  cout << ans_max-ans_min;
}

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

using namespace std;

int N;
double dp[301][301][301];
const double INF = 1145141919810;

double memo(int c1, int c2, int c3) {
	if (dp[c1][c2][c3] != INF)return dp[c1][c2][c3];

	double ret = 0.0;

	//最後に1/(c1+c2+c3)をかける

	//1つだけ残ってる皿の寿司を食べる
	if (c1 >= 1) {
		ret += ((double)c1) * memo(c1 - 1, c2, c3);
	}

	//2つだけ残ってる皿の寿司を食べる
	if (c2 >= 1) {
		ret += ((double)c2) * memo(c1 + 1, c2 - 1, c3);
	}

	//3つだけ残ってる皿の寿司を食べる
	if (c3 >= 1) {
		ret += ((double)c3) * memo(c1, c2 + 1, c3 - 1);
	}
	ret += (double)N;//取り除く操作自身
	if (c1 == c2 && c2 == c3 && c3 == 0)return 0.0;
	return dp[c1][c2][c3] = ret / (double)(c1 + c2 + c3);
}

int main() {
	cin >> N;
	int cnt3 = 0, cnt2 = 0, cnt1 = 0;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		if (a == 3)cnt3++;
		if (a == 2)cnt2++;
		if (a == 1)cnt1++;
	}

	for (int i = 0; i <= N; i++)for (int j = 0; j <= N; j++)for (int k = 0; k <= N; k++)dp[i][j][k] = INF;
	
	cout << setprecision(12) << memo(cnt1, cnt2, cnt3) << endl;
		
	return 0;
}

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

using namespace std;

int const MMM = 100005 , INF = INT_MAX;
int dp[MMM] , n , k;
int arr[MMM];
int calc(int a , int b)
{
    return abs(arr[b] - arr[a]);
}

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

    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> arr[i];
    }
    fill(dp , dp + n + 1 , INF);
    dp[1] = 0;
    dp[2] = calc(1 , 2);

    for(int i = 3 ; i <= n ; i++){
        for(int j = max(1 , i - k) ; j < i ; j++){
            dp[i] = min(dp[i] , dp[j] + calc(i , j));
        }
    }
    cout << dp[n];

    return 0;
}


Measured memory_bytes: 1024
import math

 

 
N,M = map(int,input().split())
S = input()
T = input()


def lcd(n,m):
    return int(n * m / gcd(n,m))
def gcd(n,m):
    if n % m == 0:
        return m
    else:
        return gcd(m,n % m)
#    return int(m*n/math.gcd(n,m))
    
def prove(n,m):
    n_i = int(n/gcd(n,m))
    m_i = int(m/gcd(n,m))
    n_list,m_list=[],[]
    for i in range(gcd(n,m)):
        n_list += S[i*n_i]
        m_list += T[i*m_i]
#    print(c)
#    print(pair[m])
    if n_list==m_list:
        return lcd(n,m)
    else:
        return -1


print(prove(N,M))



Measured memory_bytes: 3944
# -*- coding:utf-8 -*-
import sys


class Hash(object):
    def __init__(self, size):
        self._array = [None] * size
        self._size = size

    def _hash(self, key):
        return key % self._size

    def insert(self, key, value):
        j = self._hash(key)
        if self._array[j] is None:
            self._array[j] = [value]
        else:
            self._array[j].append(value)

    def find(self, key, value):
        j = self._hash(key)
        if self._array[j] is None:
            return False
        elif value in self._array[j]:
            return True
        else:
            return False


def stoi(s):
    ret = 0
    p = 1
    ctoi = {"A": 1, "C": 2, "G": 3, "T": 4}
    for c in s:
        ret += ctoi[c] * p
        p *= 7
    return ret


def dictionary(lst):
    h = Hash(1046527)
    ret = []
    for val in lst:
        if val[0] == "insert":
            h.insert(stoi(val[1]), val[1])
        elif val[0] == "find":
            if h.find(stoi(val[1]), val[1]):
                ret.append("yes")
            else:
                ret.append("no")
        else:
            raise ValueError
    return ret


if __name__ == "__main__":
    lst = [val.split() for val in sys.stdin.read().splitlines()]
    n = int(lst.pop(0)[0])
    print("\n".join(dictionary(lst)))

Measured memory_bytes: 380988
N = input()

def total(n):    
    t = 0
    for i in n:
        t += int(i)
    return t

if len(N) == 1:
    print(N)
else:
    if N[1:] == '9' * (len(N) - 1):
        print(total(N))
    else:
        print(total(str(int(N[0]) - 1) + '9' * (len(N) - 1)))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;

ll dp[110][4][4][4];

int main(int argc, char const *argv[]) {
    int n; cin >> n;
    memset(dp, 0, sizeof(dp));

    //長さ0の文字列は1つ
    dp[0][3][3][3] = 1ll;
    for (int m = 0; m < n; ++m) {
        //最後から1文字目の文字
        REP(i,4) {
            //最後から2文字目の文字
            REP(j,4) {
                //最後から3文字目の文字
                REP(k,4) {
                    //条件に当てはまらない場合はcontinue
                    if (dp[m][i][j][k] == 0) continue;
                    //新しく追加する文字
                    REP(l,4) {
                        if (l == 1 && i == 2 && j == 0) continue;
                        else if (l == 2) {
                            if (i == 0 && j == 1) continue;
                            else if (i == 1 && j == 0) continue;
                            else if (j == 1 && k == 0) continue;
                            else if (i == 1 && k == 0) continue;
                        }
                        dp[m+1][l][i][j] = (dp[m+1][l][i][j]+dp[m][i][j][k])%MOD;
                    }
                }
            }
        }
    }
    ll ans = 0ll;
    REP(i,4) {
        REP(j,4) {
            REP(k,4) {
                ans = (ans+dp[n][i][j][k])%MOD;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define int long long
#define p (int)(1e9 + 7)

int MOD(int a){
	a %= p;
	return a >= 0 ? a : a + p;
}

signed main(){
	int N, i;
	scanf("%lld", &N);
	char *S = (char *)malloc(sizeof(char) * (N + 1));
	scanf("%s", S);
	int num[26];
	for(i = 0; i < 26; i++){
		num[i] = 1;
	}
	for(i = 0; i < N; i++){
		num[(int)S[i] - (int)'a']++;
	}
	int ans = 1;
	for(i = 0; i < 26; i++){
		ans = MOD(ans * num[i]);
	}
	printf("%lld\n", MOD(ans - 1));
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  string s;
  cin >> N >> s;
  long long int r, g, b;
  r = 0, g = 0, b = 0;
  for (char ch : s)
  {
    if(ch=='R')
      r++;
    else if(ch=='G')
      g++;
    else if(ch=='B')
      b++;
  }
  long long int sum = r * g * b;
  for (int i = 0; i < N;i++){
    for (int k = i + 2; k < N;k+=2){
      int j = (i + k) / 2;
      if(s.at(i)+s.at(j)+s.at(k)=='R'+'G'+'B'){
        sum--;
      }
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 3648
#include <iostream>

using namespace std;

int main() {
    int k, s;
    int ans = 0;

    cin >> k >> s;

    for (int x=0; x<=k; x++) {
        for (int y=0; y<=k; y++) {
            int z = s-x-y;

            if(z>=0 && z<=k) {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){

int n;

scanf("%d",&n);

char s[n];

scanf("%s",&s);

int count=0;

for(int i=0;i<n-2;i++){
  if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C'){
    count++;
  }
}

printf("%d",count);

return 0;
}


Measured memory_bytes: 1712
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (lli i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

lli n, d, x;
vector<lli> a;
int main() {
  cin >> n >> d >> x; read_n(a, n);
  lli ans = x;
  for (lli i=0; i<n; ++i) {
    for (lli e=0; e<d; e+=a[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

  int ans = 0, a = 4, b = 7;
  for(int i = 0; i*a <= n; i++) {
    for(int j = 0; j*b <= n; j++) {
      if(i*a + j*b == n) {
        cout << "Yes";
        return 0;
      }
    }
  }
  cout <<"No";
}


Measured memory_bytes: 256
class String
  def to_ia
    self.split(/\s+/).map {|s| s.to_i}
  end
end
 
def is_prime(x)
  return true if x == 2
  return false if x < 2 or x % 2 == 0
  i = 3
  while i <= Math.sqrt(x).ceil
    return false if x % i == 0
    i += 2
  end
  true
end
 
lines = STDIN.read.split(/\n/)
numbers = lines[1..-1].map {|l| l.to_i}
puts numbers.select {|n| is_prime(n)}.size

Measured memory_bytes: 8980
#include <stdio.h>

int main(){
	int len1, len2, len3, ccount = 0, hcount = 0, hoge, hogehoge;
	while (scanf("%d%c%d%c%d", &len1, &hoge, &len2, &hogehoge, &len3) != EOF){
		if (len1*len1 + len2*len2 == len3*len3) ccount++;
		if (len1 == len2) hcount++;
	}
	printf("%d\n%d\n", ccount, hcount);
	return 0;
}

Measured memory_bytes: 596
a,v=map(int, input().split())
b,w=map(int, input().split())
t=int(input()) 

if a < b:
    if a + (v * t) >= b + (w * t):
        print('YES') 
    else:
        print('NO')
elif a > b:
    if a - (v * t) <= b - (w * t):
        print('YES') 
    else:
        print('NO')

Measured memory_bytes: 9132
#include<iostream>
using namespace std;
int main()
{
	int n,p[10000],d1[10000],d2[10000],bangou;
	while(1){
		int max=0;
		cin >> n;
		if(n==0)break;
		for(int i=0 ; i<n ; ++i){
			cin >> p[i] >> d1[i] >> d2[i];
		}
		for(int i=0 ; i<n ; ++i){
			if(max<d1[i]+d2[i]){
				max=d1[i]+d2[i];
				bangou=p[i];
			}
		}
		cout << bangou << " " << max << endl;
	}
	return 0;
}

Measured memory_bytes: 1276
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

int main(void)
{
    string S;
    cin >> S;

    int len = S.size();

    // 010101...
    string zeroone = "";
    // 101010...
    string onezero = "";

    for (int i = 0; i < len; i++)
    {
        if (i % 2 == 0)
        {
            zeroone += '0';
            onezero += '1';
        }
        else
        {
            zeroone += '1';
            onezero += '0';
        }
    }

    int diff1 = 0;
    int diff2 = 0;
    for (int i = 0; i < len; i++)
    {
        if (S[i] != zeroone[i])
        {
            diff1++;
        }

        if (S[i] != onezero[i])
        {
            diff2++;
        }
    }

    int ans = min(diff1, diff2);
    cout << ans << endl;
    return (0);
}

Measured memory_bytes: 768
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Long> a = new ArrayList<>();
        IntStream.range(0, n).forEach(i -> a.add(sc.nextLong()));


        Long plusMinusStep = 0L;
        Long minusPlusStep = 0L;
        Long plusMinusSum = 0L;
        Long minusPlusSum = 0L;
        for (int i = 0; i < n; i++) {
            Long target = a.get(i);
            if (i % 2 == 1) {
                if (plusMinusSum + target >= 0) {
                    plusMinusStep += Math.abs(plusMinusSum + target) + 1;
                    plusMinusSum = -1L;
                } else {
                    plusMinusSum += target;
                }
                if (minusPlusSum + target <= 0) {
                    minusPlusStep += Math.abs(minusPlusSum + target) + 1;
                    minusPlusSum = 1L;
                } else {
                    minusPlusSum += target;
                }
                continue;
            }
            if (plusMinusSum + target <= 0) {
                plusMinusStep += Math.abs(plusMinusSum + target) + 1;
                plusMinusSum = 1L;
            } else {
                plusMinusSum += target;
            }
            if (minusPlusSum + target >= 0) {
                minusPlusStep += Math.abs(minusPlusSum + target) + 1;
                minusPlusSum = -1L;
            } else {
                minusPlusSum += target;
            }
        }
        System.out.println(Math.min(plusMinusStep, minusPlusStep));
    }

}


Measured memory_bytes: 64932
from collections import Counter


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    A_dict = dict(Counter(A))
    A_sum = sum([i * j  for i, j in A_dict.items()])
    
    ans = []
    for i in range(Q):
        B, C = map(int, input().split())
        if not A_dict.get(B):
            ans.append(A_sum)
            continue
        diff = (C - B) * A_dict[B]
        A_sum += diff
        ans.append(A_sum)

        A_dict.setdefault(C, 0)
        A_dict[C] += A_dict[B]
        del A_dict[B]

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


if __name__ == '__main__':
    main()

Measured memory_bytes: 21388
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    for (int i=3; i<=n; i++)
    {
        if (i%3==0 || i%10==3 || (i/10)%10==3 || (i/100)%10==3 || (i/1000)%10==3) cout<<" "<<i;
    }
    cout<<'\n';
    return 0;
}




Measured memory_bytes: 3132
n = int(input())
ans = 0
i = 1

while i <= n:
    yakusuu = 0

    for j in range(1, i + 1):
        if i % j == 0:
            yakusuu = yakusuu + 1

    if yakusuu == 8:
        ans = ans + 1

    i = i + 2

print(ans)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define MOD 1000000007
#define ll long long int
#define db double
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define endl "\n"
#define mp make_pair
#define f first
#define se second
#define pi 3.14159265358979
//ll string_inp() {cin.get(); for(int i =0;i<n;i++){ getline(cin,s[i]);}}
ll gcd(ll a, ll b){ if (a == 0) return b;  return gcd(b % a, a);  }
ll power(ll x, ll y, ll mod = 2e18) {ll ans = 1;x %= mod;while(y){if(y&1) ans = (x * ans) % mod;x = (x * x) % mod;y >>= 1;}return ans;}
ll modInverse(ll a, ll m) { ll m0 = m; ll y = 0, x = 1; if (m == 1) return 0; while (a > 1) { ll q = a / m; ll t = m; m = a % m,a = t; t = y; y = x - q * y; x = t; } if(x < 0) x += m0;return x;}
int takemod(int a, int mod = MOD){a%=mod;if(a<0)a+=mod;return a;}
ll binsearch(std::vector<ll>& nums, ll target) {ll n = nums.size();ll l = 0;ll r = n-1;while(l<=r){ll mid = l+ (r-l)/2;if(nums[mid]==target)return mid;else if(nums[mid]>target)r = mid-1;else l = mid+1;}return -1;}
bool isPowerOfTwo (int x) {return x && (!(x&(x-1))); }

using namespace std;

int main()
{
   fastio
   ll animals,legs;
   cin>>animals>>legs;
   if(legs>=2*animals&&legs<=4*animals&&legs%2==0)
    cout<<"Yes"<<endl;
   else cout<<"No"<<endl;



}




Measured memory_bytes: 3624
#include<iostream>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  if(a==1 && b== 2)
    cout<<"3"<<endl;
  if(a==2 && b == 3) 
    cout<<"1"<<endl;
  if(a==3 && b==1)
    cout<<"2"<<endl;
  if(a==3 && b==2)
    cout<<"1"<<endl;
  if(a==2 && b==1)
    cout<<"3"<<endl;
  if(a==1 && b==3)
    cout<<"2"<<endl;
return 0;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C = []
for i in range(N):
    C.append(A[i]-B[i])

C.sort(reverse=True)

summed = 0
for i in C:
    if i > 0:
        summed += i
print(summed)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
using namespace std;
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 ll INF=(ll)1e9;
const ll MOD=(ll)1e9+7;
vector<int> dx={1,0,-1,0},dy={0,1,0,-1};
ll gcd(ll a,ll b){
  int x,r;
  x=a*b;
  if(a<b) swap(a,b);
  r=a%b;
  while(r){
    a=b;
    b=r;
    r=a%b;
  }
  return b;
}

int main(){
  ll N,a,ans=1;
  cin>>N;
  ll A[N];
  for(ll i=0;i<N;i++) cin>>A[i];
  a=A[0];
  for(ll i=1;i<N;i++){
    a=gcd(a,A[i]);
  }
  cout<<a<<endl;
}


Measured memory_bytes: 1024
N, M = map(int, input().split())  # N段の階段, 壊れている床の個数M

A = set([int(input()) for _ in range(M)])

dp = [0, 1]

for i in range(1, N+1):
    if i in A:
        dp.append(0)
    else:
        dp.append((dp[-2] + dp[-1]) % 1000000007)

print(dp[-1] % 1000000007)


Measured memory_bytes: 13216
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    char s[204];
    cin>>s;
    n=strlen(s);
    int k=0;
    for(int i=0;i<n;i++) if(s[i]=='o') k++;
    if(k+15-n>=8) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

}




Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, t;
    cin >> n >> t;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i].first >> a[i].second;
    sort(a.begin(), a.end());
    vector<int> dp(t);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, *max_element(dp.begin(), dp.end()) + a[i].second);
        for (int j = t - 1; j >= a[i].first; --j)
            dp[j] = max(dp[j], dp[j - a[i].first] + a[i].second);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>

using namespace std;

/*
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
*/

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

void solve() {
    ll h, w, n, r, c;
    cin >> h >> w >> n >> r >> c;
    string s, t;
    cin >> s >> t;
    bool ans = true;
    ll cur = r;
    for(ll i = 0; i < n; i++) {
        if(s[i] == 'U') cur--;
        if(cur == 0) ans = false;
        if(t[i] == 'D' && cur < h) cur++;
    }
    cur = r;
    for(ll i = 0; i < n; i++) {
        if(s[i] == 'D') cur++;
        if(cur == h + 1) ans = false;
        if(t[i] == 'U' && cur > 1) cur--;
    }
    cur = c;
    for(ll i = 0; i < n; i++) {
        if(s[i] == 'L') cur--;
        if(cur == 0) ans = false;
        if(t[i] == 'R' && cur < w) cur++;
    }
    cur = c;
    for(ll i = 0; i < n; i++) {
        if(s[i] == 'R') cur++;
        if(cur == w + 1) ans = false;
        if(t[i] == 'L' && cur > 1) cur--;
    }
    cout << (ans ? "YES" : "NO") << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}

Measured memory_bytes: 4000
using System;

public class Test{
  public static void Main(){
    
    //文字列の読み込み
    string str = System.Console.ReadLine();
    long x = Convert.ToInt64(str);

    long happy = 0;
    //500円玉の嬉しさ+5円玉の嬉しさ
    happy += (x / 500) * 1000 + ((x % 500) / 5) * 5;

   	System.Console.WriteLine(happy);
  }
}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
int n,m;
struct node{
	char s[230];
	int sc, id;
	bool operator < (node &A ) const{
		if (strcmp(s, A.s) != 0) return strcmp(s, A.s) < 0;
		return sc > A.sc;
	}
}f[N];

int main(){
	scanf("%d",&n);
	for (int i = 0; i < n; ++i)
		scanf("%s%d",f[i].s,&f[i].sc), f[i].id = i+1;
	sort(f,f+n);
	for (int i = 0; i < n; ++i)
		printf("%d\n",f[i].id);
	return 0;
}

Measured memory_bytes: 256
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0

using ll = long long;

const int INF = 1073741823;
const int MINF = -1073741823;
const ll LINF = ll(4661686018427387903);
const ll MOD = 1000000007;
const double PI = acos(-1);

using namespace std;

void scans(string& str) {
	char c;
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

/*-----------------------------------------ここからコード-----------------------------------------*/

int main() {

	int n;
	scanf("%d", &n);
	printf("%d\n", n * n);

	Please AC;
}


Measured memory_bytes: 888
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
 
	static String s;
	static int x;
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			s = sc.next();
			x = sc.nextInt();
 
			Set<String> set = new TreeSet<String>();
			for (int i = 0; i < s.length(); i++) {
				for (int j = 0; j < x; j++) {
					if (i + j + 1 <= s.length()) {
						set.add(s.substring(i, i + j + 1));
					}
				}
			}
			
			int count = 0;
			for (String str : set) {
				if (count + 1 == x) {
					System.out.println(str);
				}
				count++;
			}
		}
	}
}

Measured memory_bytes: 24404
n = input()
line = input()
a = line.split(" ")
a = [int(i) for i in a]
even_list = []

for i in range(len(a)):
    if a[i] % 2 == 0:
        even_list.append(a[i])
flag = 0
for num in even_list:
    if num % 3 == 0 or num % 5 == 0:
        flag = 0
    else:
        flag = 1
        break
if flag == 1:
    print("DENIED")
else:
    print("APPROVED")

Measured memory_bytes: 3064