题目描述

小T今天来到了著名的旅游城市莆田，小T想要好好感受一下莆田的风土人情和美景美食。

今天小T决定开始感受莆田的美景，小T今天来到了一个景点，景点有个人正在表演帽子戏法，开始桌 上摆了 n 个帽子，只有第 k 个帽子里有一个小球，之后会进行 m 次操作，每次操作可以选择两个 编号 x 和 y, 满足li≤x,y≤ri, 然后将第 x 个帽子和第 y 个帽子里的东西做交换，经过 m 次 操作之后，大家都不知道小球到底在哪个帽子里了，可表演者每次都能准确指出小球在哪里。现在小T 想知道，小球所在位置到底有多少种可能性?

由于小T的时间都要用来感受莆田的美景，没有时间计算这个问题，请你帮助小T计算一下这个问题。

输入格式

第一行三个整数 n,m,k, 表示帽子数，操作数和开始小球所在位置。

接下来 m 行，每行用空格隔开的两个整数 l; 和 ri, 表示第 i 次操作的范围。

输出格式

一行一个整数表示答案。

样例

4 2 1

2 4

1 2

2

数据范围

对于 3 0 % 的 数 据 ，m=1。

对于 50%的数据，1≤ n≤10⁵。

对于100%的数据，1≤n≤10⁹,1≤m≤100,1≤k≤n,l≤li≤ri≤n。