BÀI 2

Xem PDF

Điểm: 1900 (p) Thời gian: 0.5s Bộ nhớ: 940M Input: bàn phím Output: màn hình

Thành phố A nổi tiếng với nhiều danh lam thắng cảnh cũng như sự phát triển về công nghệ, để duy trì sự phồn thịnh của thành phố này, các công nhân cần làm việc vô cùng cật lực. Thành phố A hiện tại có vô hạn số công nhân, các công nhân được đánh số từ \(1\) đến \(+\infty\). Công nhân thứ \(i\) có chỉ số xây dựng là \(i\). Hiện tại thành phố cần thực hiện \(q\) công trình, mỗi công trình yêu cầu các công nhân từ \(l\) đến \(r\) hợp lực để xây dựng. Được biết, khi \(n\) công nhân cùng làm chung với nhau thì chỉ số hiệu quả của họ sẽ là tổng phép and chỉ số xây dựng của \(n\) công nhân. Là một người cầu toàn, SHIBA muốn chỉ số hiệu quả là lớn nhất bằng cách loại bỏ ra không quá \(k\) công nhân. Đây là công việc vô cùng khó khăn, vì thế bạn hãy giúp SHIBA hoàn thành nhé.

Lưu ý:

Input:

  • Dòng thứ nhất chứa \(1\) số nguyên dương \(q\) (\(1 \le q \le 10^4\)).
  • \(q\) dòng tiếp theo mỗi dòng chứa \(3\) số nguyên dương \(l,r,k\) (\(1 \le l \le r \le 10^6,1 \le k \le 10^2\)).

Output:

  • Gồm \(q\) dòng, mỗi dòng in ra chỉ số hiệu quả lớn nhất sau khi loại bỏ ra không quá \(k\) công nhân.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(1 \le l,r,k,q \le 10^2\)
  • Subtask \(2\) (\(80\%\) số điểm): \(1 \le l,r \le 10^6, 1 \le k \le 10^2,1 \le q \le 10^4\)

Example

Test 1

Input
2
1 3 1
4 8 1
Output
2
4
Note
  • Ở công trình đầu tiên ta loại công nhân thứ \(1\), tổng phép and là 2&3.
  • Ở công trình thứ \(2\) ta loại công nhân thứ \(8\), tổng phép and là 4&5&6&7.

Bình luận

Không có bình luận nào.