СуперНім High
Нім – це гра для двох гравців, які по черзі беруть предмети, розкладені на декілька купок. Кожен гравець своїм ходом може вибрати одну з непорожніх купок і забрати з неї довільну ненульову кількість предметів. Програє той з гравців, хто у свою чергу не зможе зробити хід (тобто останній предмет забере на попередному ході його супротивик).
Дана гра математично повністю проаналізована. Програшними позиціями у грі називаються такі позиції, що при довільних подальших ходах гравця, який повинен робити хід з даної позиції, його суперник має можливість робити такі ходи, які призведуть до програшу гравця (тобто суперник має виграшну стратегію). Виграшними – такі, що, якмим б не були у подальшому дії суперника, гравець, який виконує хід з даної позиції, має можливість робити такі ходи, які призведуть його до перемоги (тобто гравець має виграшну стратегію). Віжомо, що виграшність позиції визначається нім-сумою: p_1 xor p_2 xor ... xor p_N, де p_i – кількість предметів у i-ій купці, xor – операція побітового виключного "або" (додавання двійкових подань чисел без врахування переносів у наступні розряди). Якщо ця сума відмінна від нуля, то позиція виграшна, якщо дорівнює нулю – програшна.
Туть ми будемо мати справу з величезною кількістю купок. Ваше завдання – за заданими розмірами купок визначити кількість виграшних варіантів першого ходу першого гравця з початкової позиції (тобто такі ходи, при яких виграшна стратегія все ще буде залишатись у першого гравця).
Вхідні дані
У першому рядку вхідного файлу міститься ціле число M, яке визначає кількість груп кучок. Кожен з наступних M рядків описує відповідну групу при допомозі трьох цілих чисел a, b, N. Якщо розмістити усі купки у групі у порядку неспадання розмірів, то a – розмір найменшоїй купки, b – розмір найбільшої, N – кількість купок у групі, а різниця між розмірами двох сусідніх купок постійна.
1 ≤ M ≤ 20000, 0 ≤ a ≤ b ≤ 10^18, b-a кратно N-1.
Вихідні дані
Виведіть єдине ціле число – кількість варіантів першого хода, які допускає виграшна стратегія.