出题人欲哭无泪：榜歪了...大佬们太多了，看到 A 就秒了，导致很多人觉得A也许是签到...

以为能过很多人的模拟（H 和 D） 也和我们原来的设想相距甚远。

题意叙述也存在很多歧义，这确实由于我们经验不足，思考不全面所引发的的过失，在这里为给大家造成的困扰和不愉快道歉。

还要澄清一下 K 题，数据好像出了一些问题，但是有人通过了，我们还要研究一下

本场出题人对于题目难度理解的排布如下：

easy：L，C

easy-mid：H，I

mid：B，D，M，G

mid-hard：E，F，J

hard：A，K

大部分题目还是更偏向思维，考察大家日常对于 trick 和经验的积累。

下面按照难度递增顺序依次给出题目详解：

L Where is zero?

签到题，不做详细说明。

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;

#define int long long
#define debug(x) cerr << #x" = " << x << '\n';

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

signed main()
{
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    int T = 1;
    while (T --) solve();
    return 0;
}

C 富有的国王

签到题

不需要建图，直接算就行。

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;

#define int long long
#define debug(x) cerr << #x" = " << x << '\n';

void solve()
{
    int n, m;
    cin >> n >> m;

    int t = m;
    while(t--) {
        int a, b;
        cin >> a >> b;
    }

    cout << n * (n - 1) - m << endl;
}

signed main()
{
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    int T = 1;
    while (T --) solve();
    return 0;
}

H 黑客帝国

纯模拟，考验代码组织能力，在此附上一种参考写法：

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

void solve()
{
	int n;
	cin >> n;
	vector<vector<int>> a(n + 2, vector<int>(n + 2));
	int mid;
	if (n & 1) mid = (n + 1) / 2;
	else mid = n / 2;
	int l = 1, num = 0, d = 0, x = mid, y = mid;
	a[x][y] = num++;
  
	while(num < n * n) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < l; j++) {
				if (num >= n * n) break;
				x += dx[d], y += dy[d];
				a[x][y] = num++;
			}
			d = (d + 1) % 4;
		}
		l++;
	}
  
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << a[i][j] << " \n"[j == n];
		}
	}
}  
  
signed main()
{
	cin.tie(nullptr) -> ios::sync_with_stdio(false);
	int T = 1;
	cin >> T;
	while (T --) solve();
	return 0;
}

I 二进制转化

一个很经典的 trick，简单来讲就是一个字符串中的 "01" 和 "10" 子串个数是否相同只取决于这个字符串开头和结尾的字符是否相同。

• 如果字符串本身开头和结尾的元素就是相同的，那么不需要做任何的转化，直接输出 "Yes"。

• 如果字符串自身开头和结尾的元素不相同，那么只需要检查转化的范围是否可以囊括开头或结尾的任意一个，如果囊括，只需要转化开头或结尾的字符使得两端相等即可；否则输出 "No"。

综上，只需要写一个简单的 if else 判断语句就可以了。

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;

#define int long long
#define debug(x) cerr << #x" = " << x << '\n';

const i64 N = 2e5 + 10, INF = 1e18 + 10;
const i64 mod = 998244353;

void solve()
{
    int n, l, r;
    string s;
    cin >> n >> s >> l >> r;

    if (s.front() == s.back()) {
        cout << "Yes" << endl;
        return;
    } else if (l == 1 || r == n) {
        cout << "Yes" << endl;
        return;
    }

    cout << "No" << endl;
    return;
}   

signed main()
{
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T --) solve();
    return 0;
}

B 代价转移

转换成图，建有向边 ，在 范围内跑一遍 Dijkstra 求最短路。

