The Segment Game
There are N line segments [l1,r1], [l2,r2], ... , [ln,rn] lying on a Number line, each segment is distinguishable. Sagar designed a game for his friends Akash and Shivam, he asked them to pick a line segment from the Number line turn by turn. But then he put some contraints on the way the segments will be picked, the contraints are as follows :
- In the i th move a segment Sj can be picked if and only if it completely overlaps or lies completely inside the segment picked in i-1 th move.
Consider Segment Sk[lk,rk] was picked in i-1 th move then a segment Sj[lj,rj] can be picked in ith move if and only if lj >= lk and rj <= rk .
- The one who starts the game has the liberty of picking up any segment.
Shivam feels that the one who will start the game will always win the game, whereas Akash thinks the other way round. Sagar wants the game to be fair enough, So he lets Akash play first.
Sagar realizes that this game will take too much time, he wants to know who will win if both the players play optimally.
Since, you are a good programmer, Sagar asks for your help to determine the winner of the game.
Segment once picked can’t be picked again. xD
- The first line of the input contains an integer T denoting the number of Matches played by Akash and Shivam . The description of T matches follow :
- The first line of each Match contains a single integer N, denoting the number of segments N .
- N lines follow. For each i (1≤i≤N), the i-th of these lines contains two space-separated integers li and ri.
For each Match, output a single line containing Name of the Winner.
- If Akash wins the Match print “Akash”.
- If Shivam wins the Match print “Shivam” (without quotes).
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 10000
- -1000000000 ≤ li ≤ 1000000000
- -1000000000 ≤ ri ≤ 1000000000
- li < ri
1 3 -5 0 0 5 10 12 Output:
Akash can pick any of the segments, Shivam won’t be able to pick another segment as there aren’t any segment that lies completely inside other segment.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions