{"code":"2024febplatinum3","name":"USACO 2024 February Contest, Platinum, Infinite Adventure","description":"Bessie đang lên kế hoạch cho chuyến thám hiểm tại một vùng đấy có $N(1 \\le N \\le 10^5)$ thành phố. Tại mỗi thành phố $i$, có một cái cổng, cũng như một chu kỳ $T_i$. Tất cả $T_i$ đều là lũy thừa của $2$, và $T_1+...+T_N \\le 10^5$. Nếu bạn đến cổng của thành phố $i$ vào ngày $t$, bạn sẽ ngay lập tức thoát ra tại cổng của thành phố $c_{i,t \\space mod \\space T_i}$.\r\n\r\nBessie có $Q(1 \\le Q \\le 5*10^4)$ kế hoạch cho chuyến đi, mỗi kế hoạch được thể hiện bởi bộ ba số $(v,t,Δ)$. Với mỗi kế hoạch, cô ấy sẽ bắt đầu tại thành phố $v$ vào ngày $t$. Cô ấy sẽ làm hành động sau $Δ$ lần: Cô ấy sẽ đi theo cổng của thành phố hiện tại, sau đó đợi một ngày. Với mỗi kế hoạch, cô ấy muốn biết mình sẽ kết thúc tại thành phố nào.\r\n\r\n#### Input\r\n- Dòng đầu chứa hai số nguyên cách nhau bởi dấu cách: $N$ - số đỉnh, và $Q$ - số truy vấn.\r\n\r\n- Dòng thứ hai chứa $N$ số nguyên cách nhau bởi dấu cách: $T_1,T_2,...,T_N(1 \\le T_i, \\space T_i$ là một lũy thừa của $2$, $T_1+...+T_N \\le 10^5)$.\r\n\r\n- Với $i=1,2,…,N$, dòng thứ $i+2$ chứa $T_i$ số nguyên dương được ngăn cách bởi dấu cách: $c_{i,0},…,c_{i,Ti−1}(1≤c_{i,t} \\le N)$.\r\n\r\n- Với $j=1,2,…,Q$, dòng thứ $j+N+2$ chứa ba số nguyên dương được ngăn cách bởi dấu cách: $v_j,t_j,Δ_j(1 \\le v_j \\le N, \\space 1 \\le t_j \\le 10^{18},\\space 1 \\le Δ_j \\le 10^{18})$ của truy vấn thứ $j$.\r\n\r\n#### Output\r\nIn ra $Q$ dòng. Dòng thứ $j$ chứa đáp án của truy vấn thứ $j$.\r\n#### Scoring\r\n- Subtask $1$: $Δ_j \\le 2*10^2$.\r\n- Subtask $2$: $N,\\sum T_j \\le 2*10^3$.\r\n- Subtask $3$: $N,\\sum T_j \\le 10^4$.\r\n- Subtask $4$: Không có điểu kiện gì thêm.\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```\r\n        5 4\r\n        1 2 1 2 8\r\n        2\r\n        3 4\r\n        4\r\n        2 3\r\n        5 5 5 5 5 1 5 5\r\n        2 4 3\r\n        3 3 6\r\n        5 3 2\r\n        5 3 7\r\n        ```\r\n    ???+ \"Output\"\r\n        ```\r\n        2\r\n        2\r\n        5\r\n        4\r\n        ```\r\n    ??? warning \"Note\"\r\n        Ba chuyến thám hiểm đầu của Bessie diễn ra như sau:\r\n\r\n        - Tại chuyến thám hiểm thứ nhất, cô ấy đi từ thành phố $2$ tại thời điểm $4$, đến thành phố $3$ tại thời điểm  $5$, đến thành phố $4$ tại thời điểm  $6$, đến thành phố $2$ tại thời điểm $7$.\r\n        - Tại chuyến thám hiểm thứ hai, cô ấy đi từ thành phố $3$ tại thời điểm $3$, đến thành phố $4$ tại thời điểm  $4$, đến thành phố $2$ tại thời điểm  $5$, đến thành phố $4$ tại thời điểm  $6$, đến thành phố $2$ tại thời điểm  $7$, đến thành phố $4$ tại thời điểm  $8$, đến thành phố $2$ tại thời điểm  $9$.\r\n        - Tại chuyến thám hiểm thứ ba, cô ấy đi từ thành phố $5$ tại thời điểm $3$, đến thành phố $5$ tại thời điểm  $4$, đến thành phố $5$ tại thời điểm $5$.\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```\r\n        5 5\r\n        1 2 1 2 8\r\n        2\r\n        3 4\r\n        4\r\n        2 3\r\n        5 5 5 5 5 1 5 5\r\n        2 4 3\r\n        3 2 6\r\n        5 3 2\r\n        5 3 7\r\n        5 3 1000000000000000000\r\n        ```\r\n    ???+ \"Output\"\r\n        ```\r\n        2\r\n        3\r\n        5\r\n        4\r\n        2\r\n        ```","points":1000.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}