上界取 的原因：对于 ，，，，，最优路径是在 处 到达 再减 得到 。途中会越过 。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    ll a, b, c1, c2, c3;
    cin >> a >> b >> c1 >> c2 >> c3;

    if (a > b) {
        cout << (a - b) * c2 << '\n';
        return;
    }

    ll limit = max(a, b) * 2;

    vector<ll> dist(limit + 1, inf);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;

    dist[a] = 0;
    pq.emplace(0, a);

    while (!pq.empty()) {
        auto [curdist, u] = pq.top();
        pq.pop();

        // 到达终点
        if (u == b)
            break;

        if (curdist > dist[u])
            continue;

        // 三个邻接点、边权
        pair<ll, ll> adj[] = {
            {u + 1, c1},
            {u - 1, c2},
            {u * 2, c3},
        };

        for (auto [v, w] : adj) {
            ll newdist = curdist + w;
            if (newdist < dist[v] && 1 <= v && v <= limit) {
                dist[v] = newdist;
                pq.push({newdist, v});
            }
        }
    }

    cout << dist[b] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t = 1;
    cin >> t;
    while (t--)
        solve();
}

D 坐电梯

理清思路，逐秒模拟电梯运行过程即可。

因为收到的指令 ，所以可以用一个 64 位整数变量 作为待处理指令集合，它的每个二进制位保存是否存在去 楼的指令。例如，如果存在去 1 楼和 3 楼的待处理指令，，它右移 1 位或 3 位后，最低位一定是 。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int const Qmx = 1e4;

void solve() {
    int n, q;
    cin >> n >> q;

    // orders[i] 表示时刻 i 收到去 orders[i] 楼层的指令
    vector<int> orders(Qmx + 1);
    for (int i = 1; i <= n; ++i) {
        int ti, fi;
        cin >> ti >> fi;
        orders[ti] = fi;
    }

    // 电梯运行方向，向上为 1，向下为 -1，静止为 0
    int direction = 0;
    // 当前电梯位置
    int cur = 1;
    // 待处理指令集合，如果 (orderset >> i) == 1，表示存在去楼层 i 的指令
    ll orderset = 0;
    // ans[i] 表示时刻 i 电梯位置
    vector<int> ans(Qmx + 1);

    for (int t = 0; t <= Qmx; ++t) {
        ans[t] = cur;

        // 如果当前时刻有指令，加入 orderset
        if (orders[t] != 0 && orders[t] != cur)
            orderset |= (1LL << orders[t]);

        // 已经到达，删掉去当前楼层的指令
        orderset &= ~(1LL << cur);

        // 存在去比 cur 更高层的指令
        bool up = (orderset >> cur) > 0;
        // 存在去比 cur 更低层的指令
        bool down = ((1LL << cur) - 1) & orderset;

        // 电梯上行或静止
        if (direction >= 0) {
            // 上行时优先处理更高层指令，静止时先处理哪个都行
            if (up)
                direction = 1;
            else if (down)
                direction = -1;
            else
                direction = 0;
        } else {
            // 下行时优先处理更低层指令
            if (down)
                direction = -1;
            else if (up)
                direction = 1;
            else
                direction = 0;
        }

        // 改变当前电梯位置
        cur += direction;
    }

    for (int i = 1; i <= q; ++i) {
        int Q;
        cin >> Q;
        cout << ans[Q] << '\n';
    }
}

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

    int t = 1;
    cin >> t;
    while (t--)
        solve();
}

M 无聊的子序列

思维

暴力枚举长度为 1，2，3，4 的子数组即可。

我们可以通过打表的方式找到一些规律，即：不存在任何一个长度大于等于 5 的子数组满足题目中的限制条件，所以只需要暴力枚举就行了。

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;

#define int long long
#define debug(x) cerr << #x" = " << x << '\n';

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    if (n == 1) {
        cout << 1 << endl;
        return;
    } 

    int ans = n * 2 - 1;
    for (int i = 1; i <= n - 2; i++) {
        if (a[i] <= a[i + 1] && a[i + 1] <= a[i + 2]) continue;
        if (a[i] >= a[i + 1] && a[i + 1] >= a[i + 2]) continue;
        if (a[i] == a[i + 1] || a[i + 1] == a[i + 2]) continue;
        ans++;
    }
    for(int i = 1; i <= n-3; i++){
        if (a[i] > a[i + 1] && a[i] < a[i + 2] && a[i + 3] > a[i + 1] && a[i + 3] < a[i + 2]) ans++;
        if (a[i] < a[i + 1] && a[i] > a[i + 2] && a[i + 3] < a[i + 1] && a[i + 3] > a[i + 2]) ans++;
    }

    cout << ans << endl;
}   

