#include "stations.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "stub.cpp"
#endif
using ll = int;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
constexpr int max = 4000;
int ord = 0;
vi left(n, -1), right(n, -1);
vii edge(n);
rep(i,0,n-1){
edge[u[i]].pb(v[i]);
edge[v[i]].pb(u[i]);
}
vector<bool> flag(n);
std::function<void(int)> dfs = [&](int now){
left[now] = ord++;
for(auto next: edge[now]){
if(left[next] == -1){
flag[next] = !flag[now];
dfs(next);
}
}
right[now] = ord++;
};
dfs(0);
vi num(n);
rep(i,0,n){
if(flag[i]) num[i] = left[i]*2+1;
else num[i] = right[i]*2;
}
num[0] = max;
return num;
}
int find_next_station(int s, int t, std::vector<int> c) {
constexpr int max = 4000;
int lt = t/2, rt = t/2;
int ls, rs;
sort(all(c));
assert(c.size() > 0);
// right
if(s%2 == 0){
//cout << -1 << ln;
rs = s/2;
if(s == max){
rs = max;
ls = 0;
}
else{
if(c.size() == 1) ls = rs-1;
else ls = c[1]/2-1;
}
if(ls <= lt && rt <= rs){
int start = 1;
if(s == max) start = 0;
c.pb((rs+2)*2);
rep(i,start,c.size()-1){
int el = c[i];
int lc = el/2, rc = c[i+1]/2-2;
if(lc <= lt && rt <= rc) return el;
}
}
else{
return c[0];
}
}
// left
else{
//cout << -2 << ln;
ls = s/2;
reverse(all(c));
if(c.size() == 1) rs = ls+1;
else rs = c[1]/2+1;
if(ls <= lt && rt <= rs){
int start = 1;
c.pb((ls-1)*2);
rep(i,start,c.size()-1){
int el = c[i];
int lc = c[i+1]/2+1, rc = el/2;
if(lc <= ls && rs <= rc) continue;
if(lc <= lt && rt <= rc) return el;
}
}
else{
return c[0];
}
}
}
