ساكوراكوا والأسطورة المسروقة#412

ساكوراكوا والأسطورة المسروقة

ثانيتان
256 ميغابايت
Hard

ابتكار أساطير ترضي جميع المشاركين في UJGOI هو مهمة ضخمة.

لهذا السبب تم سرقة هذه الأسطورة.

أنت مُعطى رسم بياني موجه يحتوي على رأسًا والذي يكون فارغًا في البداية. بدءًا من الثانية الأولى، يتم إضافة حافة موجهة إلى هذا الرسم البياني في كل ثانية.

مهمتك هي معالجة استفسارات.

كل استفسار مُعطى برقمين و . مهمتك هي تحديد اللحظة الأولى في الوقت التي يوجد فيها مسار من إلى ومن إلى .

إذا لم يكن هناك مسار من إلى أو من إلى حتى بعد إضافة جميع الحواف، يجب عليك إخراج .

أيضًا، إذا كان x=y، يجب عليك إخراج .

Input

السطر الأول يحتوي على أربعة أعداد صحيحة n,m,q,t (1\le n,m,q\le 3\cdot 10^5; t \in \{0,1\}).

كل من الأسطر التالية تحتوي على عددين صحيحين v_i و u_i (1 \leq v_i, u_i \leq n) — الحواف التي تُضاف إلى رسم بياني فارغ في الترتيب الذي تُضاف به.

كل من الأسطر التالية تحتوي على عددين صحيحين و (1\le x, y \le n)، والتي تمثل استفسارًا.

عندما يكون t=0، يتم إعطاء كل استفسار بدون تشفير.

عندما يكون t=1، يتم إعطاء كل استفسار مع تشفير:

  1. في البداية، key=0. عندما يتم إعطاؤك الأعداد الصحيحة في استفسار، تقوم بتشكيل الأعداد الصحيحة ;

  2. x=(key-1 + a) \mod n+1;

  3. y=(key-1 + b) \mod n+1;

  4. بعد ذلك، تجيب على الاستفسار؛ دع يكون الجواب لهذا الاستفسار، ثم تقوم بتحديث key = ans قبل الإجابة على الاستفسار التالي.

Output

لكل استفسار، أخرج الجواب.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

الرسم البياني لكل من الأمثلة. كل حافة لها علامة تدل على اللحظة الزمنية التي تمت إضافتها فيها. لاحظ أن المثال الثاني مشفر؛ بعد الوصف الصحيح، ستبقى مع نفس الاستفسارات كما في حالة الاختبار الأولى.

بالنسبة للعقد ، ليس من الصعب أن نرى أنه فقط عندما تكون جميع الحواف حتى الحافة السادسة موجودة، يوجد مسار من إلى ومن إلى .

بالنسبة للعقد ، حتى عندما تكون جميع الحواف موجودة، لا يوجد مسار من إلى .

بالنسبة للعقد ، فقط عندما تكون جميع الحواف موجودة، يوجد مسار من إلى ومن إلى .

بالنسبة للعقد ، حتى عندما تكون جميع الحواف موجودة، لا يوجد مسار من إلى .

بالنسبة للعقد ، فقط عندما تكون جميع الحواف موجودة، يوجد مسار من إلى ومن إلى .

Scoring

  1. ( نقاط): n,m\le 80, t = 0;

  2. ( نقاط): n,m\le 10^3, t = 0;

  3. ( نقاط): q \le 100, t = 0;

  4. ( نقاط): t = 0;

  5. ( نقاط): بدون قيود إضافية.