signed main()
{
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    int T = 1;
    // cin >> T;
    while (T --) solve();
    return 0;
}

G 最大子段和，但是两段

经典 Kadane 算法，先正向跑一遍计算从 1 到 i 的最大连续子段和，再反向跑一遍计算从 n 到 i 的最大子段和。最后枚举两个子段的分割点，找到最大的两段之和就是答案。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 2);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<ll> dp1(n + 2), dp2(n + 2);
    // best1[i] 表示从位置 1 到 i 出现过的最大连续子段和
    // best2[i] 表示从位置 n 到 i 出现过的最大连续子段和
    vector<ll> best1(n + 2, LLONG_MIN), best2(n + 2, LLONG_MIN);
    for (int i = 1; i <= n; ++i) {
        // 作为新的子段起点或接续上一个子段
        dp1[i] = max(a[i], dp1[i - 1] + a[i]);
        best1[i] = max(best1[i - 1], dp1[i]);
    }
    for (int i = n; i >= 1; --i) {
        // 作为新的子段起点或接续上一个子段
        dp2[i] = max(a[i], dp2[i + 1] + a[i]);
        best2[i] = max(best2[i + 1], dp2[i]);
    }

    // 枚举分割位置，寻找最大值
    // 从 1 到 i-1 的最大子段和 + 从 i+1 到 n 的最大子段和
    ll ans = LLONG_MIN;
    for (int i = 2; i <= n; ++i)
        ans = max(ans, best1[i - 1] + best2[i]);
    cout << ans << '\n';
}

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

    int t = 1;
    cin >> t;
    while (t--)
        solve();
}

E 美好的每一天～不连续存在～

大致题意：求化成的形式以后 和 的值。

令，不难发现有。两边再同时平方，有：。由此我们考虑递推完整的关系。

设，则。由此：。

得到这样的关系以后，可以直接遍历更新得到所有对应的和。

(ps：出这道题的时候，出题人mh还考虑了只相差一次幂的系数关系，并惊奇地发现其系数恰好为斐波那契数列。其当时十分激动，以为自己发现了什么未被涉足的领域，后来查阅相关资料发现其并非第一个发现的，为斐波那契数与黄金比例的基本性质)。

#include<bits/stdc++.h>  
  
#define endl '\n'  
#define pii pair<int,int>  
  
#define int long long  
using namespace std;  
  
const int one = 1;  
const double eps = 1e-8;  
const int inf = 1e18;  
  
const int mod = 1e9 + 7;
  
void solve() {  
    vector<int> a(1e7 + 10), b(1e7 + 10);  
    a[0] = 1;  
    for (int i = 1; i <= 10000005; i++) {  
        a[i] = a[i - 1] * a[i - 1] % mod + 2 * b[i - 1] * a[i - 1] % mod;  
        a[i] %= mod;  
        b[i] = a[i - 1] * a[i - 1] % mod + b[i - 1] * b[i - 1] % mod;  
        b[i] %= mod;  
    }  
    int x;  
    cin >> x;  
    cout << a[x]<<" "<<b[x] << endl;  
}  
  
  
signed main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  
    int T = 1;  
    while (T--) solve();  
    return 0;  
}

F 希望与绝望

首先想一下什么时候会有解：

由于异或运算为非进位加法，其必然小于等于算术和，故必然要求，否则无解；除此之外，必须要求为偶数。

证明如下： 当 ，考虑整数 。根据恒等式：，移项可得：结果为偶数。 假设当 时命题成立，即：。我们需要证明 时也成立。记：。代入异或恒等式：。代入可得：

因此， 是偶数，得证。

现在考虑怎么构造。 显然，当的时候，只有才会有解，此时数组中元素即为，否则无解。 当的时候，令，即。对于二进制表示中某一位为的时候，必定为0，而中某一位为的时候，必定为。由此，我们针对的时候会引出一个新的条件：。如果不满足这个条件，依然无解。考虑。，并且由于，。故同时有，满足题意。 当的时候，我们可以直接添加一个和两个，其余全部填。

code

#include<bits/stdc++.h>  
  
