Gym

A - Gaby And Addition

题意：给n个数，现在规定一个操作是不进位的加法，问两两操作的最小值和最大值。

思路：既然是不进位，那每个位之间就没有影响了。我们现在想要两两操作的值最大的话，就相当于找其他n-1个数，跟他们的前缀匹配一下，找出每一位能产生的最大值((cur+bit[i])%10的最大值)。这样就可以用字典树维护前面的数的前缀，每次只用匹配一下往最值方向走就行了。最小值同理。详见代码。

view code

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define endl '
'
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e6+200;
const ll inf=0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

ll n;
ll trie[13*maxn][10];
ll a[maxn];
ll pw[20];

int k = 1;

inline void insert(ll x)
{
    int p = 0;
    vector<int> tmp;
    rep(i,0,18) tmp.pb(x%10), x /= 10;
    per(i,18,0)
    {
        int ch = tmp[i];
        if(!trie[p][ch]) trie[p][ch] = k++;
        p = trie[p][ch];
    }
}

inline ll search(ll x, bool flag)
{
    int p = 0;
    vector<int> tmp;
    rep(i,0,18) tmp.pb(x%10), x /= 10;
    ll ans = 0;
    per(i,18,0)
    {
        int ch = tmp[i];
        if(flag)
        {
            int maxj = -1, cur = -1;
            per(j,9,0) if(trie[p][j]&&(ch + j)%10 > cur) cur = (ch+j)%10, maxj = j;
            p = trie[p][maxj], ans = ans + pw[i]*((ch + maxj) % 10);
        }
        else
        {
            int minj = -1, cur = 11;
            per(j,9,0) if(trie[p][j]&&(ch + j)%10 < cur) cur = (ch+j)%10, minj = j;
            p = trie[p][minj], ans = ans + pw[i]* ((ch + minj) % 10);
        }
    }
    return ans;
}

signed main()
{
    pw[0] = 1;  ll ans1 = inf, ans2 = 0;
    for(int i = 1; i <= 18; i++) pw[i] = pw[i-1] * 10;
    n = read();
    rep(i,1,n)
    {
        a[i] = read();
        if(i>1)
        ans1 = min(ans1,search(a[i],false)) ,ans2 = max(ans2, search(a[i],true));
        insert(a[i]);
    }
    cout<<ans1<<' '<<ans2<<'
';
    return 0;
}

B - Maximum Tree

题意：给n个数，随意排列，使得在a[k]代表树第k层的结点所含有的子树个数的前提下，树的结点个数最大值。

贪心，把子树个数多的放到靠近根的地方即可。

view code

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define endl '
'
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

ll a[maxn];

int main()
{
    ll n = read();
    rep(i,1,n) a[i] = read();
    sort(a+1,a+1+n);
    ll ans = 1;
    ll cur = 1;
    ll pre = 1;
    per(i,n,1)
    {
        cur = pre*a[i];
        ans += cur;
        pre = cur;
    }
    cout<<ans<<endl;
    return 0;
}

C - Planet Communcation

题意：问最少要多少条过原点的直线可以覆盖图中所有点。

思路：以第一个点作为原点，然后构建向量，化成最简，然后看向量种类有多少种即是答案。

view code

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define endl '
'
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

typedef struct Pos
{
    ll x;
    ll y;
    ll z;
  //  bool operator < (Pos a)const{return x<a.x;}
}P;

P a[maxn];


map<pair<PII,ll>,ll> cnt;

int main()
{
    ll n = read();
    a[1].x = read(), a[1].y = read(), a[1].z = read();
    rep(i,2,n)
    {
        a[i].x = read(), a[i].y = read(), a[i].z = read();
        a[i].x -= a[1].x, a[i].y -= a[1].y, a[i].z -= a[1].z;
        ll d = gcd(a[i].x, a[i].y);
        d = gcd(d, a[i].z);
        P tmp;
        tmp.x = a[i].x/d, tmp.y = a[i].y/d, tmp.z = a[i].z/d;
        cnt[mp(mp(tmp.x, tmp.y),tmp.z)]++;
    }
    cout<<cnt.size()<<endl;
    return 0;
}

D - Double it

题意：给一个操作A:x->2x+1, B:x->2x+2，一开始x为0，问到n的方案。

思路：正着推发现有难度。但是发现到A可以唯一确定答案为一个奇数，B可以唯一确定答案为偶数。所以如果n一开始是奇数，那么肯定上一步是A过来的，偶数的话就肯定是B过来的，然后继续往回推。最后倒序输出方案就完事了。

view code

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define endl '
'
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

int main()
{
    ll n;
    n = read();
    string s;
    while(n)
    {
        if(n&1) n--, n/=2, s += 'A';
        else n -= 2, n /= 2, s+= 'B';
    }
    per(i,s.size()-1,0) cout<<s[i]; cout<<endl;
    return 0;
}

E - Text Editor

题意：给一个主串t和模式串p，问在p的最长的且在t中出现次数超过k次的前缀。

