Problem Background

Source: Sky City

In this context, "Oxen" refers exclusively to a type of monster in a game and is unrelated to the general meaning of "scalpers" or "ticket touts".

Legend has it that long, long ago, above the land of Melander, there floated a Sky City, which was the center of wealth, power, and honor. One day, it mysteriously disappeared.

Now, after centuries without a trace, Sky City has reappeared. Warriors from the kingdom have ventured to explore it, but obtaining a ticket for the airship is no easy task.

The captain of the airship dock, Medrong Dulufu, demands that everyone must buy a ticket to board the ship, and travelers without a ticket cannot embark.

Dzhuon Miao, the leader of a group of scalpers, has dispatched $q$ teams of scalpers to monopolize the tickets from Medrong Dulufu.

She sells these tickets at a high price, profiting greatly from the difference.

To maintain order at the airship dock, Medrong Dulufu has decreed that no fighting between humans and scalpers is allowed, although he has not prohibited fights among the scalpers themselves.

Problem Description

Dzhuon Miao's subordinates consist of two types of scalpers:

1. Type I scalpers have "attack" value $a$ and "health" value $A$.
2. Type II scalpers have "attack" value $b$ and "health" value $B$.

The battles between scalpers follow these rules:

1. At any time, if one side's "health" is $\leq 0$, their opponent wins.
2. Each round, the scalper with the higher "attack" value acts first.
3. Each side attacks once per round, dealing damage equal to their "attack" value.

The constructed Type III scalpers must meet the following conditions:

1. Their "attack" value is different from both Type I and Type II scalpers.
2. Type I scalpers lose to Type II scalpers in combat. (If the input does not satisfy this condition, output -1 -1 directly.)
3. Type II scalpers lose to Type III scalpers in combat.
4. Type III scalpers lose to Type I scalpers in combat.

Please provide a valid construction.

Simplified Problem Statement

Solve the equation: (If $x=\text{true}$, then $[x]=1$, otherwise $=0$)

$$\begin{aligned}\left\lceil\frac{A}{b}\right\rceil&+[b<a]\le\left\lceil\frac{B}{a}\right\rceil\\\left\lceil\frac{B}{c}\right\rceil&+[c<b]\le\left\lceil\frac{C}{b}\right\rceil\\\left\lceil\frac{C}{a}\right\rceil&+[a<c]\le\left\lceil\frac{A}{c}\right\rceil\\c&\ne a~\text{and}~c\ne b\end{aligned}$$

Given $a, A, b, B$, solve for $c, C$.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $q$.

The next $q$ lines each contain four positive integers $a, A, b, B$.

The data guarantees $a \ne b$.

Output Format

Output $q$ lines, each containing two positive integers representing the "attack" and "health" values of the constructed Type III scalpers. If there is no solution, output -1 -1.

This problem uses a Special Judge, and all valid solutions will be scored.

Sample Input and Output

Input Sample #1

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

Output Sample #1

4 1
1 5
2 3

Input Sample #2

4
14 1 10 15
14 1 10 15
14 1 10 15
14 1 10 15

Output Sample #2

11 11
11 12
11 13
11 14

Input Sample #3

1
1 1 999 999

Output Sample #3

-1 -1

Notes/Hints

Sample Explanation

For Sample #1, we can set A as $(1,5)$, B as $(2,3)$, and C as $(4,1)$.

The tuples $(x,y)$ represent a scalper with "attack" $x$ and "health" $y$.

The table below shows the combat scenarios for A, B, and C, with the numbers in parentheses indicating their "health" at the start of each round.

Thus, outputting any valid type of scalper will score points.

For Sample #2: Setting the Type III scalper's attack to $11$ is sufficient to defeat Type II scalpers, and any health value from $11$ to $14$ will result in losing to Type I scalpers.

Thus, any valid output will score points.

For Sample #3: Type II scalpers are too strong to construct a Type III scalper that can both defeat Type II scalpers and lose to Type I scalpers.

Thus, outputting -1 -1 will score points.

Data Size

Let $M=\max\left(a,A,b,B\right)$:

• Subtask1(10pts): $M\le10, q=3990$.
• Subtask2(20pts): $M\le100, q=3991$, data is random.
• Subtask3(10pts): $M\le10^5, q=992$, data is random.
• Subtask4(20pts): $M\le10^5, q=993$.
• Subtask5(10pts): $q=3994$, data is random.
• Subtask6(30pts): $q=3995$, no special restrictions.
• This problem has varying time limits based on data strength. If a reasonable full-score solution is challenged, please contact the problem setter.