#define endl '\n'  
#define pii pair<int,int>  
  
#define int long long  
using namespace std;  
  
const int one = 1;  
const double eps = 1e-8;  
const int inf = 1e18;  
  
const int mod = 1e9 + 7;  

void solve() {  
    int n, s, x;  
    cin >> n >> s >> x;  
    vector<int> a(n + 1);  
    if (s >= x && (s - x) % 2 == 0) {  
        int k = (s - x) / 2;  
        if (n == 1) {  
            if (x == s) cout << s << endl;  
            else cout << "zetsubou" << endl;  
        } else if (n == 2) {  
            if ((k & x) != 0) {  
                cout << "zetsubou" << endl;  
            } else cout << x + k << " " << k << endl;  
        } else {  
            cout << x << " " << k << " " << k << " ";  
            for (int i = 4; i <= n; i++) cout << 0 << " ";  
            cout << endl;  
        }  
    } else {  
        cout << "zetsubou" << endl;  
    }  
}
  
  
signed main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  
    int T = 1;  
    while (T--) solve();  
    return 0;  
}

J Shoegazing

（对不起，因为我的疏忽导致此题题面数据有误，k）

针对分音符为一拍，分音符则有拍。我们需要判断是否等于。由于读入的音符可能为分音符，拍值极小，超出double精度，不能直接用小数判断。而整数部分最多只有拍，粗略估算，假如全是全音符，大概有个拍，远小于long long精度范围。

故可以这么考虑：针对整数部分，通过加法直接求和；而对于小数部分，个可以转换成个以及个。通过往高次递推可以精确地对小数部分计算，最终求和。

#include<bits/stdc++.h>  
  
#define endl '\n'  
#define pii pair<int,int>  
  
#define int long long  
using namespace std;  
  
const int one = 1;  
const double eps = 1e-8;  
const int inf = 1e18;  
  
const int mod = 1e9 + 7;  
  
void solve() {  
    int a, b;  
    cin >> a >> b;  
    string str;  
    cin >> str;  
    int k = -1;  
    int temp = b;  
    while (temp) {  
        k++, temp >>= 1;  
    }  
    //b为2的k次幂  
    map<string, int> mp;  
    map<int, int> cnt;  //代表2的()次幂拍
  
    mp["x---"] = k, mp["x-"] = k - 1;  
    int pre = 0;  
    for (int i = 0; i < str.size(); i++) {  
        if (i == 0) continue;  
        else {  
            if (str[i] == 'x') {  
                string sub = str.substr(pre, i - pre);  
                if (mp.count(sub)) {  
                    cnt[mp[sub]]++;  
                } else {  
                    int len = i - pre - 1;  
                    cnt[k - len - 2]++;  
                }  
                pre = i;  
            } else continue;  
        }  
    }  
  
    string sub = str.substr(pre);  
    if (mp.count(sub)) {  
        cnt[mp[sub]]++;  
    } else {  
        int len = sub.size() - 1;  
        cnt[k - len - 2]++;  
    }  
  
    int sum = 0;  
    for (auto it: cnt) {  
        int l = it.first, r = it.second;  
        if (l < 0 && r % 2 == 1) {  
            cout << "ITS MY OWN INVENTION" << endl;  
            return;//由于a为整数，故不能出现小数部分  
        } else {  
            if (l < 0)cnt[l + 1] += r / 2;  
            else {  
                sum += (1ll << l) * r;  
            }  
        }  
    }  
  
    if (sum == a) cout << "LIVE HAPPILY" << endl;  
    else cout << "ITS MY OWN INVENTION" << endl;  
}  
  
  
signed main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  
    int T = 1;  
    while (T--) solve();  
    return 0;  
}

A 隔板

递推，DP，组合数学

不知道有多少人被这个 题目 和 人畜无害的题面 给骗到了，虽然是一道很经典的板子题，但是涉及到的数学知识还是很难的，之前没有见过的这类问题的萌新很难在第一次想出来正解......

先说结论，隔板法是不行的，因为会有重复。

其结果相当于 “第二类斯特林数” 乘以 。

