#P18831. [Croatian CPC2019] Dramatični Dvoboj

[Croatian CPC2019] Dramatični Dvoboj

[Croatian CPC2019] Dramatični Dvoboj

题目描述

有 nn 种长方形地毯,每种都有无限多张。第 ii 种地毯的两条边分别标为 SS 和 DD,长度分别为 sis_i 和 did_i。

Malnar 与另一名玩家进行游戏。游戏开始前,Malnar 在地上放置 kk 张地毯,分别作为 kk 堆地毯的底层,其中第 ii 张地毯的种类为 aia_i。对于每张初始地毯,Malnar 可以任选以下两种朝向之一:

  • SS 边水平放置,水平、竖直边长分别为 sai,dais_{a_i},d_{a_i};
  • DD 边水平放置,水平、竖直边长分别为 dai,said_{a_i},s_{a_i}。

接下来,由另一名玩家先手,两人轮流操作。每次操作选取任意种类的一张新地毯,放到某一堆的最上方。新放的地毯必须将 SS 边水平放置,不能旋转,且其水平边长和竖直边长必须分别严格小于该堆原来最上方地毯的对应边长。

无法进行操作的玩家输掉游戏。双方都采用最优策略。

请为 Malnar 找到一种初始 kk 张地毯的朝向安排,使他能够获胜,或者判断不存在这样的安排。

输入格式

第一行包含两个整数 n,kn,k(1≤n,k≤1051\le n,k\le10^5)。

接下来 nn 行,第 ii 行包含两个整数 si,dis_i,d_i(1≤si,di≤1051\le s_i,d_i\le10^5)。保证所有 sis_i 两两不同,所有 did_i 两两不同。

最后一行包含 kk 个整数 a1,…,aka_1,\ldots,a_k(1≤ai≤n1\le a_i\le n),表示初始地毯的种类。同一种类可以重复出现。

输出格式

如果不存在使 Malnar 获胜的安排,输出 nemoguce。

否则,输出一个长度为 kk 的连续二进制字符串:第 ii 个字符为 0 表示第 ii 张初始地毯的 SS 边水平放置,为 1 表示其 DD 边水平放置。

如果存在多种合法答案,输出任意一种。

样例 1

输入

5 3
1 1
2 3
4 2
3 4
5 5
1 3 4

输出

001

样例 2

输入

5 3
1 1
2 3
4 2
3 4
5 5
1 2 5

输出

nemoguce