TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1143
  • Problem
  • P1143(校内赛三)校门外的树2.0
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    NK中学校大门外有一条长度为L的笔直马路。在这条路的人行道上种有棵树。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上有L+1个整数点,即0,1,2,……,L,有的点上可能种有一棵树,每个点上最多只有一棵树。
    该地区的市政部门经常把人行道挖烂了再铺好,铺好了再挖烂。所以有的树在一年时间内会被反复挖倒很多次(每次施工结束时会再次把树栽好)。去年市政部门总共施工了M次,现在告诉你每次施工的起始点和终止点。问,这条路上哪些树被挖倒的次数最多。

    Input Format

    第一行有三个空格间隔的整数L、N和 M ,L代表马路的长度,N代表树的总数,M代表施工的次数。
    接下来一行有N个空格间隔的整数,表示每棵树所在的位置。
    接下来的M行每行包含两个整数,用一个空格隔开,表示一次施工的起始点和终止点的坐标。

    Output Format

    共一行,包含若干个空格间隔整数(由小到大排列),表示被挖倒次数最多的树的位置。

    Sample Input

    500 5 3
    190 3 10 175 220
    150 300
    100 200
    170 471

    Sample Output

    175 190

    Hint

    位于3和10位置的树一次也没被挖倒
    位于175和190位置的树被挖到了3次
    位于220位置的树被挖倒了2次
    所以答案是175和190
    【数据范围】
    0<=L<=1000000000
    1<=N<=1000
    0<=M<=1000
    数据保证至少有一棵树会被挖倒