TLEoj Contest #11 - Tổng xor - TLEOJ: TLE Online Judge

TLEoj Contest #11 - Tổng xor

Điểm: 1600 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

xink

Dạng bài

Cho 2 số nguyên dương $n,k$ , nhiệm vụ của bạn là tính tổng $XOR$ của tất cả các số nguyên dương có giá trị nhỏ hơn $2^n$ mà có $k$ bit là $1$ .

Input, Output và Subtasks

Input:

Dòng đầu tiên chứa một số nguyên dương $t$ là số testcase $(1\le t\le 10^5)$ .
$t$ dòng tiếp theo, mỗi dòng gồm 2 số $n,k\ (1\le k\le n\le 10^{18})$ .

Output:

In ra $t$ dòng, mỗi dòng chứa phần dư của đáp án testcase thứ $i$ khi chia cho $119\times 2^{23}+1$ .

Scoring

Subtask $1$ $(10\%)$ : $1\le n\le 1000$ .
Subtask $2$ $(40\%)$ : $1\le n\le 10^6$ .
Subtask $3$ $(50\%)$ : Không giới hạn gì thêm.

Sample

Input

2
2 1
4 2

Output

3
15

Note

Trong testcase thứ nhất, các số thỏa mãn là $1,2$ nên kết quả là $1\oplus 2=3$ .
Trong testcase thứ hai, các số thỏa mãn là $3,5,6,9,10,12$ nên kết quả là $3\oplus 5\oplus 6\oplus 9\oplus 10\oplus 12=15$ .

Bình luận

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