思路：首先会想到KMP。但是如果直接拿模式串一位一位匹配是O(n²)的时间复杂度，肯定过不了。
我们发现模式串长度越长，越不容易满足要求。所以这里有个单调性，可以来二分。我们二分答案可能的长度，然后用这么长的前缀丢进KMP里面，看看能否满足，如果发现可以，就把长度调大一点，反之调小一点。时间复杂度O(nlogn)。
最后注意KMP用来计数时，每次匹配完不能直接j=0, i -= p.size()，因为这样会使得指针回溯使得算法退化。我们匹配完一个直接j = nxt[j]就行了（还是尽量选择前面最大匹配完的一部分接着匹配）。

view code

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define endl '
'
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

int nxt[maxn];

void getnext(string p)
{
    mem(nxt,0);
    nxt[0] = -1;        //第一位设为-1
    int i = 0, j = -1;   //i指针用来遍历数组， j相当于最大公共前后缀长度
    while(i<(int)p.size())
    {
        if(j==-1||p[i]==p[j]) i++, j++, nxt[i] = j;     //看看前后缀是否相等
        else j = nxt[j];        // 不行的话往前回溯
    }
}

int KMP(string t, string p)
{
    int i = 0, j = 0;
    getnext(p);
    int cnt = 0;
    while(i<t.size())
    {
        if(j==p.size())
        {
             cnt++;
             j = nxt[j];
        }
        if(j==-1||t[i]==p[j]) i++, j++;     //相等继续
        else j = nxt[j];        // 失配后找到nxt[j]的位置继续匹配。
    }
    if(j==p.size()) cnt++;
    return cnt;
}


int main()
{
    string t, p;
    int n;
    getline(cin,t);
    getline(cin,p);
    cin>>n;
    int L = 1 , R = p.size();
    string res = "-1";
    while(L<=R)
    {
        int mid = (L+R)>>1;
        string tmp(p,0, mid);
        if(KMP(t,tmp)>=n) res = tmp, L = mid + 1;
        else R = mid - 1;
    }
    if(res=="-1") cout<<"IMPOSSIBLE"<<endl;
    else cout<<res<<endl;
    return 0;
}

F - Polygon Triangles

题意：给你n个三角形，问你能不能够组成一个非退化四边形。

思路：发现其实是个三角形就能满足。。。

view code

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define endl '
'
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

typedef struct Pos
{
    ll x;
    ll y;
    ll z;
}P;

P a[maxn];


map<pair<PII,ll>,ll> cnt;

bool check(ll a, ll b, ll c)
{
    if(a+b>c&&a-b<c) return true;
    return false;
}

int main()
{
    ll n = read();
    bool flag = 1;
    rep(i,1,n)
    {
        ll b[5];
        b[1] = read(), b[2] = read(), b[3] = read();
        sort(b+1,b+1+3);
        a[i].x = b[1] , a[i].y = b[2], a[i].z = b[3];
        if(!check(a[i].x, b[2], b[3])) flag = 0;
        if(flag)
        cnt[mp(mp(a[i].x,a[i].y),a[i].z)]++;
    }
    if(flag) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

H - Logo

题意：输出指定规模的UN。

思路：水题模拟。

view code

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define endl '
'
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

ll a[maxn];

int main()
{
    ll n = read();
    cout<<"*";
    rep(i,1,n-2) cout<<' '; cout<<"* ";
    rep(i,1,n) cout<<"*"; cout<<endl;
    rep(i,1,n-2)
    {
        cout<<"*";
        rep(j,1,n-2) cout<<' ';
        cout<<"* ";

        cout<<"*";
        rep(j,1,n-2) cout<<' '; cout<<"*"; cout<<endl;
    }
    rep(i,1,n) cout<<"*";
    cout<<" *";
    rep(i,1,n-2) cout<<' '; cout<<"*";cout<<endl;
    return 0;
}

J - Jeronimo's List

题意：给出n个数，q个询问，每次问你第几个数是什么（从小到大） , n <= 1e7。

思路：直接sort肯定白给。我们可以用桶排序的思想，先预处理好这个完整的数组，然后把每个值映射到1e7的范围里，统计好个数，然后从头到尾走一遍，先遇到的就是靠前的。

view code

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define endl '
'
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 3e7+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 3e7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

ll a[maxn];
ll ans[maxn];
ll id[maxn];

int main()
{
   ll n = read(), m = read(), q = read();
   rep(i,1,m) a[i] = read();
   rep(i,m+1,n) a[i] = (a[i-m]+a[i-m+1])%mod;
   rep(i,1,n) ans[a[i]]++;
   ll cur = 1;
   int p = 0;
   rep(i,0,mod-1)
   {
       if(ans[i])
       {
           while(ans[i])
           id[++p] = i, cur ++, ans[i]--;
       }
   }
   rep(i,1,q)
   {
       ll x = read();
       cout<<id[x]<<endl;
   }
   return 0;
}