代码中二维数组 f[i][j] 表示将 i 个球分到 j 个盒子的合法方案数，初始化 f[0][0] = 1，其它 f[0][j] = 0

然后对于每个新球第 i 个，可以放入已有的 j 个盒子中（对应 f[i−1][j] 种情况，每种再乘以 j 种选择）

或者放入一个新盒子（对应 f[i−1][j−1] 种情况，同样再乘以 j 表示在 m 个盒子中选定一个作为“新盒子”）

合并后便得到转移 f[i][j] = j * (f[i−1][j] + f[i−1][j−1]) % mod，输出 f[n][m] 即可，时间和空间复杂度均为 O(nm)。

以下为参考代码：

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;

#define int long long
#define debug(x) cerr << #x" = " << x << '\n';

const i64 mod = 998244353;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> f(n + 1, vector<int>(m + 1));
	f[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			f[i][j] = j * (f[i - 1][j] % mod + f[i - 1][j - 1] % mod) % mod;
		}
	}
	cout << f[n][m] % mod << endl;
}

signed main()
{
	cin.tie(nullptr) -> ios::sync_with_stdio(false);
	int T = 1;
	// cin >> T;
	while (T --) solve();
	return 0;
}

K 农场里的欧几里得

计算几何，思维

首先，要知道 "核" 的概念：对于一多边形，其内部可能存在一片区域（也可能不存在），使得在该区域内的点可以 "看" 到多边形内部的任意边.

写成数学语言就是，对于简单多边形 P 内部一定区域中如果存在一个点 p（不一定是顶点，也可以在边上或内部），使得对于多边形内任意一点 q ∈ P，线段 pq 都完全落在 P 内部，那么这片区域就被称作多边形的 "核"。

我们可以发现星形图形的核，就是由 “凹”进去的点所形成的凸包。

显然，我们在这个区域内的任意一点都满足题目中所述的条件，可以直接取 min；

另外可以注意到，假设我们选中了一个摄像头位于一个角的区域中，以下图举例（K 深色区域为核），假设我们选中了除了核以外的 区域A 中的一个点，我们可以发现，只有区域G，B中的部分面积覆盖不到，则我们可以选择另外某个区域中一个点，也就是除了 F，C，A 区域外的任意区域内的任意一点，就可以覆盖多边形的全部部分。

贪心思路如上，剩下的就是暴力枚举每个区域，以及点在某个区域内的判断，都是板子内容，下面贴上参考代码。

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;

#define int long long
#define debug(x) cerr << #x" = " << x << '\n';

typedef pair<int, int> PII;

const i64 N = 2e5 + 10, INF = 1e18 + 10;
const i64 mod = 998244353;

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

const long double PI = acos(-1);
const long double eps = 1e-10;
int sign(long double x) {
    if (fabsl(x) < eps) return 0;
    else return x > 0 ? 1 : -1;
}
int sign(long double x, long double y) {
    if (fabsl(x - y) < eps) return 0;
    else return x > y ? 1 : -1;
}

