题目背景

这是一道 hack 题。在此类型的题目中，你将得到若干个问题和若干个解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括：

1. 输出错误的结果。
2. 运行超时。
3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于每个问题，你需要提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。

---

提示：如果你使用提交答案功能，请在提交其他题目时记得将语言改回你所使用的语言

题目描述

以下给出三个问题的题目描述：

问题 1

给出两个正整数 $x, y$，保证它们的最小公倍数（$\mathrm{lcm}$）不大于 $10^9$。求它们的最小公倍数。

问题 2

多组数据，给定一个长度为 $n$ 的数组 $[a_1, a_2, \dots a_n]$，保证数组单调递增。有 $q$ 次询问，每次给出一个整数 $x$，求数组中有多少数小于等于 $x$。

问题 3

多组数据，给定一个长度为 $n$ 的数组 $[a_1, a_2, \dots a_n]$，有 $q$ 次询问，每次给出一个整数 $x$，求数组中有多少数小于等于 $x$。

注：问题 $2$ 和问题 $3$ 除了在是否保证数组递增上有差异外，在数据范围上也有区别，见下。

输入格式

问题 1

输入只有一行两个整数，依次表示 $x$ 和 $y$。

问题 2

第一行是一个整数 $T$，表示测试数据组数。
接下来按顺序给出每组数据的输入。
每组数据第一行是两个整数，依次表示数组 $a$ 的长度 $n$ 和询问次数 $q$。
每组数据第二行有 $n$ 个整数，依次表示 $a_1, a_2, \dots a_n$。
每组数据第三行有 $q$ 个整数，依次表示 $q$ 次询问给出的 $x$。

问题 3

第一行是一个整数 $T$，表示测试数据组数。
接下来按顺序给出每组数据的输入。
每组数据第一行是两个整数，依次表示数组 $a$ 的长度 $n$ 和询问次数 $q$。
每组数据第二行有 $n$ 个整数，依次表示 $a_1, a_2, \dots a_n$。
每组数据第三行有 $q$ 个整数，依次表示 $q$ 次询问给出的 $x$。

输出格式

问题 1

输出只有一行一个整数，表示两数的最小公倍数。

问题 2

对每组数据，输出一行 $q$ 个整数，依次表示每次询问的答案。

问题 3

对每组数据，输出一行 $q$ 个整数，依次表示每次询问的答案。

3 4

12

2
3 3
5 7 9
7 7 7
3 3
1 2 3
2 2 2

2 2 2 
2 2 2 

2
3 3
4 4 5
4 5 6
3 3
1 1 3
1 2 3

2 3 3
2 2 3

提示

样例组与实际输入的说明

三个样例分别对应三个问题的样例输入输出。

如果你直接采用『提交答案』的方式，请分别将三个输入数据命名为 1.in、2.in、3.in，并打成 zip 压缩包进行提交；

如果你采用提交数据生成器的方式，你的生成器可以从标准输入读入一个整数 $x$，满足 $1 \leq x \leq 3$，表示该测试点对应的问题编号，然后输出对应的输入数据。

显然，你的程序不应该读入『输入格式』里提到的任何内容（而应该构造它们），也不应该输出『样例输出』里提到的任何内容（而是只输出你构造的输入数据）。你不应该使用样例测试你的程序，这只是对三个问题的样例说明。

数据规模要求

你给出的数据必须满足如下要求：

1. 完全符合『输入格式』的规定，不能有多余的输入，但是可以有行末空格和文末回车。
2. 数据中所有的数字都应为整数。
3. 对于问题 1，$1 \leq x, y \leq 10^9$，且你必须保证两数的最小公倍数也不超过 $10^9$。
4. 对于问题 2，$1 \leq T \leq 3$，$1 \leq n,q \leq 10^5$，$1 \leq a_i, x \leq 10^9$。
5. 对于问题 3，$1 \leq T \leq 3$，$1 \leq n, q, a_i, x \leq 10^6$。

目标代码

你需要 hack 如下的代码：

问题 1

#include <iostream>
#include <algorithm>

int main() {
  int x, y;
  std::cin >> x >> y;
  int ans = x * y / std::__gcd(x, y);
  std::cout << ans << std::endl;
}

问题 2

#include <iostream>
#include <algorithm>

const int maxn = 1000003;

int T;
int n, q;
int a[maxn], b[maxn];

int find(int x) {
  int l = 1, r = n;
  int ans = 0;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (a[mid] <= x) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return ans;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  for (std::cin >> T; T; --T) {
    std::cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
      std::cin >> a[i];
    }
    for (int x; q; --q) {
      std::cin >> x;
      std::cout << find(x) << " ";
    }
    std::cout << std::endl;
  }
}

问题 3

#include <iostream>

const int maxn = 1000003;

int T;
int n, q;
int a[maxn], b[maxn];

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  for (std::cin >> T; T; --T) {
    std::cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
      std::cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
      b[a[i]]++;
    }
    for (int i = 1; i < maxn; ++i) b[i] += b[i - 1];
    for (int x; q; --q) {
      std::cin >> x;
      std::cout << b[x] << " \n"[q == 1];
    }
  }
}

目标代码的编译选项为 -std=c++14 -fno-asm -O2。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。

判分说明

本题共三个测试点，分别对应三个问题，每个问题 hack 成功则对应测试点返回 accepted。

数据判定

你给出的数据必须完全符合『数据规模要求』，否则将得到 Unaccepted 的结果。

超时判定

程序每执行若干条指令，我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量，也即每执行 $O(1)$ 条指令会进行一次检测。且两次检测之间的指令条数不会太多，一般不超过 $100$ 条 C++ 语句。

如果程序的运行时间超过 $500 \text{ms}$，则判定为程序运行超时，返回 accepted 结果。

结果错误判定

如果程序在规定的时间内结束且给出了一个输出，我们会比较这个输出和完全正确的输出，如果二者不同，则判定为 hack 成功，返回 accepted 结果。

未定义行为判定

我们会在每次显式的调用数组元素前判断数组下标是否超过数组范围，如果超过，则判定为 hack 成功，返回 accepted 结果。

这就是说，如果你希望通过未定义行为进行 hack，只能对显式的调用数组元素的行为进行 hack。

样例程序

这是一份可以帮你理解你需要输出的内容的样例程序，但它不能给出正确的 hack 数据。直接提交此程序不会得分。

#include <iostream>

using namespace std;

int main() {
  int taskId;
  cin >> taskId;
  if (taskId == 1) {
    cout << "" <<endl;
  } else if (taskId == 2) {
    cout << "" << endl;
  } else if (taskId == 3) {
    cout << "" << endl;
  } else { // 这个 else 不会被执行
    cout << "QiHai Nanami" << endl;
  }
}

如果你使用『提交答案』功能，请务必保证打开压缩包后能且仅能直接看到三个 .in 文件。这就是说，文件结构必须是：

ans.zip
 |---1.in
 |---2.in
 |---3.in

三个文件不应该被额外的文件夹包含，即文件结构不能是：

ans.zip
 |---ans(folder)
      |---1.in
      |---2.in
      |---3.in

关于评测信息的说明

如果 hack 成功，对应测试点的信息为 accepted。如果返回其他信息，说明程序本身有误。

例如，如果返回 TLE，不代表成功的将对应程序 hack 至超时，而是表示数据生成器本身运行超时，测试点不得分。

特别的，返回 UKE 结果可能是数据不合法（有多余内容、缺少内容或数据范围不符合要求）。