土拨鼠玩灯

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

土拨鼠蔚蔚捡到了一盏奇怪的灯

Description

这盏灯会有规律的闪烁, 灯泡每次闪烁后的颜色可以用 nn 个二元组 (a1,b1),(a2,b2),,(an,bn)(a_1,b_1),(a_2,b_2),\cdots,(a_n,b_n) 来表示。机器会对每个 i=1,2,3,,ni=1,2,3,\cdots,n闪烁 aia_i次,并且这 aia_i次闪烁发出的颜色都为 bib_i

现在蔚蔚想知道,机器第 mm 次闪烁后,发出的颜色是什么。

Format

Input

第一行两个正整数 n,mn,m

第二行 nn 个正整数 a1,,ana_1,\cdots,a_n

第三行 nn个正整数 b1,,bnb_1,\cdots,b_n

Output

输出一行一个正整数表示答案。

Samples

样例1

4 5
1 2 3 4
4 3 2 1
2

样例解释1

机器一共闪烁了 1010 次。每次闪烁后颜色分别为:4,3,3,2,2,2,1,1,1,14,3,3,2,2,2,1,1,1,1

55 次闪烁后,机器的颜色为 22

样例2

4 3
1 1 1 1
1 2 3 4
3

样例解释2

机器一共闪烁了 44 次。每次闪烁后颜色分别为:1,2,3,41,2,3,4

33 次闪烁后,机器的颜色为 33

Limitation

对于 100%100\% 的数据,1n105,1m,ai,bi109,mai1\le n\le 10^5,1\le m,a_i,b_i\le 10^9,m\le \sum a_i

注意

输出时每行末尾的多余空格,不影响答案正确性

要求使用「文件输入输出」的方式解题,输入文件为 city.in,输出文件为 city.out

菜就多练

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
23
Start at
2024-3-2 19:00
End at
1970-1-1 8:00
Duration
-474827 hour(s)
Host
Partic.
0