struct Vector {
    long double x, y;
    Vector(long double x_ = INF, long double y_ = INF): x(x_), y(y_) { }
    Vector operator+ (Vector t) const { return Vector(x + t.x, y + t.y); }
    Vector operator- (Vector t) const { return Vector(x - t.x, y - t.y); }
    Vector operator* (long double t) const { return Vector(x * t, y * t); }
    Vector operator/ (long double t) const { return Vector(x / t, y / t); }
    Vector operator+= (Vector t) { return *this + t; };
    Vector operator-= (Vector t) { return *this - t; };
    Vector operator*= (long double t) const { return *this * t; }
    Vector operator/= (long double t) const { return *this / t; }
    long double square() { return *this * *this; }
    long double length() { return sqrtl(square()); }
    // |a| * |b| * sin(th)
    long double operator^ (Vector t) const { return x * t.y - y * t.x; }
    // |a| * |b| * cos(th)
    long double operator* (Vector t) const { return x * t.x + y * t.y; }
    bool operator==(const Vector &t) const { return sign(x, t.x) == 0 && sign(y, t.y) == 0; }
    bool operator!=(const Vector &t) const { return !(*this == t); }
    bool operator< (const Vector& t) const { return sign(x, t.x) == 0 ? y < t.y : x < t.x; }
    friend ostream &operator<< (ostream &out, const Vector p) { return out << '(' << p.x << ", " << p.y << ')'; }
    void read() { cin >> x >> y; }
};
using Point = Vector;
// 求向量A，B夹角
long double Angle(Vector A, Vector B) {
    A = A / A.length(), B = B / B.length();
    return acos(min<long double>(max<long double>(A * B, -1), +1));
}
// 三角形面积 = ×积
long double area(Point A, Point B, Point C) {
    return ((B - A) ^ (C - A));
}
// 距离
long double dist(const Point A, const Point B) {
    long double dx = A.x - B.x, dy = A.y - B.y;
    return sqrtl(dx * dx + dy * dy);
}
// true：A 在 B 的左边
bool leftTest(Vector A, Vector B) { 
    return (B ^ A) > 0;
}
// 逆时针旋转 rad°
inline Vector rotate(Vector A, double rad) {
    return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
// 法向量
Vector normalVector(Vector A) {
    return Vector(-A.y, A.x);
}
// int sgn(Point a) {   // 上半平面或者x的正方向 / 下半平面或者x轴的负方向
//     return a.y > 0 || (a.y == 0 && a.x > 0) ? 1 : -1;
// }

struct Line {
    Point a, b;   // 起点 终点
    Point s; Vector v;
    long double deg;
    
    Line() = default;
    Line(Point a, Point b) :s(a), v(b - a), a(a), b(b) { deg = atan2(v.y, v.x); }
};

// true：p 在直线 l 的左侧；
// false：否则（在右侧或共线）
bool pointOnLineLeft(Point p, Line l) {
    return sign((l.v) ^ (p - l.s)) > 0;
}

// true ⇒ p 在线段 ab 上，含端点
bool pointOnSegment(Point p, Line l) {
    return sign((p - l.a) ^ (l.v)) == 0 
        && sign((l.a - p) * (l.b - p)) <= 0;
}

// p 在直线 l 上的投影
Vector project(Point p, Line l) {
    long double r = ((p - l.a) * l.v) / l.v.square();
    return l.a + l.v * r;
}

// p 到直线 l 的垂足
Point footPoint(Point p, Line l) {
    return project(p, l);
}

// p 关于直线 l 的对称点
Point reflection(const Point &p, const Line &l) {
    Point H = footPoint(p, l);
    return H * 2 - p;  // H + (H - p)
}

// l1 与 l2 的交点
Point intersection(const Line &l1, const Line &l2) {
    long double denom = l1.v ^ l2.v;
    // 平行?
    if (sign(denom) == 0) return Point();
    long double t = ((l2.s - l1.s) ^ l2.v) / denom;
    return l1.s + l1.v * t;
}

// seg1 与 seg2 的交点
Point segIntersection(const Line &seg1, const Line &seg2) {
    Point x = intersection(seg1, seg2);
    if (pointOnSegment(x, seg1) && pointOnSegment(x, seg2)) return x;
    return Point();
}

// 判断两线段是否相交（包含端点）
// **只判断严格相交**，就把整个 if(...) {...} 块注释掉。
bool isSegmentIntersect(const Line &seg1, const Line &seg2) {
    Point A = seg1.a, B = seg1.b, C = seg2.a, D = seg2. b;
    long double c1 = (B - A) ^ (C - A);
    long double c2 = (B - A) ^ (D - A);
    long double c3 = (D - C) ^ (A - C);
    long double c4 = (D - C) ^ (B - C);
    if (sign(c1) == 0 && pointOnSegment(C, Line(A, B))) return true;
    if (sign(c2) == 0 && pointOnSegment(D, Line(A, B))) return true;
    if (sign(c3) == 0 && pointOnSegment(A, Line(C, D))) return true;
    if (sign(c4) == 0 && pointOnSegment(B, Line(C, D))) return true;

    // 严格相交：两端异侧
    return sign(c1) * sign(c2) < 0 && sign(c3) * sign(c4) < 0;
}

// * —— 更复杂的版本 —— * 

// 返回值类型：
//  0 — 不相交（no intersection）
//  1 — 严格相交（相交于两段内部，非端点）
//  2 — 重叠（共线且有区间重叠）
//  3 — 端点相交（只在端点处相交）

// 返回值元组：(type, P1, P2)
//   当 type==0 时，P1、P2 无意义（默认构造点）
//   当 type==1 或 3 时，P1==P2==交点
//   当 type==2 时，P1,P2 分别是重叠区间的两个端点

std::tuple<int, Point, Point> isSegmentIntersection(Line l1, Line l2) {
    using std::max; using std::min; using std::swap;

    // —— 1. 包围盒快速排除 —— 
    if (max(l1.a.x, l1.b.x) < min(l2.a.x, l2.b.x) ||
        min(l1.a.x, l1.b.x) > max(l2.a.x, l2.b.x) ||
        max(l1.a.y, l1.b.y) < min(l2.a.y, l2.b.y) ||
        min(l1.a.y, l1.b.y) > max(l2.a.y, l2.b.y)) {
        return {0, Point(), Point()};
    }
    // —— 2. 共线情况 —— 
    if (sign((l1.b - l1.a) ^ (l2.b - l2.a)) == 0) {
        // 不在同一直线
        if (sign((l1.b - l1.a) ^ (l2.a - l1.a)) != 0) {
            return {0, Point(), Point()};
        }
        // 共线，找投影重叠区间
        auto mn1x = min(l1.a.x, l1.b.x), mx1x = max(l1.a.x, l1.b.x);
        auto mn1y = min(l1.a.y, l1.b.y), mx1y = max(l1.a.y, l1.b.y);
        auto mn2x = min(l2.a.x, l2.b.x), mx2x = max(l2.a.x, l2.b.x);
        auto mn2y = min(l2.a.y, l2.b.y), mx2y = max(l2.a.y, l2.b.y);
        Point p1{ max(mn1x, mn2x), max(mn1y, mn2y) };
        Point p2{ min(mx1x, mx2x), min(mx1y, mx2y) };
        // 如果 p1 不在线段 l1 上，则 p1/p2 顺序反了，交换整个点
        if (!pointOnSegment(p1, l1)) {
            swap(p1, p2);
        }
        // 退化成单点
        if (p1 == p2) {
            return {3, p1, p2};
        } else {
            return {2, p1, p2};
        }
    }
    // —— 3. 异面相交排除 —— 
    long double cp1 = (l2.a - l1.a) ^ (l2.b - l1.a);
    long double cp2 = (l2.a - l1.b) ^ (l2.b - l1.b);
    long double cp3 = (l1.a - l2.a) ^ (l1.b - l2.a);
    long double cp4 = (l1.a - l2.b) ^ (l1.b - l2.b);
    // 如果两端都在同侧，则无交
    if (sign(cp1) * sign(cp2) > 0 || sign(cp3) * sign(cp4) > 0) {
        return {0, Point(), Point()};
    }
    // —— 4. 计算交点，并区分类型 —— 
    Point p = intersection(l1, l2);
    // 四个叉积都非零 ⇒ 严格相交
    if (sign(cp1) != 0 && sign(cp2) != 0 && sign(cp3) != 0 && sign(cp4) != 0) {
        return {1, p, p};
    } 
    // 否则 ⇒ 至少有端点接触
    else {
        return {3, p, p};
    }
}

// p 到直线 l 的距离
long double distancePointToLine(const Point &p, Line &l) {
    return fabsl((p - l.a) ^ l.v) / (l.v.length());
}

// p 到线段 seg 的距离
long double distancePointToSegment(const Point &p, Line &l) {
    if (l.a == l.b) return (p - l.a).length();

    Vector v = l.b - l.a;
    Vector u1 = p - l.a;
    Vector u2 = p - l.b;
    // 投影点在线段延长线上，则取端点距离
    if (sign(v * u1) < 0) return u1.length();
    if (sign(v * u2) > 0) return u2.length();
    return distancePointToLine(p, l);
}

// 线段 s1 到线段 s2 的最短距离
long double distanceSegmentToSegment(Line &s1, Line &s2) {
    if (isSegmentIntersect(s1, s2)) return 0.0L;
    return min({
        distancePointToSegment(s1.a, s2),
        distancePointToSegment(s1.b, s2),
        distancePointToSegment(s2.a, s1),
        distancePointToSegment(s2.b, s1)
    });
}

struct Polygon: vector<Point> {
    Polygon(initializer_list<Point> arg): vector<Point>(arg) {}
    template<typename... argT>
    explicit Polygon(argT &&...args): vector<Point>(forward<argT>(args)...) { }

    long double area() const {
        int n = size();
        if (n < 3) return 0;
        long double ans = 0;
        for (int i = 0; i < n; i++) 
            ans += (*this)[i] ^ (*this)[(i + 1) % n];
        return fabsl(ans) / (long double)2.00;
    }

    bool isConvex() const {
        int n = size();
        if (n < 3) return false;
        long double th = 0;
        for (int i = 0; i < n; i++) {
            int j = (i + 1) % n, k = (i + 2) % n;
            // 如果保证严格就去掉注释（是否存在三点共线）
            // if (sign(((*this)[j] - (*this)[i]) ^ ((*this)[k] - (*this)[j])) == 0) return 0;
            th += Angle(((*this)[j] - (*this)[i]), ((*this)[k] - (*this)[j]));
        }
        return sign(th - 2 * PI) == 0;
    }

    // 0 - 不在里面
    // 1 - 严格在里面
    // 2 - 在边上
    int inPolygon(Point &p) {
        bool f = 0;
        int n = size();
        Point p1, p2;
        for (int i = 0, j = n - 1; i < n; j = i++) {
            p1 = (*this)[i]; p2 = (*this)[j];
            if (pointOnSegment(p, Line(p1, p2))) return 1;
            //前一个判断 min(P1.y,P2.y) < P.y <= max(P1.y,P2.y)
            //后一个判断被测点 在 射线与边交点 的左边
            if ((sign(p1.y - p.y) > 0 != sign(p2.y - p.y) > 0) && 
                sign(p.x - (p.y - p1.y) * (p1.x - p2.x) / (p1.y - p2.y) - p1.x) < 0) {
                f = !f;
            }
        }
        if (f) return 2;
        else return 0;
    }
};

void solve()
{
    int n, m;
    cin >> n >> m;
    Polygon P(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        cin >> P[i].x >> P[i].y;
    }

    int idx = pointOnLineLeft(P[1], Line(P[0], P[2])) ? 0 : 1;
    vector<pair<Point, int>> in;
    Polygon ch;
    vector<Polygon> a;
    for (int i = (idx == 1) ? 0 : 1; i < 2 * n; i += 2) ch.push_back(P[i]);
    for (int i = idx; i < 2 * n; i += 2) {
        a.emplace_back( Polygon{ P[i],
            P[(i + 1) % P.size()],
            P[(i - 1 + P.size()) % P.size()] } );
    }

    int ans = INF;
    vector<int> regionIn(n, INF);
    while(m--) {
        Point p;
        int c;
        cin >> p.x >> p.y >> c;
        if (P.inPolygon(p) == 2) in.push_back({p, c});
        else {
        cout << (ans >= INF / 2 ? -1 : ans) << endl;
            continue;
        }

        if (ch.inPolygon(p) > 0) {
            ans = min(ans, c);
            cout << (ans >= INF / 2 ? -1 : ans) << endl;
            continue;
        }
        int id = -1;
        for (int i = 0; i < n; i++) {
            if (a[i].inPolygon(p) > 0) {
                regionIn[i] = min(regionIn[i], c);
                id = i;
                break;
            }
        }

        regionIn[id] = min(regionIn[id], c);
        int res = INF;
        for (int j = 0; j < n; j++) {
            if (j == ((id - 1) + n) % n || j == (id + 1) % n || j == id) continue;
            res = min(res, regionIn[id] + regionIn[j]);
        }   
        ans = min(ans, res);
        cout << (ans >= INF / 2 ? -1 : ans) << endl;
    }
}

signed main()
{
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    int T = 1;
    // cin >> T;
    while (T --) solve();
    return 0;
}