Page not loading? Try clicking here.
Placeholder

#8862
Subtask

Lineup Counting Queries 1s 1024MB

Problems

There is a line of cows, initially (i.e. at time t=0) containing only cow 0 at position 0 (here, a cow is at position k if there are k cows in front of it). At time t for t=1,2,3,…, the cow at position 0 moves to position ⌊t/2⌋, every cow in positions 1…⌊t/2⌋ moves forward one position, and cow t joins the line at the end of the line (position t).

Answer Q (1≤Q≤10^5) independent queries each of the following form:

Out of cows l_1…r_1, how many are located at positions l_2…r_2 immediately after time t? (0≤l_1≤r_1≤t, 0≤l2≤r2≤t, t≤10^{18})


Input

The first line contains Q, the number of queries.

The next Q lines each contain five integers specifying a query of the form "l_1 r_1 l_2 r_2 t."


Output

Output the answer to each query on a separate line.


Subtask

# Score Condition
#110

Q≤1000,t≤100

#220

l_1=r_1 for all queries

#330

r_1≤2⋅l_1 for all queries

#440

No additional constraints


Example #1

4
0 9 0 9 9
3 5 4 5 9
4 5 3 5 9
1 1 3 3 9
10
2
1
1

t = 0 | 0

t = 1 | 0 1

t = 2 | 1 0 2

t = 3 | 0 1 2 3

t = 4 | 1 2 0 3 4

t = 5 | 2 0 1 3 4 5

t = 6 | 0 1 3 2 4 5 6

t = 7 | 1 3 2 0 4 5 6 7

t = 8 | 3 2 0 4 1 5 6 7 8

t = 9 | 2 0 4 1 3 5 6 7 8 9

At t=9 the cows from front to back are [2,0,4,1,3,5,6,7,8,9].

To answer the third query, the cows at positions 3…5

are [1,3,5], and only one of them is in the range 4…5.


Example #2

1
0 1000000000000000000 0 1000000000000000000 1000000000000000000
1000000000000000001

Source

USACO 2026 First Contest, Platinum

You must sign in to write code.