canuc80k2901·2/50

Bộ Ba Chia Hết

Nộp bài trên LQDOJ

Bài 29 · Constructive Algorithms

Với hai số nguyên dương và , một số được gọi là loại nếu chia hết cho . Một số được gọi là loại II nếu chia hết cho nhưng không chia hết cho .

Hãy tìm ba số nguyên dương đôi một khác nhau x, y, z sao cho , đúng một trong ba số thuộc loại và hai số còn lại thuộc loại II. Nếu không tồn tại bộ ba như vậy, hãy thông báo.

Input

  • Dòng đầu chứa số nguyên - số bộ test.
  • Mỗi bộ test gồm một dòng chứa hai số nguyên và .

Output

  • Với mỗi bộ test, in NO nếu không tồn tại đáp án.
  • Ngược lại, in YES trên một dòng, rồi in ba số trên dòng kế tiếp. Mỗi số phải nằm trong đoạn từ đến . Chữ cái trong YES và NO có thể viết hoa hoặc viết thường.

Constraints

  • .
  • .

Scoring

  • Subtask ( số điểm): .
  • Subtask ( số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3
9 1
6 4
11 7

Output

NO
YES
24 18 42
YES
77 66 143

Giải thích: Khi , loại II không có phần tử nên bộ test đầu vô nghiệm. Trong hai bộ test còn lại, đúng một số chia hết cho , hai số kia chỉ chia hết cho , và hai số đầu cộng lại bằng số cuối.

Lời giải tóm tắt
  • Ý tưởng: Nếu B=1, mọi số chia hết cho A cũng chia hết cho A·B, nên loại II rỗng. Khi B>1, chọn x=A·B, y=A·(B-1) và z=A·(2B-1). Ta có x+y=z; x thuộc loại I, còn hệ số B-1 và 2B-1 đều không chia hết cho B, nên y,z thuộc loại II. Ba số dương, phân biệt và không vượt giới hạn.
  • Ý tưởng: Mỗi bộ test được xử lý trong O(1) thời gian và O(1) bộ nhớ.