Hint: The trailing digit of the number of data sets $q$ (e.g., $\underline0, \underline1, \underline2, \underline3, \underline4, \underline5$) may help you identify the type of Subtask.

For $100\%$ of the data: $1 \le q < 4000, 1 \le M \le 10^8$.

Large Sample Data

This problem provides test cases that meet the constraints of Subtasks $2, 3, 5$.

Compile and run the following code to obtain E01.in, E02.in, E03.in, which are test data that meet the constraints of Subtasks $2, 3, 5$ respectively.

#include<ctime>
#include<cstdio>
#include<random>
#include<string>
#include<cassert>
#include<cstdlib>
#include<iostream>
#define int long long
void print(int x){
    if (x < 0) x = -x, putchar('-');
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
void printsp(int x){
    print(x), putchar(' ');
}
void println(int x){
    print(x), putchar('\n');
}
char str[] = "E  .in";
const int Buff = 3989;
std::string string;
namespace Data_Maker{
    std::mt19937 rnd(time(0));
    int rand(int l, int r) {
        int x = r - l + 1;
        return (rnd() % x + x) % x + l;
    }
    int a, A, b, B;
    void maker(int subtaskID) {
        int t = Buff + subtaskID;
        if (3 <= subtaskID && subtaskID <= 4)
            t -= 3000;
        println(t);
        if (subtaskID == 2 || subtaskID == 3 || subtaskID == 5) {
            int MOD = 0;
            if (subtaskID == 2) MOD = 100;
            if (subtaskID == 3) MOD = 100000;
            if (subtaskID == 5) MOD = 100000000;
            while (t--) {
                a = rand(1, MOD), A = rand(1, MOD);
                b = rand(1, MOD), B = rand(1, MOD);
                while (b == a)
                    b = rand(1, MOD);
                printsp(a), printsp(A), printsp(b), println(B);
            }
        }
    }
    void File(int Test) {
        str[1] = Test / 10 + '0';
        str[2] = Test % 10 + '0';
        freopen(str, "w", stdout);
    }
    void Subtask2() {
        for (int Test = 1; Test <= 1; ++Test) {
            File(Test); maker(2);
        }
    }
    void Subtask3() {
        for (int Test = 2; Test <= 2; ++Test) {
            File(Test); maker(3);
        }
    }
    void Subtask5() {
        for (int Test = 3; Test <= 3; ++Test) {
            File(Test); maker(5);
        }
    }
}
using namespace Data_Maker;
signed main(){
    Subtask2();
    Subtask3();
    Subtask5();
}

Additionally, a Special Judge is provided, which can be compiled and invoked using spj E.in E.out E.ans to obtain feedback.

#include "testlib.h"
#define int long long
#define inf inf.readLong()
#define ouf ouf.readLong()
#define ans ans.readLong()
bool win(int a, int A, int b, int B){
  int x = 0, f = 1;
  if (a < b)
    a ^= b ^= a ^= b, A ^= B ^= A ^= B, f *= -1;
  while (1) {
    if (B - a <= 0) {
      x = 1;
      break;
    }
    if (A - b <= 0) {
      x = -1;
      break;
    }
    B -= a, A -= b;
  }
  x *= f;
  return x < 0;
}
signed main (signed argc, char**argv) {
  registerTestlibCmd(argc, argv);
  int q = inf;
  for (int t = 1; t <= q; ++t) {
    int a = inf, A = inf, b = inf, B = inf, c = ouf, C = ouf, d = ans, D = ans;
    if (d == -1 && c == -1 && C == -1)
      continue;
    if (c == a)
      quitf (_wa, "Test #%lld, a cannot equal to c!", t);
    if (c < 1 || C < 1)
      quitf (_wa, "Test #%lld, cannot print negative numbers!", t);
    if (!win(c, C, a, A))
      quitf (_wa, "Test #%lld, A cannot beat C!", t);
    if (!win(b, B, c, C))
      quitf (_wa, "Test #%lld, C cannot beat B!", t);
    if (!win(a, A, b, B))
      quitf (_wa, "Test #%lld, B cannot beat A!", t);
  }
  quitf (_ok, "Good job!");
}

The actual data generation method for this problem is included in the problem attachments. If you have stronger and more meaningful data, please propose it in the discussion area and mention the problem setter.

见题面 Input 部分

见题面 Output 部分