弹飞绵羊2

题目描述

有 \(n\) 个位置，形如 \(1,2,...,n\)。

有 \(m\) 只绵羊，第 \(i\) 只羊在位置 \(b_i\)。

如果一只绵羊在位置 \(i\)，则它会被弹到位置 \(a_i\)。特别的，如果 \(a_i = 0\)，则绵羊会直接弹飞。

由于绵羊很重，所以第 \(i\) 只绵羊最多只会弹 \(c_i\) 次。

请判断绵羊是否弹飞，或者判断此时绵羊的位置。

输入格式

第一行两个整数 \(n,m\) 表示位置数和绵羊数。

随后 \(n\) 个整数 \(a_i\)，如果绵羊在位置 \(i\)，则它会弹到位置 \(a_i\)。

随后有 \(m\) 行，每行两个整数 \(b_i\) 和 \(c_i\) 表示第 \(i\) 只绵羊初始的位置和最多会弹的次数。

输出格式

对于每只绵羊，如果绵羊在前 \(c_i\) 次会被弹飞，输出 Loser 和一个整数 \(cnt\)，表示绵羊会在第 \(cnt\) 次中弹飞；否则输出 Winner 和一个整数 \(pos\)，表示 \(c_i\) 轮后绵羊的位置。

样例 #1

样例输入 #1

10 4
2 3 4 5 0 7 8 6 10 7
1 6
5 2
9 5
3 2

样例输出 #1

Loser 5
Loser 1
Winner 7
Winner 5

提示

本题没有~~恶心的~~捆绑，请放心骗分

对于 \(30\%\) 的数据，\(n \le 10^5,m \le 5000, c_i \le 5000\)。

对于另外 \(10\%\) 的数据，\(n \le 5000,m \le 3 \times 10^5,c_i \le 3 \times 10^5\)。

对于另外 \(10\%\) 的数据，\(n \le 3 \times 10^5,m \le 3 \times 10^5,c_i \le 3 \times 10^5\)。

对于另外 \(10\%\) 的数据，\(a_i > 0\)。

对于另外 \(5\%\) 的数据，\(a_i = i + 1(i \neq n),a_n = 0\)。

对于 \(100\%\) 的数据，\(1 \le n \le 3 \times 10^5,1 \le m \le 3 \times 10^5,0 \le c_i \le 10^9,0 \le a_i \le n,1 \le b_i \le n\)。